Fast Mapping of Short Sequences with Mismatches, Insertions and Deletions Using Index Structures

By S. Hoffmann, C. Otto, Stefan Kurtz, C. Sharma, P. Khaitovich, Jörg Vogel, Peter F. Stadler, Jörg Hackermüller. PLoS Comput. Biol., 2009

549 citations recorded by the source corpus.

With few exceptions, current methods for short read mapping make use of simple seed heuristics to speed up the search. Most of the underlying matching models neglect the necessity to allow not only mismatches, but also insertions and deletions. Current evaluations indicate, however, that very different error models apply to the novel high-throughput sequencing methods. While the most frequent error-type in Illumina reads are mismatches, reads produced by 454's GS FLX predominantly contain insertions and deletions (indels). Even though 454 sequencers are able to produce longer reads, the method is frequently applied to small RNA (miRNA and siRNA) sequencing. Fast and accurate matching in particular of short reads with diverse errors is therefore a pressing practical problem. We introduce a matching model for short reads that can, besides mismatches, also cope with indels. It addresses different error models. For example, it can handle the problem of leading and trailing contaminations caused by primers and poly-A tails in transcriptomics or the length-dependent increase of error rates. In these contexts, it thus simplifies the tedious and error-prone trimming step. For efficient searches, our method utilizes index structures in the form of enhanced suffix arrays. In a comparison with current methods for short read mapping, the presented approach shows significantly increased performance not only for 454 reads, but also for Illumina reads. Our approach is implemented in the software segemehl available at http://www.bioinf.uni-leipzig.de/Software/segemehl/.

Subfields: Molecular Biology

View Paper: https://www.semanticscholar.org/paper/5a11c02053c5a7e8641a32bd81b8b0d7c7fc3b95

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Molecular Biology

Citations in the corpus

A genome-wide survey of sRNAs in the symbiotic nitrogen-fixing alpha-proteobacterium Sinorhizobium meliloti (2010, methodology): “meliloti genome was performed with the SEGEMEHL software [78] using the following parameters: extension penalty = 2, differences = 1, accuracy = 90.”
Accuracy and quality assessment of 454 GS-FLX Titanium pyrosequencing (2011, background): “tions and deletions of single bases occur less frequently than mismatches [13,14].”
Assembly Algorithms for Next-Generation Sequencing Data (2010, unknown): “Published software includes SOAP [68,69], MAQ [70], Bowtie [71], RMAP [72], CloudBurst [73], SHRiMP [74], RazerS [75], PerM[76], segemehl [77], GenomeMapper [78], and BOAT [79].”
Global mapping of transcription start sites and promoter motifs in the symbiotic α-proteobacterium Sinorhizobium meliloti 1021 (2013, unknown): “Sequencing reads from the cDNA library were processed and mapped to the S. meliloti 1021 genome using segemehl [96].”
The bioinformatics toolbox for circRNA discovery and analysis (2020, methodology): “MapSplice [48] and segemehl [40, 41] have been developed as split alignment tools, and the circRNA detection function is a new feature supported in the latest version.”
Sequence-specific error profile of Illumina sequencers (2011, background): “(26) reported that the Illumina sequencers result in more substitution-type miscalls than indeltype miscalls, while the Roche/454 sequencers result in more indel-type miscalls than substitution-type miscalls.”
ViennaNGS: A toolbox for building efficient next- generation sequencing analysis pipelines (2014, methodology): “We have successfully applied ViennaNGS components in the context of different genomics assays (Antic et al., 2014; Sedlyarov et al., 2014) in combination with the short read aligner segemehl (Hoffmann et al., 2009, 2014).”
MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping (2013, background): “Major Burrows-Wheeler transform (BWT) based aligners include BWA (Li and Durbin 2009), Bowtie (Langmead 2010; Langmead and Salzberg 2012), segemehl (Hoffmann et al. 2009), and SOAP2 (Ruiqiang Li et al. 2009).”
Shining a Light on Dark Sequencing: Characterising Errors in Ion Torrent PGM Data (2013, unknown): “2 [20], an InDel tolerant short-read aligner.”
starBase: a database for exploring microRNA–mRNA interaction maps from Argonaute CLIP-Seq and Degradome-Seq data (2010, methodology): “DegradomeSearch web-server aligned miRNA to extended clusters using segemehl (version 0.093) (32).”