Department of Computer Science
 Rutgers University

Home page

Home page  Contact us  Site map 




Indel-tolerant Read Mapping with Trinucleotide Frequencies using Cache-Oblivious kd-Trees

M. Mahmud, J. Wiedenhoeft and A. Schliep

Bioinformatics 2012, 28:18, i325–i332.

Motivation: Mapping billions of reads from next generation sequencing experiments to reference genomes is a crucial task, which can require hundreds of hours of running time on a single CPU even for the fastest known implementations. Traditional approaches have difficulties dealing with matches of large edit distance, particularly in the presence of frequent or large insertions and deletions (indels). This is a serious obstacle both in determining the spectrum and abundance of genetic variations and in personal genomics.Results: For the first time, we adopt the approximate string matching paradigm of geometric embedding to read mapping, thus rephrasing it to nearest neighbor queries in a q-gram frequency vector space. Using the L1 distance between frequency vectors has the benefit of providing lower bounds for an edit distance with affine gap costs. Using a cache-oblivious kd-tree, we realize running times, which match the state-of-the-art. Additionally, running time and memory requirements are about constant for read lengths between 100 and 1000 bp. We provide a first proof-of-concept that geometric embedding is a promising paradigm for read mapping and that L1 distance might serve to detect structural variations. TreQ, our initial implementation of that concept, performs more accurate than many popular read mappers over a wide range of structural variants. Availability and implementation: TreQ will be released under the GNU Public License (GPL), and precomputed genome indices will be provided for download at Contact:

Presented on April 16, 2012 by Md Mahmud at DIMACS, Rutgers (Invited Talk), on May 25, 2012 by Alexander Schliep at CBRC, AIST, Tokyo, Japan (Invited Talk), on Sept. 12, 2012 by Alexander Schliep at ECCB 2012, the European Conference on Computational Biology, Basel, Switzerland (Contributed Talk), on Sept. 17, 2012 by Alexander Schliep at Kolloquium der Fakultät für Mathematik und Informatik, FernUniversität in Hagen, Germany (Invited Talk).