Skip to main content
padlock icon - secure page this page is secure

Efficient and Error-Tolerant Sequencing Read Mapping

Buy Article:

$68.00 + tax (Refund Policy)

Most efficient read mappers build a Ferragina-Manzini index of a genome sequence and then process reads against it. In order to handle differences between reads and corresponding genome fragments, approximate read occurrences are searched in the index. This technique is particularly efficient for mapping reads of length ∼30bp with up to 2-3 errors, as first massive sequencers required.

However, within the last few years, in most popular sequencing technologies read length increased to 75 − 200bp. Since the number of required index queries is exponential with respect to the number of errors, it is hard to maintain the allowed error rate within this method.

We propose a new approach that overcomes this problem. The main idea is to use the Ferragina-Manzini index to filter potential approximate read occurrences. Filtering is based on the intermediate partitioning concept, i.e. reads are split into parts, which are searched in index with reduced number of errors.

We implemented this method in Bmap program. Our experiments show that Bmap outperforms current methods in efficiency without sacrificing mapping accuracy.
No References
No Citations
No Supplementary Data
No Article Media
No Metrics

Keywords: Approximate string matching; ferragina-manzini index; intermediate partitioning; next generation sequencing; read mapping; succinct suffix array

Document Type: Research Article

Publication date: April 1, 2015

More about this publication?
  • Current Bioinformatics aims to publish all the latest and outstanding developments in bioinformatics. Each issue contains a series of timely, in-depth reviews written by leaders in the field, covering a wide range of the integration of biology with computer and information science.

    The journal focuses on reviews on advances in computational molecular/structural biology, encompassing areas such as computing in biomedicine and genomics, computational proteomics and systems biology, and metabolic pathway engineering. Developments in these fields have direct implications on key issues related to health care, medicine, genetic disorders, development of agricultural products, renewable energy, environmental protection, etc.

    Current Bioinformatics is an essential journal for all academic and industrial researchers who want expert knowledge on all major advances in bioinformatics.
  • Editorial Board
  • Information for Authors
  • Subscribe to this Title
  • Ingenta Connect is not responsible for the content or availability of external websites
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content
Cookie Policy
Cookie Policy
Ingenta Connect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more