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  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).
- Supports FASTA and FASTQ input, and SAMTools output.
See README in the package for further information.
Return to the SuDS homepage.
- 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 SAMTools output format. Includes incremental BWT construction (rlcsa), 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.