A Convex Atomic-Norm Approach to Multiple Sequence Alignment and Motif Discovery.

Area of Science:

• Bioinformatics
• Computational Biology
• Optimization

Background:

• Multiple Sequence Alignment (MSA) and Motif Discovery are critical NP-hard problems in bioinformatics.
• Current methods rely on local search (e.g., Expectation Maximization, Gibbs Sampling) or greedy heuristics.
• These existing approaches often face limitations in solution quality and scalability.

Purpose of the Study:

• To develop a novel convex relaxation approach for MSA and Motif Discovery.
• To introduce an efficient algorithm for solving the proposed convex relaxation.
• To demonstrate the superiority of the new method over established bioinformatics tools.

Main Methods:

• Formulated MSA and Motif Discovery as convex optimization problems using atomic norms.
• Developed the Greedy Direction Method of Multiplier (GDMM) algorithm.
• Applied GDMM to solve the convex relaxation with two convex atomic constraints.

Main Results:

• The proposed convex relaxation approach achieved higher quality solutions for MSA and Motif Discovery.
• Experimental results demonstrated significant improvements over standard bioinformatics tools.
• The GDMM algorithm efficiently solved the complex convex optimization problems.

Conclusions:

• Convex relaxation offers a powerful new paradigm for tackling NP-hard problems in bioinformatics.
• The developed method provides a more accurate and effective approach to MSA and Motif Discovery.
• This work advances computational methods in bioinformatics, offering practical benefits for biological data analysis.