Label-guided seed-chain-extend alignment on annotated De Bruijn graphs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Scalable De Bruijn graph-based (DBG) indexing is crucial for searching large sequencing databases.
• Low-depth sequencing creates fragmented subgraphs, hindering accurate long-read alignment.
• Existing aligners struggle with fragmentation, leading to low recall or reduced accuracy due to irrelevant sample combinations.

Purpose of the Study:

• Introduce a novel scoring model, multi-label alignment (MLA), for annotated DBGs.
• Address challenges in long-read alignment caused by fragmented sequencing data.
• Improve the biological relevance and accuracy of alignments in large sequencing datasets.

Main Methods:

• Developed MLA with 'Label Change' and 'Node Length Change' operations for biologically relevant sample combinations and improved connectivity.
• Implemented MLA using a two-step approach: single-label seed-chain-extend aligner (SCA) and multi-label chainer (MLC).
• SCA provides initial alignments, while MLC refines them using MLA scoring for multi-label chains and final alignments.

Main Results:

• MLA significantly improves taxonomic classification accuracy, reducing average weighted UniFrac errors by 63.1%-66.8%.
• MLA covers 45.5%-47.4% more long-read query characters compared to state-of-the-art aligners.
• MLA achieves competitive runtimes, faster than single-label alignment and comparable to label-combining methods.

Conclusions:

• MLA effectively produces biologically relevant alignments, overcoming fragmentation issues in DBGs.
• The method enhances the accuracy and recall of long-read alignment in large sequencing databases.
• MLA offers a scalable and accurate solution for analyzing fragmented sequencing data.