FMAlign2

FMAlign2 leverages suffix arrays and a vertical division strategy to perform fast multiple sequence alignment of ultralong nucleotide sequences, redefining the approach of its predecessor from searching for global chains to partial chains.

Key Features:

• Suffix Array-based Seed Identification: FMAlign2 uses suffix arrays to identify maximal exact matches for sequence segmentation.
• Partial Chain Search: The method redefines the approach from searching for global chains to partial chains, improving upon the FM-index-based common seed extraction of FMAlign.
• Vertical Division Strategy: Large-scale alignment problems are deconstructed into manageable subMSA tasks that execute in parallel.
• Sequence-Profile Alignment and Refinement: These steps concatenate alignment subsets to yield the final result.
• Ultrong Sequence Capability: FMAlign2 handles sequences reaching billions in length within an acceptable time frame while maintaining accuracy.

Scientific Applications:

• Multiple Sequence Alignment of Ultralong Nucleotide Sequences: FMAlign2 aligns nucleotide sequences that conventional methods struggle to process due to extreme length.
• Large-Scale Genomic Dataset Analysis: The tool enables parallel execution of subMSA on deconstructed sequence segments for efficient processing of billion-length sequences.

Methodology:

FMAlign2 leverages suffix arrays to identify maximal exact matches, uses a vertical division strategy to deconstruct large-scale problems into parallel subMSA tasks, and applies sequence-profile alignment and refinement to concatenate subsets into the final alignment.