  The secondary structure that maximizes the number of non-crossing matchings
between complimentary bases of an RNA sequence of length n can be computed in
O(n^3) time using Nussinov's dynamic programming algorithm. The Four-Russians
method is a technique that will reduce the running time for certain dynamic
programming algorithms by a multiplicative factor after a preprocessing step
where solutions to all smaller subproblems of a fixed size are exhaustively
enumerated and solved. Frid and Gusfield designed an O(\frac{n^3}{\log n})
algorithm for RNA folding using the Four-Russians technique. In their algorithm
the preprocessing is interleaved with the algorithm computation. (Algo. Mol.
Biol., 2010).
  We simplify the algorithm and the analysis by doing the preprocessing once
prior to the algorithm computation. We call this the two-vector method. We also
show variants where instead of exhaustive preprocessing, we only solve the
subproblems encountered in the main algorithm once and memoize the results. We
give a simple proof of correctness and explore the practical advantages over
the earlier method. The Nussinov algorithm admits an O(n^2) time parallel
algorithm. We show a parallel algorithm using the two-vector idea that improves
the time bound to O(\frac{n^2}{log n}).
  We discuss the organization of the data structures to exploit coalesced
memory access for fast running times. The ideas to organize the data structures
also help in improving the running time of the serial algorithms. For sequences
of length up to 6000 bases the parallel algorithm takes only about 2.5 seconds
and the two-vector serial method takes about 57 seconds on a desktop and 15
seconds on a server. Among the serial algorithms, the two-vector and memoized
versions are faster than the Frid-Gusfield algorithm by a factor of 3, and are
faster than Nussinov by up to a factor of 20.
