[BiO BB] More Smith-Waterman internals. Gaps extensions this time.

[Iddo Friedberg]

On Sun, 19 Feb 2006, Theodore H. Smith wrote:

> 
> Hi people,
> 
> Is there anyone out there with enough knowledge of the arcane field  
> of Smith-Waterman matrixes to answer this?
> 
> OK, so Smith-Waterman is best done using a gap penalty that can has a  
> start cost, and an extension cost.
> 
> I want to implement a Smith-Waterman algorithm.
> 
> Must I maintain a "gap or not" matrix alongside the cell score matrix?
> 

If I understand your question correctly, it seems like you should pick
up a good Bioinformatics textbook and / or read the original Smith
Waterman paper. I'm not sure how exactly you want to implemement SW given
your question.

The short answer is "no". When building the distance matrix, you use the
gap insertion and extension penalties as initially given to generate the
values of that matrix.

Here is a free resource explaining the basics of dynamic programming for
sequence alignment, of which SW is a variant.

http://www.techfak.uni-bielefeld.de/bcd/Curric/PrwAli/prwali.html

HTH,

Iddo


--
Iddo Friedberg, Ph.D.
Burnham Institute for Medical Research
10901 N. Torrey Pines Rd.
La Jolla, CA 92037, USA
Tel: +1 (858) 646 3100 x3516
Fax: +1 (858) 646 3171
http://iddo-friedberg.org
http://BioFunctionPrediction.org