Related Experiment Video
Updated: Jun 25, 2026
10:44
Single Cell Multiplex Reverse Transcription Polymerase Chain Reaction After Patch-clamp
Published on: June 20, 2018
High speed biological sequence analysis with hidden Markov models on reconfigurable platforms
Timothy F Oliver1, Bertil Schmidt, Yanto Jakop
1School of Computer Engineering, Nanyang Technological University, Singapore 639798, Singapore. tim.oliver@pmail.ntu.edu.sg
Summary
Molecular biologists can accelerate database scanning using hidden Markov models (HMMs) with field-programmable gate arrays (FPGAs). This approach significantly reduces computational runtime for detecting protein sequence similarities.
Area of Science:
- Bioinformatics
- Computational Biology
- Computer Architecture
Background:
- Hidden Markov models (HMMs) are essential for describing biological sequence families in molecular biology.
- HMMs enable sensitive and selective database scanning for detecting functional similarities in new protein sequences.
- Current dynamic programming algorithms for HMM scanning face significant runtime challenges due to rapidly growing databases.
Purpose of the Study:
- To investigate the application of reconfigurable architectures for parallelizing dynamic programming calculations in HMM database scanning.
- To demonstrate runtime savings achievable by implementing HMM scanning on field-programmable gate arrays (FPGAs).
Main Methods:
- Fine-grained parallelization of dynamic programming algorithms using reconfigurable architectures.
- Implementation of the parallelized algorithm on a standard off-the-shelf field-programmable gate array (FPGA).
- Benchmarking scan times for HMM database scanning on the FPGA platform.
Main Results:
- Significant runtime savings were achieved for HMM database scanning.
- Reconfigurable architectures enable efficient fine-grained parallelization of the dynamic programming computation.
- FPGA implementation offers a practical solution to accelerate HMM-based sequence analysis.
Conclusions:
- Reconfigurable architectures, specifically FPGAs, provide an effective hardware acceleration for HMM database scanning.
- This approach addresses the growing computational demands posed by large biological sequence databases.
- The fine-grained parallelization strategy leads to substantial improvements in scan time efficiency.
Related Concept Videos
03:00Next-generation Sequencing
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
03:21RNA-seq
RNA sequencing, or RNA-Seq, is a high-throughput sequencing technology used to study the transcriptome of a cell. Transcriptomics helps to interpret the functional elements of a genome and identify the molecular constituents of an organism. Additionally, it also helps in understanding the development of an organism and the occurrence of diseases.
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...
Before the discovery of RNA-seq, microarray-based methods and Sanger sequencing were used for transcriptome analysis. However, while microarray-based...