Dynamic Programming

Dynamic Programming

This page is a placeholder, or under current development; it is here principally to establish the logical framework of the site. The material on this page is correct, but incomplete.

Dynamic programming and optimal sequence alignment.

 

Introductory reading

Giegerich (2000) A systematic approach to dynamic programming in bioinformatics. Bioinformatics 16:665-77. (pmid: 11099253)

[ PubMed ] [ DOI ] 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.

 

Contents

Dynamic Programing - Presentation by Zahra Ebrahim-Zadeh, BCB410 - 2011

 

Exercises

Exercises - by Zahra Ebrahim-Zadeh, BCB410 - 2011

 

Further reading and resources

Nalbantoğlu (2014) Dynamic programming. Methods Mol Biol 1079:3-27. (pmid: 24170392)

[ PubMed ] [ DOI ] Abstract Independent scoring of the aligned sections to determine the quality of biological sequence alignments enables recursive definitions of the overall alignment score. This property is not only biologically meaningful but it also provides the opportunity to find the optimal alignments using dynamic programming-based algorithms. Dynamic programming is an efficient problem solving technique for a class of problems that can be solved by dividing into overlapping subproblems. Pairwise sequence alignment techniques such as Needleman-Wunsch and Smith-Waterman algorithms are applications of dynamic programming on pairwise sequence alignment problems. These algorithms offer polynomial time and space solutions. In this chapter, we introduce the basic dynamic programming solutions for global, semi-global, and local alignment problems. Algorithmic improvements offering quadratic-time and linear-space programs and approximate solutions with space-reduction and seeding heuristics are discussed. We finally introduce the application of these techniques on multiple sequence alignment briefly.

Needleman & Wunsch (1970) A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol 48:443-53. (pmid: 5420325)

[ PubMed ] [ DOI ]

Smith & Waterman (1981) Identification of common molecular subsequences. J Mol Biol 147:195-7. (pmid: 7265238)

[ PubMed ] [ DOI ]