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

bugzilla-daemon at portal.open-bio.org bugzilla-daemon at portal.open-bio.org
Fri Oct 7 20:51:21 EDT 2005


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.

More information about the Biopython-dev mailing list