To use all functions of this page, please activate cookies in your browser.

my.bionity.com

With an accout for my.bionity.com you can always see everything at a glance – and you can configure your own website and individual newsletter.

- My watch list
- My saved searches
- My saved topics
- My newsletter

## Needleman-Wunsch algorithmThe The Needleman–Wunsch algorithm is an example of dynamic programming, and was the first application of dynamic programming to biological sequence comparison. Scores for aligned characters are specified by a similarity matrix. Here, For example, if the similarity matrix was
then the alignment: AGACTAGTTAC CGA---GACGT with a gap penalty of -5, would have the following score... To find the alignment with the highest score, a two-dimensional array (or matrix) is allocated. This matrix is often called the F matrix, and its (i,j)th entry is often denoted As the algorithm progresses, the Basis: The pseudo-code for the algorithm to compute the F matrix therefore looks like this (array and sequence indexes start at 0): for i=0 to length(A)-1 F(i,0) <- d*i for j=0 to length(B)-1 F(0,j) <- d*j for i=1 to length(A) for j = 1 to length(B) { Choice1 <- F(i-1,j-1) + S(A(i), B(j)) Choice2 <- F(i-1, j) + d Choice3 <- F(i, j-1) + d F(i,j) <- max(Choice1, Choice2, Choice3) } Once the F matrix is computed, note that the bottom right hand corner of the matrix is the maximum score for any alignments. To compute which alignment actually gives this score, you can start from the bottom right cell, and compare the value with the three possible sources(Choice1, Choice2, and Choice3 above) to see which it came from. If Choice1, then A(i) and B(i) are aligned, if Choice2, then A(i) is aligned with a gap, and if Choice3, then B(i) is aligned with a gap. AlignmentA <- "" AlignmentB <- "" i <- length(A) j <- length(B) while (i > 0 AND j > 0) { Score <- F(i,j) ScoreDiag <- F(i - 1, j - 1) ScoreUp <- F(i, j - 1) ScoreLeft <- F(i - 1, j) if (Score == ScoreDiag + S(A(i-1), B(j-1))) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- B(j-1) + AlignmentB i <- i - 1 j <- j - 1 } else if (Score == ScoreLeft + d) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- "-" + AlignmentB i <- i - 1 } otherwise (Score == ScoreUp + d) { AlignmentA <- "-" + AlignmentA AlignmentB <- B(j-1) + AlignmentB j <- j - 1 } } while (i > 0) { AlignmentA <- A(i-1) + AlignmentA AlignmentB <- "-" + AlignmentB i <- i - 1 } while (j > 0) { AlignmentA <- "-" + AlignmentA AlignmentB <- B(j-1) + AlignmentB j <- j - 1 } ## See also- Smith-Waterman algorithm
- BLAST
- Levenshtein distance
- Dynamic time warping
Categories: Bioinformatics | Computational phylogenetics |
|||||||||||||||||||||||||

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Needleman-Wunsch_algorithm". A list of authors is available in Wikipedia. |