Scalable Convex Multiple Sequence Alignment via Entropy-Regularized Dual Decomposition

Area of Science:

• Bioinformatics
• Computational Biology
• Optimization

Background:

• Multiple Sequence Alignment (MSA) is crucial for biological sequence analysis, aiding in phylogenetic tree construction, profile generation, and protein structure prediction.
• The NP-hard nature of MSA necessitates heuristic and local-search methods, though a recent convex optimization approach showed promise.
• Existing convex programming methods for MSA face scalability issues, limited to short sequences (up to 50) and exhibiting slow convergence.

Purpose of the Study:

• To address the limitations of existing convex optimization approaches for Multiple Sequence Alignment (MSA).
• To develop a more efficient and scalable algorithm for MSA that can handle significantly longer biological sequences.
• To improve the quality and speed of MSA through a novel algorithmic approach.

Main Methods:

• Proposed an accelerated dual decomposition algorithm for MSA.
• Incorporated entropy regularization to achieve closed-form solutions for subproblems.
• Developed a single-loop algorithm with iteration complexity linear to the total sequence length.

Main Results:

• The accelerated dual decomposition algorithm significantly enhances alignment quality for sequences up to hundreds in length.
• The new method demonstrates superior performance compared to existing techniques, including the previous convex programming approach.
• The algorithm overcomes the convergence limitations of prior methods, which failed for longer sequences.

Conclusions:

• The proposed accelerated dual decomposition algorithm offers a scalable and effective solution for Multiple Sequence Alignment.
• This advancement enables high-quality MSA for longer biological sequences, expanding the applicability of convex optimization in bioinformatics.
• The developed method represents a significant improvement over existing MSA algorithms, particularly in terms of speed and handling of large datasets.