Biology Reference
In-Depth Information
Chapter 1
Dynamic Programming
¨ . Ufuk Nalbanto ˘ lu
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 meaning-
ful 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 pair-
wise 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 align-
ment problems. Algorithmic improvements offering quadratic-time and linear-space programs and approx-
imate solutions with space-reduction and seeding heuristics are discussed. We finally introduce the
application of these techniques on multiple sequence alignment briefly.
Key words Dynamic programming, Needleman-Wunsch algorithm, Smith-Waterman algorithm,
Affine gap penalties, Hirschberg's algorithm, Banded dynamic programming, Bounded dynamic
programming, Seeding
1
Introduction
Biological sequence alignment is undoubtedly one of the major
techniques used in several areas of computational biology. Several
tasks such as inferring phylogenetic relationships, homology search
of functional elements, classification of proteins, designing detec-
tion markers require an extensive amount of sequence alignments.
This volume can change between the multiple alignment of a
few gene-size sequences to an extensive molecular database search
of large queries. Considering the fast rate of increase in the database
volumes and the number of sequences to be aligned, we can have
an idea about the fact that the sequence alignment programs
employed are quite successful in handling the problem. Here we
introduce the basic methodology behind the success of the align-
ment programs, namely dynamic programming.
Search WWH ::




Custom Search