A Randomized Algorithm for Aligning DNA Sequences to Reference Genomes

摘要

The alignment of reads generated by next- generation sequencers is an important problem in many biomedical applications. Although many methods have been proposed, we introduce a new randomized algorithm with the distinction of having high performance across a wide range of read lengths and base error rates. We utilize two FM indices to facilitate efficient bidirectional searching. Randomization allows us to estimate effectively key parameters, which ultimately account for the consistency in performance of the method. Our method by and large outperformed some of the recent and popular methods over a wide range of read lengths and base error rates.