[BioPython] Smith-Waterman, anyone?

Brad Chapman chapmanb@arches.uga.edu
Thu, 3 May 2001 20:26:23 -0400


Hi Iddo!

> Does anybody have a nice (preferably fast) program which implements the
> Smith-Waterman local pairwise alignment algorithm? I'm looking for
> something which accepts 2 strings (better yet: BioPython sequence objects)
> and a substitution matrix as input, and gives some sort of intelligble
> output.

Quite the opposite of what Ewan has, I have some code for
Needleman-Wunsch in pure python. While Ewan's code satisfies your
fastness criterion (and also the all important "actually functional"
criterion), mine does use BioPython Seq objects, so I've got a leg up
there :-). I think you actually might already have this code, but it's
here just in case:

http://www.bioinformatics.org/bradstuff/bp/NWAlign.tar.gz

I wrote this a while back and it is actually not that functional, but
is a place to start if you want a pure python alternative. I actually
want to go back and work on this type of alignment code again, as this 
was part of my attempt to work my way through the excellent Durbin et
al. book. So, this is something I would like to attack in the
future. In my mind, the best thing to do would be to build a python
implementation (so I can learn :-), and then interface with Ewan's
code as a fast backend.

If you, or anyone else, is into this, I really would like to do
it. Maybe when school is out (very soon!), I will try to start putting 
something together.

All-nice-and-good-but-probably-doesn't-help-you-with-your-current-needs-ly 
yr's, 
Brad