title: Mapping reads on a genomic sequence: an algorithmic overview and a practical comparative analysis.
abstract: Mapping short reads against a reference genome is classically the first step of many next-generation sequencing data analyses, and it should be as accurate as possible. Because of the large number of reads to handle, numerous sophisticated algorithms have been developped in the last 3 years to tackle this problem. In this article, we first review the underlying algorithms used in most of the existing mapping tools, and then we compare the performance of nine of these tools on a well controled benchmark built for this purpose. We built a set of reads that exist in single or multiple copies in a reference genome and for which there is no mismatch, and a set of reads with three mismatches. We considered as reference genome both the human genome and a concatenation of all complete bacterial genomes. On each dataset, we quantified the capacity of the different tools to retrieve all the occurrences of the reads in the reference genome. Special attention was paid to reads uniquely reported and to reads with multiple hits.
authors.affiliation: INRA, UR1077 Unité Mathématique Informatique et Génome, Jouy-en-Josas, France. Sophie.Schbath@jouy.inra.fr
authors.forename: Sophie
authors.initials: S
authors.lastname: Schbath
authors.forename: Véronique
authors.initials: V
authors.lastname: Martin
authors.forename: Matthias
authors.initials: M
authors.lastname: Zytnicki
authors.forename: Julien
authors.initials: J
authors.lastname: Fayolle
authors.forename: Valentin
authors.initials: V
authors.lastname: Loux
authors.forename: Jean-François
authors.initials: JF
authors.lastname: Gibrat
mesh_terms: D000465:Algorithms; D001419:Bacteria / Q000235:genetics*; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods* / Q000706:statistics & numerical data; D016680:Genome, Bacterial; D015894:Genome, Human; D023281:Genomics; D006801:Humans; D008969:Molecular Sequence Data; D016415:Sequence Alignment; D017422:Sequence Analysis, DNA / Q000379:methods* / Q000706:statistics & numerical data; D012984:Software