Nussinov's Algorithm for RNA Folding via Base Pair Maximization

The first efficient DP algorithm to predict RNA secondary structures was presented by Nussinov (Nussinov et al., 1978). This version was derived from (Durbin et al., 1998).

  nussinov78 alg inp = axiom (p s) where
    (left,right,pair,split,h) = alg

       s = tabulated (
           left  <<< base -~~ p s           |||
           right <<<          p s ~~- base  |||
           (pair <<< base -~~ p s ~~- base)
                         'with' basepairing |||
           split <<<      p s ~~~ p s       ... h

alg = (left,right,pair,split,h) where
  left  _ x   = x
  right   x _ = x
  pair  _ x _ = x + 1
  split  x y  = x + y

  h        xs = [maximum xs]