title: Indel-tolerant read mapping with trinucleotide frequencies using cache-oblivious kd-trees.
abstract: BACKGROUND
  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 L(1) 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 L(1) 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.
  
  
  METHODS
  TreQ will be released under the GNU Public License (GPL), and precomputed genome indices will be provided for download at http://treq.sf.net.
  
  
  BACKGROUND
  pavelm@cs.rutgers.edu
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Department of Computer Science, Rutgers University, New Jersey, USA. pavelm@cs.rutgers.edu
authors.forename: Md Pavel
authors.initials: MP
authors.lastname: Mahmud
authors.forename: John
authors.initials: J
authors.lastname: Wiedenhoeft
authors.forename: Alexander
authors.initials: A
authors.lastname: Schliep
mesh_terms: D002874:Chromosome Mapping; D014644:Genetic Variation; D015894:Genome, Human; D023281:Genomics / Q000379:methods; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D054643:INDEL Mutation; D009711:Nucleotides / Q000737:chemistry; D017422:Sequence Analysis, DNA / Q000379:methods*
chemical_list: D009711:Nucleotides