title: Backtracking in matrix to get min element
body: <p>[Not sure if I should post here, if not let me know please!]</p>
  
  <p>The problem lies in the backtracking procedure of the <a href="http://ab.inf.uni-tuebingen.de/teaching/ws06/albi1/script/rna_structure_06Dec2006.pdf" rel="nofollow">method of Zucker's</a> for minimizing energy in a secondary RNA structure, which uses dynamic programming.</p>
  
  <p>So, I have the upper triangular matrix <code>W</code>, who is filled with this formula:</p>
  
  <pre><code>W(i, j) = min([W(i,j-1),
                 W(i+1,j),
                 V(i,j),
                 min_k   // I will use an example, where this argument is NOT used
               ]);
  </code></pre>
  
  <p>At the same time I also fill a backtrack table <code>B</code> with this logic:</p>
  
  <pre><code>if(min was the first option)
    B(i, j) = 10;
  elseif(min was the 2nd option)
    B(i, j) = 11;
  elseif(min was the 3rd option)
    B(i, j) = 12;
  else
    // doesn't matter now
  </code></pre>
  
  <p>I am not sure if I have to show how <code>V</code> is filled.</p>
  
  <p>I <em>am sure that these matrices are created corrected</em>.</p>
  
  <p>The problem is that I have to show all the backtrack paths leading to the minimum value of <code>W</code>.</p>
  
  <p>Note that this question is not about <em>give me the code</em>. It is to get the big picture of how backtracking should be performed with a single example. Pseudo-code should also do the trick I guess.</p>
  
  <p>Example:</p>
  
  <pre><code>x = CACGGUUAG // input
  W =
  
        Inf      Inf      Inf        8        8        8        5        5        5
        Inf      Inf      Inf      Inf        8        8        5        5        5
        Inf      Inf      Inf      Inf      Inf        8        8        8        6
        Inf      Inf      Inf      Inf      Inf      Inf        8        8        8
        Inf      Inf      Inf      Inf      Inf      Inf      Inf        8        8
        Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf        8
        Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf
        Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf
        Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf      Inf
  
  B =
           C        A        C        G        G        U        U        A        G
       ----------------------------------------------------------------------------
       C   0        0        0       12       10       10       11       10       10
       A   0        0        0        0       12       10       12       10       10
       C   0        0        0        0        0       12       10       10       12
       G   0        0        0        0        0        0       12       10       10
       G   0        0        0        0        0        0        0       12       10
       U   0        0        0        0        0        0        0        0       12
       U   0        0        0        0        0        0        0        0        0
       A   0        0        0        0        0        0        0        0        0
       G   0        0        0        0        0        0        0        0        0
  </code></pre>
  
  <p>From what I can understand, because I couldn't find information on how to proceed after filling the matrices, so I improvised.</p>
  
  <p>I only <em>know</em> that backtrack starts from top right corner.
  So, I said:</p>
  
  <pre><code>if(B(i, j) == 10)
    go left
  elseif(B(i, j) == 11)
    go down
  else
    go left and down
  </code></pre>
  
  <p>which in this example yields</p>
  
  <pre><code>&lt;-   GC  // left
  &lt;-   AC
  |
  v    UA  // down
   /
  V    UC  // left and down
   /
  v    UG
  </code></pre>
  
  <p>which seems to work, since, if you take the path from UG in array <code>W</code>, you will find yourself in the right top corner of <code>W</code> which I think has what we are looking for.</p>
  
  <p>The problem with this logic I made up, is how to get all optimal paths and not just the one!</p>