FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis

Shanshan Ren; Vlad-Mihai Sima; Zaid Al-Ars

doi:10.1109/BIBM.2015.7359892

FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis

Shanshan Ren, Vlad-Mihai Sima, Zaid Al-Ars

Computer Engineering

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

18 Citations (Scopus)

Abstract

Many DNA sequence analysis tools have been developed to turn the massive raw DNA sequencing data generated by NGS (Next Generation Sequencing) platforms into biologically meaningful information. The pair-HMMs forward algorithm is widely used to calculate the overall alignment probability needed by a number of DNA analysis tools. In this paper, we propose a novel systolic array design to accelerate the pair-HMMs forward algorithm on FPGAs. A number of architectural features have been implemented to improve the performance of the design, such as early exit points to increase the utilization of the array for small sequence sizes, as well as on-chip buffering to enable the processing of long sequences effectively. We present an implementation of the design on the Convey supercomputing platform. Experimental results show that the FPGA implementation of the pair-HMMs forward algorithm is up to 67x faster, compared to software-only execution.

Original language	English
Title of host publication	Proceedings - 2015 IEEE International Conference on Bioinformatics and Biomedicine
Editors	Jun (Luke) Huan, Satoru Miyano, Amarda Shehu
Place of Publication	Danvers, MA
Publisher	IEEE
Pages	1465-1470
Number of pages	6
ISBN (Electronic)	978-1-4673-6799-8
ISBN (Print)	978-1-4673-6798-1
DOIs	https://doi.org/10.1109/BIBM.2015.7359892
Publication status	Published - 2015
Event	2015 IEEE International Conference on Bioinformatics and Biomedicine, BIBM - Duration: 9 Nov 2015 → 12 Nov 2015

Conference

Conference	2015 IEEE International Conference on Bioinformatics and Biomedicine, BIBM
Abbreviated title	BIBM
Period	9/11/15 → 12/11/15

Keywords

hardware acceleration
NGS
FPGA
pair-HMMs …

Access to Document

10.1109/BIBM.2015.7359892

Cite this

@inproceedings{0a3499fc075748668a428b6a87a0366f,

title = "FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis",

abstract = "Many DNA sequence analysis tools have been developed to turn the massive raw DNA sequencing data generated by NGS (Next Generation Sequencing) platforms into biologically meaningful information. The pair-HMMs forward algorithm is widely used to calculate the overall alignment probability needed by a number of DNA analysis tools. In this paper, we propose a novel systolic array design to accelerate the pair-HMMs forward algorithm on FPGAs. A number of architectural features have been implemented to improve the performance of the design, such as early exit points to increase the utilization of the array for small sequence sizes, as well as on-chip buffering to enable the processing of long sequences effectively. We present an implementation of the design on the Convey supercomputing platform. Experimental results show that the FPGA implementation of the pair-HMMs forward algorithm is up to 67x faster, compared to software-only execution.",

keywords = "hardware acceleration, NGS, FPGA, pair-HMMs …",

author = "Shanshan Ren and Vlad-Mihai Sima and Zaid Al-Ars",

year = "2015",

doi = "10.1109/BIBM.2015.7359892",

language = "English",

isbn = "978-1-4673-6798-1",

pages = "1465--1470",

editor = "Huan, {Jun (Luke)} and Satoru Miyano and Amarda Shehu",

booktitle = "Proceedings - 2015 IEEE International Conference on Bioinformatics and Biomedicine",

publisher = "IEEE",

address = "United States",

note = "2015 IEEE International Conference on Bioinformatics and Biomedicine, BIBM , BIBM ; Conference date: 09-11-2015 Through 12-11-2015",

}

Ren, S, Sima, V-M & Al-Ars, Z 2015, FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis. in J Huan, S Miyano & A Shehu (eds), Proceedings - 2015 IEEE International Conference on Bioinformatics and Biomedicine. IEEE, Danvers, MA, pp. 1465-1470, 2015 IEEE International Conference on Bioinformatics and Biomedicine, BIBM , 9/11/15. https://doi.org/10.1109/BIBM.2015.7359892

FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis. / Ren, Shanshan; Sima, Vlad-Mihai; Al-Ars, Zaid.
Proceedings - 2015 IEEE International Conference on Bioinformatics and Biomedicine. ed. / Jun (Luke) Huan; Satoru Miyano; Amarda Shehu. Danvers, MA: IEEE, 2015. p. 1465-1470.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

T1 - FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis

AU - Ren, Shanshan

AU - Sima, Vlad-Mihai

AU - Al-Ars, Zaid

PY - 2015

Y1 - 2015

N2 - Many DNA sequence analysis tools have been developed to turn the massive raw DNA sequencing data generated by NGS (Next Generation Sequencing) platforms into biologically meaningful information. The pair-HMMs forward algorithm is widely used to calculate the overall alignment probability needed by a number of DNA analysis tools. In this paper, we propose a novel systolic array design to accelerate the pair-HMMs forward algorithm on FPGAs. A number of architectural features have been implemented to improve the performance of the design, such as early exit points to increase the utilization of the array for small sequence sizes, as well as on-chip buffering to enable the processing of long sequences effectively. We present an implementation of the design on the Convey supercomputing platform. Experimental results show that the FPGA implementation of the pair-HMMs forward algorithm is up to 67x faster, compared to software-only execution.

AB - Many DNA sequence analysis tools have been developed to turn the massive raw DNA sequencing data generated by NGS (Next Generation Sequencing) platforms into biologically meaningful information. The pair-HMMs forward algorithm is widely used to calculate the overall alignment probability needed by a number of DNA analysis tools. In this paper, we propose a novel systolic array design to accelerate the pair-HMMs forward algorithm on FPGAs. A number of architectural features have been implemented to improve the performance of the design, such as early exit points to increase the utilization of the array for small sequence sizes, as well as on-chip buffering to enable the processing of long sequences effectively. We present an implementation of the design on the Convey supercomputing platform. Experimental results show that the FPGA implementation of the pair-HMMs forward algorithm is up to 67x faster, compared to software-only execution.

KW - hardware acceleration

KW - NGS

KW - FPGA

KW - pair-HMMs …

UR - http://resolver.tudelft.nl/uuid://0a3499fc-0757-4866-8a42-8b6a87a0366f

U2 - 10.1109/BIBM.2015.7359892

DO - 10.1109/BIBM.2015.7359892

M3 - Conference contribution

SN - 978-1-4673-6798-1

SP - 1465

EP - 1470

BT - Proceedings - 2015 IEEE International Conference on Bioinformatics and Biomedicine

A2 - Huan, Jun (Luke)

A2 - Miyano, Satoru

A2 - Shehu, Amarda

PB - IEEE

CY - Danvers, MA

T2 - 2015 IEEE International Conference on Bioinformatics and Biomedicine, BIBM

Y2 - 9 November 2015 through 12 November 2015

ER -

FPGA acceleration of the pair-HMMs forward algorithm for DNA sequence analysis

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this