Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatic Analysis
Sequence Alignment Algorithms
Dynamic Programming Algorithm

The algorithm for global optimal alignment of two sequences, yielding the maximum score, is based on a mathematical method known as dynamic programming.

The primary advantage of this method is that it guarantees a global optimum: the best alignment result for a given set of parameters—substitution matrix and gap penalties—without any approximations.

The main drawback of the method is that many alignments of two given sequences may yield the optimal score, while it is by no means certain that even one of them is biologically meaningful (biologically correct). For example, when comparing the alpha- and beta-chains of chicken Hemoglobin, W. Fitch and T. Smith found 17 alignments, each producing the exact same optimal score, of which only one proved to be correct (using additional information on the Spatial Structure of Proteins). In fact, it turned out that for this task there exist 1,317 alignments that yield a score within 5% of the optimum.

There is another drawback: the time required to align two sequences of lengths n and m is proportional to the size of the edit matrix, that is, proportional to the product m x n. The computational complexity of the algorithm is denoted by O(f). Since n and m are typically of the same order, the algorithm is said to require O(n²) time (or memory). In the field of biological sequence analysis using standard computers (rather than supercomputers), O(n²) algorithms yield satisfactory results, whereas O(n³⁾ algorithms can only be applied to very short sequences.

Thus, the dynamic programming method will be too slow when searching for a match for a query sequence in a full sequence database, and it is even less suited for all-against-all alignments. The database search problem is essentially The problem of matching a sequence of interest against an extremely long sequence whose length equals that of the entire database.

A scheme containing all possible alignments can be constructed as a matrix, similar to the one used for dot plots. The elements of one sequence (NUCLEOTIDES or Amino Acids) index the rows, and the elements of the other sequence index the columns. Any path through the matrix starting at the top-left corner and ending at the bottom-right corner corresponds to a single alignment (see Figure 17). The task is to find the path with the maximum score, and the difficulty lies in the fact that a vast number of such paths must be considered.

To understand the core idea of dynamic programming, let us consider a basic example of "navigating" a 5x5 graph from the starting point (0,0) to the end point (4,4) (Figure 47(a)).

There are 6 paths from the starting point (0,0) to point "A" (Figure 47(b)). By Symmetry, There are also 6 paths from point "A" to the end point (4,4), and the total number of paths from start to finish passing through point "A" is 36.

Suppose further that we have assigned costs to individual steps. The question is: do we need to check all 36 paths to find the optimal one that passes from start to finish through point "A"?

It turns out we do not, because the choice of the optimal path from point "A" to the end does not depend on the choice of the path from the start to point "A".

Class="center">

Figure 47 - Model graph: a - diagram; b - paths from point (0,0) to point A

If we determine the optimal path among the 6 leading from the starting point to point "A", as well as the optimal path among those from "A" to the end, then the optimal path from start to finish passing through "A" will be defined as the optimal path from start to "A" followed by the optimal path from "A" to the end point.

In this case, we only need to consider no more than 12 paths passing through point "A"—the 6 paths from point (0,0) to "A" extended by the single most optimal path from "A" to the end; plus another 6 paths from "A" to the end extending the single optimal path from the start to "A".

This is the advantage of the dynamic programming method: the problem is systematically broken down into progressively smaller subproblems (Figure 48), thereby reducing the volume of necessary computations.

The algorithm for global alignment of two Biological Sequences using dynamic programming was first proposed by Saul B. Needleman and Christian D. Wunsch.

To identify local matches, a similar algorithm was first employed by Temple F. Smith and Michael S. Waterman.

Figure 48 - Decomposition of the optimal alignment problem into subproblems