Mapping Reads on a Genomic Sequence: An Algorithmic Overview and a Practical Comparative Analysis
Open Access
- 16 April 2012
- journal article
- research article
- Published by SAGE Publications in Journal of Computational Biology
- Vol. 19 (6) , 796-813
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.Keywords
This publication has 19 references indexed in Scilit:
- SHRiMP2: Sensitive yet Practical Short Read MappingBioinformatics, 2011
- BFAST: An Alignment Tool for Large Scale Genome ResequencingPLOS ONE, 2009
- PerM: efficient mapping of short sequencing reads with periodic full sensitive spaced seedsBioinformatics, 2009
- SOAP2: an improved ultrafast tool for short read alignmentBioinformatics, 2009
- Fast and accurate short read alignment with Burrows–Wheeler transformBioinformatics, 2009
- Ultrafast and memory-efficient alignment of short DNA sequences to the human genomeGenome Biology, 2009
- SeqMap: mapping massive amount of oligonucleotides to the genomeBioinformatics, 2008
- SOAP: short oligonucleotide alignment programBioinformatics, 2008
- Integr8 and Genome Reviews: integrated views of complete genomes and proteomesNucleic Acids Research, 2004
- Opportunistic data structures with applications2002