---

Pairwise Alignment

The alignment of two sequences (DNA or protein) is a relatively straightforward computational problem. The best solution seems to be an approach called Dynamic Programming.

For those of you who are mathematically inclined and want to understand how dynamic programming works there is an excellent textbook on the web called Pairwise Sequence Alignment by Robert Giegerich and David Wheeler at the Global Network Academy, Virtual School of Natural Sciences.

This is one chapter of the VSNS Biocomputing Hypertext Coursebook, which contains several other interesting tutorials.

---

All I'm going to say about how it works is this:

Dynamic Programming is a very general programming technique. 
It is applicable when a large search space can be structured 
into a succession of stages, such that: 
     -the initial stage contains trivial solutions to sub-problems           
     -each partial solution in a later stage can be calculated by 
     	recurring a fixed number of partial solutions in an earlier stage
     -the final stage contains the overall solution 

Here are some figures that summarize how it works.

A certain similarity to the dot plot is obvious.

---

Global vs. Local Alignments

There are two different methods of applying Dynamic Programming to the alignment of two sequences.

The complete sequences can be globally aligned with each other. The GCG program GAP implements the Needleman and Wunsch Global alignment algorithm.

Global algorithms are often not effective for highly diverged sequences and do not reflect the biological reality that two sequences may only share limited regions of conserved sequence. Sometimes two sequences may be derived from ancient recombination events where only a single functional domain is shared.

Local alignment finds the region (or regions) of highest similarity between two sequences. The GCG program BESTFIT implements the Smith and Waterman Local alignment algorithm.

These two programs will often give very different results for the alignment of two sequences.

---

---

Using Computers for Molecular Biology
Stuart M. Brown, Ph.D., RCR, NYU Medical Center

Comments to: browns02@mcrcr.med.nyu.edu