readaligner

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 [1] for details.
Includes a novel data structure called the rotation index [1] 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.

News

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 [1]), or with mismatches and indels (suffix filters).

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.
[springerlink]