Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2005 Sep 6;33(15):4951-64.
doi: 10.1093/nar/gki773. Print 2005.

Thermodynamically based DNA strand design

Dan Tulpan  1 , Mirela Andronescu, Seo Bong Chang, Michael R Shortreed, Anne Condon, Holger H Hoos, Lloyd M Smith
Affiliations

Thermodynamically based DNA strand design

Dan Tulpan et al. Nucleic Acids Res. .

Abstract

We describe a new algorithm for design of strand sets, for use in DNA computations or universal microarrays. Our algorithm can design sets that satisfy any of several thermodynamic and combinatorial constraints, which aim to maximize desired hybridizations between strands and their complements, while minimizing undesired cross-hybridizations. To heuristically search for good strand sets, our algorithm uses a conflict-driven stochastic local search approach, which is known to be effective in solving comparable search problems. The PairFold program of Andronescu et al. [M. Andronescu, Z. C. Zhang and A. Condon (2005) J. Mol. Biol., 345, 987-1001; M. Andronescu, R. Aguirre-Hernandez, A. Condon, and H. Hoos (2003) Nucleic Acids Res., 31, 3416-3422.] is used to calculate the minimum free energy of hybridization between two mismatched strands. We describe new thermodynamic measures of the quality of strand sets. With respect to these measures of quality, our algorithm consistently finds, within reasonable time, sets that are significantly better than previously published sets in the literature.

PubMed Disclaimer

Figures

Figure 1
Figure 1
Positive free energy gaps of correct and incorrect word–complement pairs for set S5 Penchovsky. The three curves represent (from left to right) the cumulative distribution of the free energy values of all correct word–complement hybrids, of all incorrect word–complement hybrids and of all (incorrect) complement–complement hybrids. The two dots represent the specific values of i and j that determine the free energy gap as defined in Equation 1.
Figure 2
Figure 2
Correlation between pairwise discrimination values and duplex free energy gaps for sets S5 Penchovsky (control) and S5-1 (improved); each point in the plot corresponds to the discrimination and free energy gap values of a given word and an incorrect complement.
Figure 3
Figure 3
Concentration of words, complements, perfect and imperfect matches as a function of duplex free energy gaps for sets (a) S5 Penchovsky (control), and (b) S5-1 (improved); each point in the plot corresponds to the equilibrium concentration of one single strand or duplex.
Figure 4
Figure 4
Outline of the stochastic local search procedure used to partition strands into groups for use in DNA computations. A ‘bad junction’ is a junction with MFE lower than v.
Figure 5
Figure 5
Outline of the stochastic local search procedure for DNA strand design.
See this image and copyright information in PMC

References

    1. Fan J., Chen X., Halushka M.K., Berno A., Huang X., Ryder T., Lipshutz R.J., Lockhart D.J., Chakravarti A. Parallel genotyping of Human SNPs using generic high-density oligonucleotide tag arrays. Genome Res. 2000;10:853–860. - PMC - PubMed
    1. Gartner Z.J., Tse B.N., Grubina R., Doyon J.B., Snyder T.M., Liu D.R. DNA-templated organic synthesis and selection of a library of macrocycles. Science. 2004;305:1601–1605. - PMC - PubMed
    1. Halpin D.R., Harbury P.B. DNA Display I. Sequence-encoded routing of DNA populations. PLoS Biol. 2004;2:e173. - PMC - PubMed
    1. Adleman L.M. Molecular computation of solutions to combinatorial problem. Science. 1994;266:1021–1024. - PubMed
    1. Liu Q., Frutos A.G., Wang L., Condon A., Corn R.M., Smith L.M. DNA computations on surfaces. Nature. 2000;403:175–179. - PubMed

Publication types