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

[Yee Man]

Hi Ewan

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

Thanks for your reply. I hope my code will be of any use to the Bioperl
project.

> >
> 
> The first pass of the method converts the local alignment to a global
> alignment by finding the start/end points. 

I think you can get the end points without building up the directional
matrix. But how can you find the start points without doing a traceback?
Or do you actually calculate the matrix twice by reversing the input
sequences to find the start 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
> 
> 

I found a Canadian paper saying using a generalized Hirschberg algorithm
can make a better use of memory and CPU. I don't know if it will be useful
or not but you can download it from here:
http://www.cs.ualberta.ca/~jonathan/Papers/Papers/jdc.ps

> 
> SWAT is the program.
> 

I think I have the program. But is there any paper that describes it? It
will be easier for me to follow his code if I know what he tried to do.

Thanks
Yee Man