The Original Needleman-Wunsch Algorithm,
Which Can be Easily Adapted to Structural Alignment

Mark Gerstein@yale.edu, 1998

### Lecture Notes

Basic Sequence Alignment [html-with-frames] [pdf]
Scoring and Assessing Significance [html-with-frames] [pdf]
Mathematical Background on Probability [html-with-frames] [pdf]
Structural Alignment [html-with-frames] [pdf]
Mathematical Background on Rotations [html-with-frames] [pdf

Bioinformatics Course Home [http://bioinfo.mbb.yale.edu/course ]

### References

This is intended as a supplement to the method described in:

M Gerstein & M Levitt (1996). "Using Iterative Dynamic Programming to Obtain Accurate Pairwise and Multiple Alignments of Protein Structures," in Proceedings of the Fourth International Conference on Intelligent Systems in Molecular Biology, 59-67 (Menlo Park, CA, AAAI Press, June 12-15). [full text available from: http://hyper.stanford.edu/~mbg/Align/ismb96]

Needleman, S. B. and Wunsch, C. D. (1971). "A general method applicable to the search for similarities in the amino acid sequence of two proteins." J. Mol. Biol. 48: 443-453

### The Tutorial...

 Step 1 -- Make a Dot Plot (Similarity Matrix) Put 1's where characters are identical. A B C N Y R Q C L C R P M A 1 Y 1 C 1 1 1 Y 1 N 1 R 1 1 C 1 1 1 K C 1 1 1 R 1 1 B 1 P 1
Step 2 -- Start Computing the Sum Matrix

new_value_cell(R,C) <=

cell(R,C) { Old value, either 1 or 0 }

+ Max[

cell (R+1, C+1), { Diagonally Down, no gaps }

cells(R+1, C+2 to C_max),{ Down a row, making col. gap }

cells(R+2 to R_max, C+2) { Down a col., making row gap }

]

Use this Excel Formula:

"=IF(M28="",0,1)+MAX(N45,N46:N47,O45:Y45)"

Good Excel Formulas Inserted in Step 4 (below)

 A B C N Y R Q C L C R P M A 1 Y 1 C 1 1 1 Y 1 N 1 R 1 1 C 1 1 1 K C 1 1 1 R 1 2 0 0 B 1 2 1 1 1 1 1 1 1 1 1 0 0 P 0 0 0 0 0 0 0 0 0 0 0 1 0
Step 3 -- Keep Going

 A B C N Y R Q C L C R P M A 1 Y 1 C 1 1 1 Y 1 N 1 R 5 4 3 3 2 2 0 0 C 3 3 4 3 3 3 3 4 3 3 1 0 0 K 3 3 3 3 3 3 3 3 3 2 1 0 0 C 2 2 3 2 2 2 2 3 2 3 1 0 0 R 2 1 1 1 1 2 1 1 1 1 2 0 0 B 1 2 1 1 1 1 1 1 1 1 1 0 0 P 0 0 0 0 0 0 0 0 0 0 0 1 0
Step 4 -- Sum Matrix All Done

 Alignment Score is 8 matches. A B C N Y R Q C L C R P M A 8 7 6 6 5 4 4 3 3 2 1 0 0 Y 7 7 6 6 6 4 4 3 3 2 1 0 0 C 6 6 7 6 5 4 4 4 3 3 1 0 0 Y 6 6 6 5 6 4 4 3 3 2 1 0 0 N 5 5 5 6 5 4 4 3 3 2 1 0 0 R 4 4 4 4 4 5 4 3 3 2 2 0 0 C 3 3 4 3 3 3 3 4 3 3 1 0 0 K 3 3 3 3 3 3 3 3 3 2 1 0 0 C 2 2 3 2 2 2 2 3 2 3 1 0 0 R 2 1 1 1 1 2 1 1 1 1 2 0 0 B 1 2 1 1 1 1 1 1 1 1 1 0 0 P 0 0 0 0 0 0 0 0 0 0 0 1 0
Step 5 -- Traceback

A B C N Y - R Q C L C R - P M

A Y C - Y N R - C K C R B P -

 A B C N Y R Q C L C R P M A 8 7 6 6 5 4 4 3 3 2 1 0 0 Y 7 7 6 6 6 4 4 3 3 2 1 0 0 C 6 6 7 6 5 4 4 4 3 3 1 0 0 Y 6 6 6 5 6 4 4 3 3 2 1 0 0 N 5 5 5 6 5 4 4 3 3 2 1 0 0 R 4 4 4 4 4 5 4 3 3 2 2 0 0 C 3 3 4 3 3 3 3 4 3 3 1 0 0 K 3 3 3 3 3 3 3 3 3 2 1 0 0 C 2 2 3 2 2 2 2 3 2 3 1 0 0 R 2 1 1 1 1 2 1 1 1 1 2 0 0 B 1 2 1 1 1 1 1 1 1 1 1 0 0 P 0 0 0 0 0 0 0 0 0 0 0 1 0
Step 6 -- Alternate Paths

A B C - N Y R Q C L C R - P M

A Y C Y N - R - C K C R B P -

 A B C N Y R Q C L C R P M A 8 7 6 6 5 4 4 3 3 2 1 0 0 Y 7 7 6 6 6 4 4 3 3 2 1 0 0 C 6 6 7 6 5 4 4 4 3 3 1 0 0 Y 6 6 6 5 6 4 4 3 3 2 1 0 0 N 5 5 5 6 5 4 4 3 3 2 1 0 0 R 4 4 4 4 4 5 4 3 3 2 2 0 0 C 3 3 4 3 3 3 3 4 3 3 1 0 0 K 3 3 3 3 3 3 3 3 3 2 1 0 0 C 2 2 3 2 2 2 2 3 2 3 1 0 0 R 2 1 1 1 1 2 1 1 1 1 2 0 0 B 1 2 1 1 1 1 1 1 1 1 1 0 0 P 0 0 0 0 0 0 0 0 0 0 0 1 0