Anzeige
Erschienen in:
2022 | OriginalPaper | Buchkapitel
Fast and Optimal Sequence-to-Graph Alignment Guided by Seeds
verfasst von : Pesho Ivanov, Benjamin Bichsel, Martin Vechev
Erschienen in: Research in Computational Molecular Biology
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We present a novel A\(^\star \) seed heuristic that enables fast and optimal sequence-to-graph alignment, guaranteed to minimize the edit distance of the alignment assuming non-negative edit costs.
We phrase optimal alignment as a shortest path problem and solve it by instantiating the A\(^\star \) algorithm with our seed heuristic. The seed heuristic first extracts non-overlapping substrings (seeds) from the read, finds exact seed matches in the reference, marks preceding reference positions by crumbs, and uses the crumbs to direct the A\(^\star \) search. The key idea is to punish paths for the absence of foreseeable seed matches. We prove admissibility of the seed heuristic, thus guaranteeing alignment optimality.
Our implementation extends the free and open source aligner and demonstrates that the seed heuristic outperforms all state-of-the-art optimal aligners including GraphAligner, Vargas, PaSGAL, and the prefix heuristic previously employed by AStarix. Specifically, we achieve a consistent speedup of >60\(\times \) on both short Illumina reads and long HiFi reads (up to 25 kbp), on both the E. coli linear reference genome (1 Mbp) and the MHC variant graph (5 Mbp). Our speedup is enabled by the seed heuristic consistently skipping >99.99% of the table cells that optimal aligners based on dynamic programming compute.
AStarix Aligner and Evaluations: https://github.com/eth-sri/astarix.