Repository: Freie Universität Berlin, Math Department

Fast and accurate read mapping with approximate seeds and multiple backtracking

Siragusa, E. and Weese, D. and Reinert, K. (2013) Fast and accurate read mapping with approximate seeds and multiple backtracking. Oxford Journals, 41 (7). e78. ISSN Print ISSN 0305-1048; Online ISSN 1362-4962

Full text not available from this repository.

Official URL:


We present Masai, a read mapper representing the state-of-the-art in terms of speed and accuracy. Our tool is an order of magnitude faster than RazerS 3 and mrFAST, 2–4 times faster and more accurate than Bowtie 2 and BWA. The novelties of our read mapper are filtration with approximate seeds and a method for multiple backtracking. Approximate seeds, compared with exact seeds, increase filtration specificity while preserving sensitivity. Multiple backtracking amortizes the cost of searching a large set of seeds by taking advantage of the repetitiveness of next-generation sequencing data. Combined together, these two methods significantly speed up approximate search on genomic data sets. Masai is implemented in C++ using the SeqAn library. The source code is distributed under the BSD license and binaries for Linux, Mac OS X and Windows can be freely downloaded from

Item Type:Article
Subjects:Biological Sciences
Mathematical and Computer Sciences
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:1161
Deposited By: AG Alg BioInf
Deposited On:12 Sep 2012 08:48
Last Modified:10 Aug 2013 09:39

Repository Staff Only: item control page