A novel fast multiple nucleotide sequence alignment method based on FM-index.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Multiple sequence alignment (MSA) is crucial for biological analyses but struggles with large, long sequences.
• Classical MSA algorithms face scalability challenges with increasing genomic data.
• Existing divide-and-conquer methods rely on accurate identification of common segments (anchors).

Purpose of the Study:

• To develop a novel algorithm, FMAlign, for efficient and accurate multiple nucleotide sequence alignment.
• To address the limitations of existing MSA methods in handling large-scale and long sequences.
• To improve the performance of sequence alignment through optimized segment selection.

Main Methods:

• Proposed FMAlign, a novel algorithm employing FM-index for efficient extraction of long common segments.
• Utilized FM-index to identify sequence anchors, avoiding space-consuming hash tables.
• Implemented a divide-and-conquer strategy based on identified long common segments.

Main Results:

• FMAlign demonstrated superior running time compared to existing methods like MAFFT, HAlign, and FAME.
• The algorithm achieved high accuracy, particularly on long sequence datasets.
• FMAlign proved effective for large-scale nucleotide sequences in terms of both length and number.

Conclusions:

• FMAlign offers a significant improvement in speed and accuracy for multiple nucleotide sequence alignment.
• The FM-index based approach provides an efficient solution for handling large genomic datasets.
• FMAlign is a viable tool for large-scale genomic sequence analysis, applicable to diverse biological datasets.