Optimal DNA Codes for Computing and Self-Assembly

Introduction

Until very recently, DNA has been considered just as primary storage of instructions for the makeup of living organisms. Over a decade ago, (Adleman, 1994) gave the successful demonstration of a DNA’s potential use for different purposes, more specifically, a solution to the Hamiltonian Path Problem (HPP), a problem considered beyond reach for feasible solution on conventional computers. A computational equivalent of the well known traveling salesman problem (TSP), the Hamiltonian Path problem (HPP) calls for deciding the existence of a Hamiltonian path to traverse the edges a directed graph with two singled out as source and destination vertices. The problem calls for a Boolean decision whether there exists a Hamiltonian path joining the source to the destination (i.e., a path passing through every vertex exactly once). Later in the 1990s, several authors (Winfree et al, 1998; Seaman, 1999; Benenson et al., 2001) realized a second, perhaps more important use of DNA, as a “smart glue” for self-assembly from the “bottom-up” of atomic and molecular components to form much larger and complex structures in the order of mesoscales and microscales. Even more recently, (Neel and Garzon, 2006; Garzon et al., 2003) have suggested yet a third use of DNA as a structure capable of indexing large data repositories in terascale memories searchable in feasible times, for example in the form of DNA microarrays or DNA chips (Draghici, 2003).

All these applications require an unprecedented degree of precision in placing and operating on atomic-scale components, unachievable by traditional “top-down” assembly methods, such as microlithography. The specificity and selectivity of hybridization between (nearly) complementary small DNA oligonucleotides confers upon DNA a well recognized advantage to serve as a material to self-assemble such components. Several recent results have demonstrated the exquisite degree of control that DNA would offer on structures built on DNA scaffolds. Methods to find large sets of probes (or code sets, as will be referred to below) to serve as building blocks for such operations have thus been explored in the last few years. Although the problem of finding optimal sets has been shown to be computationally difficulty (NP-complete), even for very specific and very coarse measures of hybridization affinity (Phan and Garzon, 2008), a variety of methods have been tried to find such DNA codeword sets, as well as of techniques to measure their quality. These methods have produced good DNA codes that have sufficed for prototypes of the applications mentioned above. For example, (Phan and Garzon, 2008) used a new construction called shuffling that theoretically builds good codes of size nearly optimal (within a constant factor of the optimal set) from seed DNA codes of shorter length. The size of the codes is, however, sensitively dependent on the quality and size of the seed codes. The search for such codes is thus not only of theoretical importance, but also of practical significance since they are likely to be required for the full realization of self-assembly applications in practical settings. The gigantic size of the search spaces involved even for small lengths (exp(2,4¹⁶) for 16-mers) is a primary road block for progress in this area, especially when nearly optimal performance is expected or desirable.

In this paper, we describe results of a tour de force to conduct an exhaustive search to produce code sets that are large enough to be nearly maximal sets while guaranteeing high quality. The quality criteria and a summary of prior methods are described in Section 2. Section 3 shows how to solve the problem of actually producing the actual composition of the sets, unlike its counterpart in vitro. Consequently, we also present a quantitative characterization of these codes through an analysis of occurrence of shorter k-mer blocks. In Section 4 we summarize some of the implications of these analyses for the application of these code sets. Finally, we also discuss some of the remaining problems to these sets and mention two interesting problems for further research. We assume that the reader is familiar with basic facts about molecular biology; see (Watson et al., 2003; Wetmur, 1997) for background details. Some of the results presented here have been announced in preliminary or incomplete form in (Bobba et al., 2006) and (Garzon et al., 2006). Full results and complete analyses are presented here.