Title :
High Speed Biological Sequence Analysis With Hidden Markov Models on Reconfigurable Platforms
Author :
Oliver, Timothy F. ; Schmidt, Bertil ; Jakop, Yanto ; Maskell, Douglas L.
Author_Institution :
Sch. of Comput. Eng., Nanyang Technol. Univ., Singapore, Singapore
Abstract :
Molecular biologists use hidden Markov models (HMMs) as a popular tool to statistically describe biological sequence families. This statistical description can then be used for sensitive and selective database scanning, e.g., new protein sequences are compared with a set of HMMs to detect functional similarities. Efficient dynamic-programming algorithms exist for solving this problem; however, current solutions still require significant scan times. These scan time requirements are likely to become even more severe due to the rapid growth in the size of these databases. This paper shows how reconfigurable architectures can be used to derive an efficient fine-grained parallelization of the dynamic programming calculation. We describe how this technique leads to significant runtime savings for HMM database scanning on a standard off-the-shelf field-programmable gate array (FPGA).
Keywords :
bioinformatics; biological techniques; database management systems; field programmable gate arrays; hidden Markov models; molecular biophysics; HMM database scanning; biological sequence analysis; dynamic programming algorithms; field programmable gate array; hidden Markov models; reconfigurable platforms; selective database scanning; statistical description; Biomedical engineering; Computer architectures; Database; Dynamic programming; Markov models; Parallel processing; Search; Sequences; computer architectures; database; dynamic programming (DP); parallel processing; search; sequences; Algorithms; Computational Biology; Markov Chains; Pattern Recognition, Automated; Sequence Alignment; Sequence Analysis, Protein;
Journal_Title :
Information Technology in Biomedicine, IEEE Transactions on
DOI :
10.1109/TITB.2007.904632