[Bioperl-l] Re: DNA Smith-Waterman code

[Ewan Birney]

On Sat, 11 Jan 2003, Yee Man wrote:

>
> Hi folks,
>
> 	I wrote a module that does DNA Smith-Waterman with affine gap
> penalty in the form of gap_cost = gap_penalty + extension_penalty * #gaps.
> I am wondering if someone here would allow me to add the code to the main
> tree.
>
> 	It is currently implemented with half-hearted Gotoh's improvement.
> Instead of storing the scoring matrix as an auxillary array and calculates
> it twice, I store the whole thing so that I only need to calculate it
> once. I also have a module that implements the whole Gotoh's improvement.
> The current one is good with small alignments. I can add the true Gotoh's
> improvement module as a fallback when we don't have the memory to run the
> doubly faster version.
>
> 	The code works basically the same as pSW and it returns a
> SimpleAlign object at the end. You can check align.pl in the
> attached package for details. It shouldn't take me too long to incorporate
> the code to the bioperl tree.

I will take a look at it and integrate it in.

>
> Regards,
> Yee Man
>
> PS Ewan: I read the comments in pSW.pm and it says it is going to use
> linear space to store the directional matrix. Is that really true? I
> remember when I read Ron Shamir's lecture notes, Hirschberg's divide and
> conquer only works for Global Alignment and not Local Alignment that SW is
> supposed to solve. Did I miss something?
>

The first pass of the method converts the local alignment to a global
alignment by finding the start/end points. then you drop into divide and
conquor. my divide and conquor ...ummm... sucks ... because I use a high
overhead memory approach (which i call a shadow-matrix). Not worth
copying; far easier to write than the forward/backward meeting for complex
DPs


> PPS What is the name of Phil Green's paper to optimize SW?
>

SWAT is the program.