Giegerich R
Faculty of Technology, Bielefeld University, 33615 Bielefeld, Germany.
Bioinformatics. 2000 Aug;16(8):665-77. doi: 10.1093/bioinformatics/16.8.665.
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.
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.
动态规划可能是生物信息学中最流行的编程方法。序列比较、基因识别、RNA结构预测以及数百个其他问题都通过动态规划的新变体得以解决。目前，开发一个成功的动态规划算法需要经验、天赋和运气。构成动态规划算法的典型矩阵递归关系构建起来错综复杂，且难以可靠地实现。不存在通用的、与问题无关的指导方法。
本文介绍了一种为生物序列分析问题构建动态规划解决方案的系统方法。通过将算法概念性地拆分为识别阶段和评估阶段，算法开发得到了极大简化，并且可以系统地推导出正确的递归关系。无需额外的努力，该方法就能生成一个用函数式编程语言表示的早期可执行原型。该方法具有相当广泛的适用性，并且在减少编程工作量的同时，不会导致最终程序效率方面的开销。
