Random Permutations Based Alignment / “Shuffling-Based” Alignment
An introduction paper: “A Random-Permutations-Based Approach to Fast Read Alignment” (RECOMB-SEQ 2013).
Additional applications: Assembly and more.
Assembly: the algorithm is also used to construct approximate overlap graphs. These graph are used for fast assembly. Note that the algorithm allows errors in the reads, so no error correction is necessary prior to the construction of the graph. See: technical report.
More about using permutations-based search for assembly, error correction and other applications by constructing graphs of reads: search / alignment page.
Long-Range “Independence” in DNA
Homopolymer Length Filters
Homopolymer length filters eliminate the mapping problem caused by homopolymer length errors (ionTorrent/454). A technical report about “Homopolymer Length Filters” is available here.
More information: HPLFs page.