website/archive/binaries/mac/src/muscle/nwrec.cpp

   1 /***\r
   2 Needleman-Wunch recursions\r
   3 \r
   4 Notation: i,j are prefix lengths so are in\r
   5 ranges i = [0,|A|] and j = [0,|B|].\r
   6 \r
   7 Profile positions are in ranges [0,|A|-1]\r
   8 and [0,|B|-1] so prefix length i corresponds\r
   9 to position (i-1) in the profile, and similarly\r
  10 for j.\r
  11 \r
  12 Terminal gap scoring\r
  13 --------------------\r
  14 Terminal gaps are scored as with open [close]\r
  15 penalties only at the left [right] terminal,\r
  16 as follows:\r
  17 \r
  18       0  i\r
  19           |  |\r
  20         A XXXXX...\r
  21         B ---XX...\r
  22 \r
  23           i |A|-1\r
  24           |  |\r
  25         A ...XXXXX\r
  26         B ...XX---\r
  27 \r
  28 In these examples, open / close penalty at position\r
  29 i is  included, but close / open penalty at |A|-1 /\r
  30 0 is not included.\r
  31 \r
  32 This is implemented by setting the open [close] \r
  33 penalty to zero in the first [last] position of\r
  34 each profile.\r
  35 \r
  36 Consider adding a column to a sub-alignment. After the\r
  37 column is added, there are i letters from A and j letters\r
  38 from B.\r
  39 \r
  40 The column starts a left-terminal gap if:\r
  41         Delete with i=1, j=0 or\r
  42         Insert with i=0, j=1.\r
  43 \r
  44 The column ends a left-terminal gap if:\r
  45         Match following Delete with j=1, or\r
  46         Match following Insert with i=1.\r
  47 \r
  48 The column starts a right-terminal gap if:\r
  49         Delete following a Match and i=|A|, or\r
  50         Insert following a Match and j=|B|.\r
  51 \r
  52 The column ends a right-terminal gap if:\r
  53         Match with i=|A|, j=|B| following Delete or Insert.\r
  54         \r
  55 RECURSION RELATIONS\r
  56 ===================\r
  57 \r
  58          i-1\r
  59           |\r
  60 DD      A ..X X\r
  61         B ..- -\r
  62 \r
  63 MD      A ..X X\r
  64         B ..X -\r
  65 \r
  66 D(i,j) = max\r
  67                         D(i-1,j) + e\r
  68                         M(i-1,j) + goA(i-1)\r
  69 Valid for:\r
  70         i = [1,|A|-1]\r
  71         j = [1,|B|]\r
  72 \r
  73 I(i,j) By symmetry with D(i,j).\r
  74 \r
  75        i-2\r
  76         | i-1\r
  77                 | |\r
  78 MM      A ..X X\r
  79         B ..X X\r
  80 \r
  81 DM      A ..X X\r
  82         B ..- X\r
  83 \r
  84 IM  A ..- X\r
  85         B ..X X\r
  86             | |\r
  87                 | j-1\r
  88            j-2\r
  89 \r
  90 M(i,j) = L(i-1,j-1) + max\r
  91                         M(i-1,j-1)\r
  92                         D(i-1,j-1) + gcA(i-2)\r
  93                         I(i-1,j-1) + gcB(j-2)\r
  94 Valid for:\r
  95         i = [2,|A|]\r
  96         j = [2,|B|]\r
  97 \r
  98 Equivalently:\r
  99 \r
 100 M(i+1,j+1) = L(i,j) + max\r
 101                         M(i,j)\r
 102                         D(i,j) + gcA(i-1)\r
 103                         I(i,j) + gcB(j-1)\r
 104 \r
 105 Valid for:\r
 106         i = [1,|A|-1]\r
 107         j = [1,|B|-1]\r
 108 \r
 109 Boundary conditions\r
 110 ===================\r
 111 \r
 112 A XXXX\r
 113 B ----\r
 114         D(0,0) = -infinity\r
 115 \r
 116         D(i,0) = ie\r
 117                 i = [1,|A|]\r
 118 \r
 119         D(0,j) = -infinity\r
 120                 j = [0,|B|]\r
 121 \r
 122 I(0,0), I(0,j) and I(i,0) by symmetry with D.\r
 123 \r
 124         M(0,0) = 0\r
 125         M(i,0) = -infinity, i > 0\r
 126         M(0,j) = -infinity, j > 0\r
 127 \r
 128 A X\r
 129 B -\r
 130         D(1,0) = e\r
 131         D(1,j) = -infinity, j = [1,|B|]\r
 132                 (assuming no I-D allowed).\r
 133 \r
 134         D(0,1) = -infinity\r
 135         D(1,1) = -infinity\r
 136         D(i,1) = max.\r
 137 ***/\r