Geometric Approaches to Gibbs Energy Landscapes and DNA Oligonucleotide Design

Geometric Approaches to Gibbs Energy Landscapes and DNA Oligonucleotide Design

Max H. Garzon (The University of Memphis, Memphis, TN, USA) and Kiran C. Bobba (The University of Memphis, Memphis, TN, USA)
Copyright: © 2011 |Pages: 15
DOI: 10.4018/ijnmc.2011070104
OnDemand PDF Download:
No Current Special Offers


DNA codeword design has been a fundamental problem since the early days of DNA computing. The problem calls for finding large sets of single DNA strands that do not crosshybridize to themselves, to each other or to others' complements. Such strands represent so-called domains, particularly in the language of chemical reaction networks (CRNs). The problem has shown to be of interest in other areas as well, including DNA memories and phylogenetic analyses because of their error correction and prevention properties. In prior work, a theoretical framework to analyze this problem has been developed and natural and simple versions of Codeword Design have been shown to be NP-complete using any single reasonable metric that approximates the Gibbs energy, thus practically making it very difficult to find any general procedure for finding such maximal sets exactly and efficiently. In this framework, codeword design is partially reduced to finding large sets of strands maximally separated in DNA spaces and, therefore, the size of such sets depends on the geometry of these spaces. Here, the authors describe in detail a new general technique to embed them in Euclidean spaces in such a way that oligonucleotides with high (low, respectively) hybridization affinity are mapped to neighboring (remote, respectively) points in a geometric lattice. This embedding materializes long-held metaphors about codeword design in analogies with error-correcting code design in information theory in terms of sphere packing and leads to designs that are in some cases known to be provably nearly optimal for small oligonucleotide sizes, whenever the corresponding spherical codes in Euclidean spaces are known to be so. It also leads to upper and lower bounds on estimates of the size of optimal codes of size under 20-mers, as well as to a few infinite families of DNA strand lengths, based on estimates of the kissing (or contact) number for sphere codes in high-dimensional Euclidean spaces. Conversely, the authors show how solutions to DNA codeword design obtained by experimental or other means can also provide solutions to difficult spherical packing geometric problems via these approaches. Finally, the reduction suggests a tool to provide some insight into the approximate structure of the Gibbs energy landscapes, which play a primary role in the design and implementation of biomolecular programs.
Article Preview


Biomolecular computing and programming have brought forth the importance of the theoretical problem of deep understanding of the thermodynamics hybridization for a variety of applications, such as self-assembly (Qian & Winfree, 2011; Seeman, 2006), natural language processing (Garzon et al., 2009; Neel at al., 2006; Bobba et al., 2006) and DNA-based memories (Neel & Garzon, 2008) and, more recently, biological phylogenies based purely on whole-genomic DNA (Garzon & Wong, 2011). The primary and critical tool in all these applications is the appropriate sets of DNA molecular ensembles that encode inputs to computational problems or serve as building blocks for the appropriate nanostructures in order to guarantee that the desirable reactions take place as intended, amidst the tendency of DNA molecules to form other structures due to the uncertainty and variability inherent in hybridization affinity. This Codeword Design problem has seen some progress in the last decade in at least two subareas. First, in searching and/or building such DNA code sets (Garzon et al., 2009; Deaton et al., 2006; Tulpan et al., 2005; Chen et al., 2006), in which the size of feasible computational problems or self-assembled nanostructures is usually directly related to the largest ensemble of DNA molecules that satisfy a given set of crosshybridization and noncrosshybrization constraints. The second and perhaps more important area deals with developing the appropriate theoretical framework to understand and analyze this type of problems, organize the knowledge about the subject in a systematic manner, and explore the power and limitations of biomolecules at large.

Complete Article List

Search this Journal:
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing