Back to search

University of British Columbia

Effective heuristic methods for DNA strand design

Abstract

dc:description

Sets of DNA strands that satisfy combinatorial and thermodynamic properties play an important role in various approaches to biomolecular computations, nano structure design, molecular tagging, and DNA microarrays. The problem of designing such sets of DNA strands appears to be computationally hard. This thesis introduces new algorithms for design of DNA strand sets that satisfy any of several combinatorial and thermodynamic constraints, which aim to maximize desired hybridization between strands and their complements, while minimizing undesired cross-hybridizations. To heuristically search for good strand sets for bio-computing applications, our algorithms use a conflict-driven stochastic local search approach, which is known to be effective in solving comparable search problems. We describe new and improved thermodynamic measures of the quality of strand sets. With respect to these measures of quality, our algorithms consistently find, within reasonable time, sets that are significantly better than previously published sets in the literature. We also present a detailed analysis and selection of heuristics for improving the quality of DNA strand selection criteria with direct applications in microarray probe design.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tulpan, Dan C.

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/18592

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Tulpan, Dan C.. Effective heuristic methods for DNA strand design. doctoral thesis, University of British Columbia, 2006. http://hdl.handle.net/2429/18592