Hobbes: optimized gram-based methods for efficient read alignment.

ABSTRACT: Recent advances in sequencing technology have enabled the rapid generation of billions of bases at relatively low cost. A crucial first step in many sequencing applications is to map those reads to a reference genome. However, when the reference genome is large, finding accurate mappings poses a significant computational challenge due to the sheer amount of reads, and because many reads map to the reference sequence approximately but not exactly. We introduce Hobbes, a new gram-based program for aligning short reads, supporting Hamming and edit distance. Hobbes implements two novel techniques, which yield substantial performance improvements: an optimized gram-selection procedure for reads, and a cache-efficient filter for pruning candidate mappings. We systematically tested the performanc

SUBMITTER: Ahmadi A 

PROVIDER: S-EPMC3315303 | biostudies-literature | 2012 Mar

REPOSITORIES: biostudies-literature