+++ /dev/null
-/***\r
-Needleman-Wunch recursions\r
-\r
-Notation: i,j are prefix lengths so are in\r
-ranges i = [0,|A|] and j = [0,|B|].\r
-\r
-Profile positions are in ranges [0,|A|-1]\r
-and [0,|B|-1] so prefix length i corresponds\r
-to position (i-1) in the profile, and similarly\r
-for j.\r
-\r
-Terminal gap scoring\r
---------------------\r
-Terminal gaps are scored as with open [close]\r
-penalties only at the left [right] terminal,\r
-as follows:\r
-\r
- 0 i\r
- | |\r
- A XXXXX...\r
- B ---XX...\r
-\r
- i |A|-1\r
- | |\r
- A ...XXXXX\r
- B ...XX---\r
-\r
-In these examples, open / close penalty at position\r
-i is included, but close / open penalty at |A|-1 /\r
-0 is not included.\r
-\r
-This is implemented by setting the open [close] \r
-penalty to zero in the first [last] position of\r
-each profile.\r
-\r
-Consider adding a column to a sub-alignment. After the\r
-column is added, there are i letters from A and j letters\r
-from B.\r
-\r
-The column starts a left-terminal gap if:\r
- Delete with i=1, j=0 or\r
- Insert with i=0, j=1.\r
-\r
-The column ends a left-terminal gap if:\r
- Match following Delete with j=1, or\r
- Match following Insert with i=1.\r
-\r
-The column starts a right-terminal gap if:\r
- Delete following a Match and i=|A|, or\r
- Insert following a Match and j=|B|.\r
-\r
-The column ends a right-terminal gap if:\r
- Match with i=|A|, j=|B| following Delete or Insert.\r
- \r
-RECURSION RELATIONS\r
-===================\r
-\r
- i-1\r
- |\r
-DD A ..X X\r
- B ..- -\r
-\r
-MD A ..X X\r
- B ..X -\r
-\r
-D(i,j) = max\r
- D(i-1,j) + e\r
- M(i-1,j) + goA(i-1)\r
-Valid for:\r
- i = [1,|A|-1]\r
- j = [1,|B|]\r
-\r
-I(i,j) By symmetry with D(i,j).\r
-\r
- i-2\r
- | i-1\r
- | |\r
-MM A ..X X\r
- B ..X X\r
-\r
-DM A ..X X\r
- B ..- X\r
-\r
-IM A ..- X\r
- B ..X X\r
- | |\r
- | j-1\r
- j-2\r
-\r
-M(i,j) = L(i-1,j-1) + max\r
- M(i-1,j-1)\r
- D(i-1,j-1) + gcA(i-2)\r
- I(i-1,j-1) + gcB(j-2)\r
-Valid for:\r
- i = [2,|A|]\r
- j = [2,|B|]\r
-\r
-Equivalently:\r
-\r
-M(i+1,j+1) = L(i,j) + max\r
- M(i,j)\r
- D(i,j) + gcA(i-1)\r
- I(i,j) + gcB(j-1)\r
-\r
-Valid for:\r
- i = [1,|A|-1]\r
- j = [1,|B|-1]\r
-\r
-Boundary conditions\r
-===================\r
-\r
-A XXXX\r
-B ----\r
- D(0,0) = -infinity\r
-\r
- D(i,0) = ie\r
- i = [1,|A|]\r
-\r
- D(0,j) = -infinity\r
- j = [0,|B|]\r
-\r
-I(0,0), I(0,j) and I(i,0) by symmetry with D.\r
-\r
- M(0,0) = 0\r
- M(i,0) = -infinity, i > 0\r
- M(0,j) = -infinity, j > 0\r
-\r
-A X\r
-B -\r
- D(1,0) = e\r
- D(1,j) = -infinity, j = [1,|B|]\r
- (assuming no I-D allowed).\r
-\r
- D(0,1) = -infinity\r
- D(1,1) = -infinity\r
- D(i,1) = max.\r
-***/\r