Format

Send to

Choose Destination
Methods Mol Biol. 2014;1079:3-27. doi: 10.1007/978-1-62703-646-7_1.

Dynamic programming.

Author information

1
Department of Electrical Engineering, University of Nebraska-Lincoln, Lincoln, NE, USA.

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.

PMID:
24170392
DOI:
10.1007/978-1-62703-646-7_1
[Indexed for MEDLINE]

Supplemental Content

Full text links

Icon for Springer
Loading ...
Support Center