[Biopython-dev] [Bug 1876] Bio.pairwise2 generates incorrect Needleman-Wunsch score_matrix

[bugzilla-daemon at portal.open-bio.org]

http://bugzilla.open-bio.org/show_bug.cgi?id=1876


jchang at biopython.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |INVALID




------- Comment #7 from jchang at biopython.org  2005-10-07 20:51 -------
The algorithms produce equivalent scores and alignments when the gap penalties
are linear.  However, the algorithm implemented in Biopython is more general
and can handle more exotic non-linear models of gap penalties.

It's been many years since I've looked at this, but IIRC the original
Needleman-Wunsch paper described the algorithm implemented in Biopython, and
the algorithm in Durbin is a refinement made later to increase its speed.  The
refinement is much faster [ O(NM) vs O(NNM) ].  In biopython, for the case of
affine gap penalties, the alignment algorithm in _make_score_matrix_fast is a
hybrid of the two approaches, that has O(NM) running time, while also being
easier (for me) to understand and debug.




------- You are receiving this mail because: -------
You are the assignee for the bug, or are watching the assignee.