A hybrid short read mapping accelerator

Publication type:
Journal article
Metadata:
Autoren
Autoren-URL
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=fis-test-1&SrcAuth=WosAPI&KeyUT=WOS:000315926400001&DestLinkType=FullRecord&DestApp=WOS_CPL
DOI
10.1186/1471-2105-14-67
Externe Identifier
  • Clarivate Analytics Document Solution ID: 103OC
  • PubMed Identifier: 23441908
ISSN
1471-2105
Zeitschrift
BMC BIOINFORMATICS
Artikelnummer
ARTN 67
Datum der Veröffentlichung
2013
Status
Published
Titel
A hybrid short read mapping accelerator
Sub types
  • Article
Ausgabe der Zeitschrift
14

Data source: Web of Science (Lite)

Other metadata sources:
Autoren
DOI
10.1186/1471-2105-14-67
eISSN
1471-2105
Ausgabe der Veröffentlichung
1
Zeitschrift
BMC Bioinformatics
Sprache
en
Artikelnummer
67
Online publication date
2013
Datum der Veröffentlichung
2013
Status
Published
Herausgeber
Springer Science and Business Media LLC
Herausgeber URL
http://dx.doi.org/10.1186/1471-2105-14-67
Datum der Datenerfassung
2019
Titel
A hybrid short read mapping accelerator
Ausgabe der Zeitschrift
14

Data source: Crossref

Abstract
<h4>Background</h4>The rapid growth of short read datasets poses a new challenge to the short read mapping problem in terms of sensitivity and execution speed. Existing methods often use a restrictive error model for computing the alignments to improve speed, whereas more flexible error models are generally too slow for large-scale applications. A number of short read mapping software tools have been proposed. However, designs based on hardware are relatively rare. Field programmable gate arrays (FPGAs) have been successfully used in a number of specific application areas, such as the DSP and communications domains due to their outstanding parallel data processing capabilities, making them a competitive platform to solve problems that are "inherently parallel".<h4>Results</h4>We present a hybrid system for short read mapping utilizing both FPGA-based hardware and CPU-based software. The computation intensive alignment and the seed generation operations are mapped onto an FPGA. We present a computationally efficient, parallel block-wise alignment structure (Align Core) to approximate the conventional dynamic programming algorithm. The performance is compared to the multi-threaded CPU-based GASSST and BWA software implementations. For single-end alignment, our hybrid system achieves faster processing speed than GASSST (with a similar sensitivity) and BWA (with a higher sensitivity); for pair-end alignment, our design achieves a slightly worse sensitivity than that of BWA but has a higher processing speed.<h4>Conclusions</h4>This paper shows that our hybrid system can effectively accelerate the mapping of short reads to a reference genome based on the seed-and-extend approach. The performance comparison to the GASSST and BWA software implementations under different conditions shows that our hybrid design achieves a high degree of sensitivity and requires less overall execution time with only modest FPGA resource utilization. Our hybrid system design also shows that the performance bottleneck for the short read mapping problem can be changed from the alignment stage to the seed generation stage, which provides an additional requirement for the future development of short read aligners.
Addresses
  • School of Computer Engineering, Nanyang Technological University, Singapore, Singapore. chen0511@e.ntu.edu.sg
Autoren
DOI
10.1186/1471-2105-14-67
eISSN
1471-2105
Externe Identifier
  • PubMed Identifier: 23441908
  • PubMed Central ID: PMC3598928
Open access
true
ISSN
1471-2105
Zeitschrift
BMC bioinformatics
Schlüsselwörter
  • Chromosome Mapping
  • Sequence Alignment
  • Sequence Analysis, DNA
  • Genome
  • Algorithms
  • Software
Sprache
eng
Medium
Electronic
Online publication date
2013
Open access status
Open Access
Paginierung
67
Datum der Veröffentlichung
2013
Status
Published
Publisher licence
CC BY
Datum der Datenerfassung
2013
Titel
A hybrid short read mapping accelerator.
Sub types
  • research-article
  • Journal Article
Ausgabe der Zeitschrift
14

Files

https://bmcbioinformatics.biomedcentral.com/counter/pdf/10.1186/1471-2105-14-67 https://www.ncbi.nlm.nih.gov/pmc/articles/pmid/23441908/pdf/?tool=EBI https://europepmc.org/articles/PMC3598928?pdf=render

Data source: Europe PubMed Central

Abstract
BACKGROUND: The rapid growth of short read datasets poses a new challenge to the short read mapping problem in terms of sensitivity and execution speed. Existing methods often use a restrictive error model for computing the alignments to improve speed, whereas more flexible error models are generally too slow for large-scale applications. A number of short read mapping software tools have been proposed. However, designs based on hardware are relatively rare. Field programmable gate arrays (FPGAs) have been successfully used in a number of specific application areas, such as the DSP and communications domains due to their outstanding parallel data processing capabilities, making them a competitive platform to solve problems that are "inherently parallel". RESULTS: We present a hybrid system for short read mapping utilizing both FPGA-based hardware and CPU-based software. The computation intensive alignment and the seed generation operations are mapped onto an FPGA. We present a computationally efficient, parallel block-wise alignment structure (Align Core) to approximate the conventional dynamic programming algorithm. The performance is compared to the multi-threaded CPU-based GASSST and BWA software implementations. For single-end alignment, our hybrid system achieves faster processing speed than GASSST (with a similar sensitivity) and BWA (with a higher sensitivity); for pair-end alignment, our design achieves a slightly worse sensitivity than that of BWA but has a higher processing speed. CONCLUSIONS: This paper shows that our hybrid system can effectively accelerate the mapping of short reads to a reference genome based on the seed-and-extend approach. The performance comparison to the GASSST and BWA software implementations under different conditions shows that our hybrid design achieves a high degree of sensitivity and requires less overall execution time with only modest FPGA resource utilization. Our hybrid system design also shows that the performance bottleneck for the short read mapping problem can be changed from the alignment stage to the seed generation stage, which provides an additional requirement for the future development of short read aligners.
Date of acceptance
2013
Autoren
Autoren-URL
https://www.ncbi.nlm.nih.gov/pubmed/23441908
DOI
10.1186/1471-2105-14-67
eISSN
1471-2105
Externe Identifier
  • PubMed Central ID: PMC3598928
Zeitschrift
BMC Bioinformatics
Schlüsselwörter
  • Algorithms
  • Chromosome Mapping
  • Genome
  • Sequence Alignment
  • Sequence Analysis, DNA
  • Software
Sprache
eng
Country
England
Paginierung
67
PII
1471-2105-14-67
Datum der Veröffentlichung
2013
Status
Published online
Datum, an dem der Datensatz öffentlich gemacht wurde
2013
Titel
A hybrid short read mapping accelerator.
Sub types
  • Journal Article
Ausgabe der Zeitschrift
14

Data source: PubMed

Autoren
Zeitschrift
BMC Bioinform.
Paginierung
67 - 67
Datum der Veröffentlichung
2013
Titel
A hybrid short read mapping accelerator.
Ausgabe der Zeitschrift
14

Data source: DBLP

Beziehungen:
Property of

Tools