Sequence embedding for fast construction of guide trees for multiple sequence alignment.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple sequence alignment (MSA) relies on initial sequence clustering.
• Traditional clustering methods require N2 computation for N sequences, becoming prohibitive for large datasets (>10,000).
• High computational and memory costs limit large-scale MSA.

Purpose of the Study:

• To develop and test novel embedding methods for efficient clustering of large sequence sets.
• To overcome the computational barriers of traditional pairwise distance calculations in sequence clustering.

Main Methods:

• Utilized embedding methods to approximate sequence similarities in a reduced space.
• Avoided the need for computing a full pairwise distance matrix for all sequences.

Main Results:

• Demonstrated significant reductions in computation time and memory requirements for large-scale sequence clustering.
• Validated the quality of generated clusters by using them as guide trees for multiple sequence alignment.

Conclusions:

• The proposed embedding approach offers a scalable solution for clustering massive sequence datasets.
• This method facilitates large-scale multiple sequence alignments by providing efficient and accurate clustering.
• Source code is available for download.