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