Thermodynamically based DNA strand design.
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.
Tulpan
Dan
D
Department of Computer Science, University of British Columbia, Vancouver, BC, V6T 1Z4, Canada.
Andronescu
Mirela
M
Chang
Seo Bong
SB
Shortreed
Michael R
MR
Condon
Anne
A
Hoos
Holger H
HH
Smith
Lloyd M
LM
D000465:Algorithms; D019295:Computational Biology; D015342:DNA Probes / Q000737:chemistry; D020411:Oligonucleotide Array Sequence Analysis; D013269:Stochastic Processes; D013816:Thermodynamics
D015342:DNA Probes