View on Pubmed.gov 11099253 | View on doi.org 10.1093/bioinfo...
A systematic approach to dynamic programming in bioinformatics.
- Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany. robert@techfak.uni-bielefeld.de
Abstract
MOTIVATION
Dynamic programming is probably the most popular programming method in bioinformatics. Sequence comparison, gene recognition, RNA structure prediction and hundreds of other problems are solved by ever new variants of dynamic programming. Currently, the development of a successful dynamic programming algorithm is a matter of experience, talent and luck. The typical matrix recurrence relations that make up a dynamic programming algorithm are intricate to construct, and difficult to implement reliably. No general problem independent guidance is available.
RESULTS
This article introduces a systematic method for constructing dynamic programming solutions to problems in biosequence analysis. By a conceptual splitting of the algorithm into a recognition and an evaluation phase, algorithm development is simplified considerably, and correct recurrences can be derived systematically. Without additional effort, the method produces an early, executable prototype expressed in a functional programming language. The method is quite generally applicable, and, while programming effort decreases, no overhead in terms of ultimate program efficiency is incurred.
References
Cited by 69 citations (total)
Journal Article Research Support, Non-U.S. Gov't
160-fold acceleration of the Smith-Waterman algorithm using a field programmable gate array (FPGA).
Electronic publication date July 18, 2007
Isaac T S Li [...] Kevin Truong et al.
BACKGROUND
To infer homology and subsequently gene function, the Smith-Waterman (SW) algorithm is used to find the optimal local alignment between...
Journal Article Research Support, N.I.H., Extramural Research Support, Non-U.S. Gov't
Transmembrane protein alignment and fold recognition based on predicted topology.
Electronic publication date March 4, 2014
Han Wang [...] Dong Xu et al.
BACKGROUND
Although Transmembrane Proteins (TMPs) are highly important in various biological processes and pharmaceutical developments, general prediction of TMP structures is...
Conflict of interest statement
MeSH
- •
- •
Specialties
- •
- •