search

antzucaro / matchr

An approximate string matching library for the Go programming language.
Other
178 stars 26 forks source link

An easier way of doing Smith-Waterman #2

Open mmcco opened 9 years ago

mmcco commented 9 years ago

I don't know if you're interested, but there's a much easier way of doing Smith-Waterman that involves having an extra row and column at the 0th indexes, whose scores are all zero. You only need a single body loop:

https://github.com/plsql/jh-bio/blob/unique-kmers/bioutils/alignment.go#L63

For example, comparing "heh" and "hhh" will use the below matrix:

0.0  0.0  0.0  0.0  

0.0  1.0  1.0  1.0  

0.0  0.5  0.5  0.5  

0.0  1.0  1.5  1.5
mmcco commented 9 years ago

Anecdotally, you may also be interested in Needleman-Wunsch. It's basically a modified version of Smith-Waterman that does global alignment instead of local alignment. There's an example in the linked source file.

antzucaro commented 9 years ago

Thanks for the suggestion on SW! I'm aware of Needleman, but I haven't needed it yet. If I get some free time, I'll check it out. Thanks again!