A tool for mapping (short) DNA reads into reference sequences.
  • Align reads using either k-mismatches or k-errors (mismatches, insertions and deletions) model; see README for different alignment modes.
  • Algorithms are based on Burrows-Wheeler transform and backward backtracking, see the paper for details.
  • Includes a novel data structure called the rotation index that finds alignments with higher number of mismatches in feasible time (but requires a larger index and fixed length query reads). Please see the paper for details.
  • Supports FASTA and FASTQ input, and SAMTools output.

See README in the package for further information.


2012-November A small bug fix: Callcounter not reinitialized between reads causing tail of the read set not mapped.
2010-04-27 First public release: Supports FASTA and FASTQ input and SAMToolsrlcsa), and parallel searching (OpenMP). Alignment with mismatches (a hybrid algorithm or rotation indexes), or with mismatches and indels (suffix filters).


November 2012 Small bug fix (callcounter not reinitialized between reads)
April 2010 First public release (--gap and --mate-pair not yet implemented).


V. Mäkinen, N. Välimäki, A. Laaksonen and R. Katainen: Unified View of Backward Backtracking in Short Read Mapping. To appear in Ukkonen Festschrift 2010 (Eds. Tapio Elomaa, Pekka Orponen, Heikki Mannila), Springer-Verlag, LNCS 6060, pp. 182-195, 2010.