Fast inexact mapping using advanced tree exploration on backward search methods.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Next Generation Sequencing (NGS) relies on seeding and local alignment for short sequence mapping.
• Existing backward search algorithms (Burrows Wheeler Transform, Ferragina and Manzini Index, Suffix Arrays) are computationally expensive with errors.
• Current methods struggle with increased computational cost when accommodating insertions, deletions, and mismatches.

Purpose of the Study:

• To present an inexact sequence mapping algorithm utilizing pruning strategies for search tree exploration.
• To improve the efficiency of sequence alignment in the presence of errors.
• To reduce the computational burden of mapping short reads in genomic data.

Main Methods:

• Developed an inexact mapping algorithm employing pruning strategies for search tree exploration.
• Implemented an out-of-core index for handling large genomes with limited memory.
• Evaluated the algorithm's performance as a preprocessing step for sequence mappers.

Main Results:

• Achieved a 13x speed-up over similar algorithms with up to 6 base errors (insertions, deletions, mismatches).
• Successfully processed 400 bps reads with up to 9 errors on an Illumina dataset.
• Reduced the number of reads needing alignment by 55%, leading to 20-40% overall execution time reduction.

Conclusions:

• The algorithm serves as an effective preprocessing step for modern sequence mappers.
• It significantly accelerates overall alignment time by reducing the number of reads to be aligned.
• The method can enhance the seeding step of existing sequence mappers and supports large-scale genomic analysis.