The PairFold 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.

For RNA, PairFold uses the thermodynamics parameters from the Turner Group [2]. For DNA, it uses the thermodynamic parameters from the laboratory of John SantaLucia Jr. [3].


References

[1] M. Zuker, D.H. Mathews & D.H. Turner, Algorithms and Thermodynamics for RNA Secondary Structure Prediction: A Practical Guide In RNA Biochemistry and Biotechnology, J. Barciszewski & B.F.C. Clark, eds., NATO ASI Series, Kluwer Academic Publishers, (1999)

[2] Serra, M.J., Turner, D.H., & Freier, S.M. 1995. Predicting thermodynamic properties of RNA. Meth. Enzymol., 259, 243-261.

[3] SantaLucia, JJr (1998) A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics. Proc. Natl. Acad. Sci. USA 95, 1460-1465.

Links

Michael Zuker's Web Page
Turner Group
John SantaLucia Lab