title: BitMapper: an efficient all-mapper based on bit-vector computing.
abstract: BACKGROUND
  As the next-generation sequencing (NGS) technologies producing hundreds of millions of reads every day, a tremendous computational challenge is to map NGS reads to a given reference genome efficiently. However, existing methods of all-mappers, which aim at finding all mapping locations of each read, are very time consuming. The majority of existing all-mappers consist of 2 main parts, filtration and verification. This work significantly reduces verification time, which is the dominant part of the running time.
  
  
  RESULTS
  An efficient all-mapper, BitMapper, is developed based on a new vectorized bit-vector algorithm, which simultaneously calculates the edit distance of one read to multiple locations in a given reference genome. Experimental results on both simulated and real data sets show that BitMapper is from several times to an order of magnitude faster than the current state-of-the-art all-mappers, while achieving higher sensitivity, i.e., better quality solutions.
  
  
  CONCLUSIONS
  We present BitMapper, which is designed to return all mapping locations of raw reads containing indels as well as mismatches. BitMapper is implemented in C under a GPL license. Binaries are freely available at http://home.ustc.edu.cn/%7Echhy.
authors.affiliation: Key Laboratory on High Performance Computing, Hefei, Anhui230027, P.R. China. chhy@mail.ustc.edu.cn.|School of Computer Science, University of Science and Technology of China, Hefei, Anhui, 230027, P.R. China. chhy@mail.ustc.edu.cn.
authors.forename: Haoyu
authors.initials: H
authors.lastname: Cheng
authors.affiliation: Key Laboratory on High Performance Computing, Hefei, Anhui230027, P.R. China. jhp9650@mail.ustc.edu.cn.|School of Computer Science, University of Science and Technology of China, Hefei, Anhui, 230027, P.R. China. jhp9650@mail.ustc.edu.cn.
authors.forename: Huaipan
authors.initials: H
authors.lastname: Jiang
authors.affiliation: Hefei University of Technology, Hefei, 230009, China. jiaoyun@hfut.edu.cn.
authors.forename: Jiaoyun
authors.initials: J
authors.lastname: Yang
authors.affiliation: Key Laboratory on High Performance Computing, Hefei, Anhui230027, P.R. China. xuyun@ustc.edu.cn.|School of Computer Science, University of Science and Technology of China, Hefei, Anhui, 230027, P.R. China. xuyun@ustc.edu.cn.
authors.forename: Yun
authors.initials: Y
authors.lastname: Xu
authors.affiliation: Department of Computer Science, University of Missouri-Columbia, Columbia MO, 65203, USA. ShangY@missouri.edu.
authors.forename: Yi
authors.initials: Y
authors.lastname: Shang
mesh_terms: D000465:Algorithms; D000818:Animals; D017360:Arabidopsis / Q000235:genetics; D017173:Caenorhabditis elegans / Q000235:genetics; D003205:Computing Methodologies; D016678:Genome; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D054643:INDEL Mutation; D012984:Software