PairFold - About
program predicts the secondary structure of a pair of RNA or
DNA molecules. Extending the notion of secondary structure for a single
molecule, a secondary structure for a pair of molecules (R1, R2) is a set
of base pairs, with each base of R1 and R2 occurring in at most one pair.
The model for measuring the free energy of a secondary structure for two
DNA or RNA molecules at a given temperature is very similar to that for a
single molecule, except that a intermolecular initiation penalty is added.
See Figure 1 part (d). The secondary structure can be represented as a
pair of strings (S1, S2) containing the symbols ".", "(", and ")". We
define the structure (S1, S2) for the pair of molecules (R1, R2) to be
pseudoknot free if and only if the structure S1S2 for the single molecule
R1R2 is pseudoknot free. PairFold returns four secondary structures, for
the pairs (R1, R2), (R2, R1), (R1, R1), and (R2, R2). The algorithm uses
dynamic programming and runs in time bounded by the cube of the lengths of
the input strands.