Mac binaries

[jabaws.git] / website / archive / binaries / mac / src / muscle / nwrec.cpp

diff --git a/website/archive/binaries/mac/src/muscle/nwrec.cpp b/website/archive/binaries/mac/src/muscle/nwrec.cpp
new file mode 100644 (file)
index 0000000..ff759cf
--- /dev/null
+++ b/website/archive/binaries/mac/src/muscle/nwrec.cpp
@@ -0,0 +1,137 @@
+/***\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