Search code examples
algorithmnlpbiopython

What is the algorithm behind pairwise2 align in BioPython?

The package BioPython allows to compute pairwise local or global alignement, through different functions (align.globalxx, align.localxx, ...).

However, I have not found anywhere the algorithm on which this alignement is based. The code (source, doc) states: "Pairwise sequence alignment using a dynamic programming algorithm", and that is all.

  • Is there a paper on which this implementation is based?
  • Is it using a "standard algorithm" and if yes, what is its name?

Edit: This is a question more for citing than for understanding purposes.

Solution

  • The docstring of a private function in the code indicates that "This is an implementation of the Needleman-Wunsch dynamic programming algorithm as modified by Gotoh, implementing affine gap penalties." (l. 761 of this code).