Large multiple sequence alignments with a root-to-leaf regressive method.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple sequence alignments (MSAs) are crucial for structural and evolutionary predictions.
• Existing progressive MSA algorithms struggle with accuracy and scalability for large datasets.
• The complexity of aligning millions of sequences necessitates novel computational approaches.

Purpose of the Study:

• To introduce a novel regressive algorithm for multiple sequence alignment.
• To enhance the accuracy and scalability of MSA for extremely large genomic datasets.
• To enable the analysis of datasets comprising millions of sequences on standard hardware.

Main Methods:

• Developed a regressive algorithm that aligns the most dissimilar sequences first.
• Employed an efficient divide-and-conquer strategy to manage large-scale alignments.
• Integrated third-party alignment tools to run in linear time, irrespective of inherent complexity.

Main Results:

• The regressive algorithm successfully aligns up to 1.4 million sequences on a standard workstation.
• Demonstrated substantial accuracy improvements for datasets exceeding 10,000 sequences.
• The method offers linear time complexity, overcoming limitations of previous algorithms.

Conclusions:

• The regressive algorithm provides a scalable and accurate solution for large-scale MSA.
• This approach is suitable for analyzing massive genomic datasets, such as the Earth BioGenome Project.
• Enables new possibilities for evolutionary and structural studies using unprecedented data volumes.