CombFold predicts which strand from a combinatorial set of strands has the minimum free energy secondary structure. An example of a combinatorial set of strands is the set of 8^8 DNA tags used by Brenner for massively parallel signature sequencing, where each tag is obtained by choosing 8 4mers from the set {TTAC, AATC, TACT, ATCA, ACAT, TCTA, CTTT, CAAA}, (where a tag can be chosen more than once) and concatenating them in any order. Combinatorial sets of a more general nature, such as those typically used in DNA computations, can also be handled. Combfold uses a dynamic programming algorithm to identify its output, thereby avoiding the need to calculate the free energy of each individual strand in the combinatorial set.

For RNA, CombFold 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. Andronescu, D. Dees, L. Slaybaugh, Y. Zhao, B. Cohen, A. Condon, and S. Skiena, Algorithms for testing that sets of DNA words concatenate without secondary structure , Proceedings of the Eighth International Workshop on DNA Based Computers, Hokkaido, Japan, June 2002. To appear in LNCS.

[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

Turner Group
John SantaLucia Lab