Junghuei Chen - US grants

There are several varieties of "evolutionary computation" based on analogies from the theory of natural evolution. In molecular biology, similar analogies are the basis of experiments on "in vitro evolution." From the beginning of DNA computing there has been an obvious appeal to the idea of marrying these two approaches. This KDI project brings these two approaches together. It provides DNA implementations for executing and assessing two classes of Genetic Algorithm computations, using population sizes larger than is usually practical with conventional computers. This project has two major goals addressing two problem types from the practice of Genetic Algorithms. The first goal is to demonstrate a DNA computation of a classic Genetic Algorithms test problem known as "Max 1s." This test problem evolves a given initial population of bitstrings until some bitstrings match a predetermined target. Two-dimensional denaturing gradient gel electrophoresis (DGGE) is used in the laboratory to physically separate candidate strands of DNA according to how well they match copies of a prespecified target strand. Molecular biological techniques are adapted to perform crossover, random mutation, and amplification of candidates. The second major goal demonstrates a class of Genetic Algorithms computations known as "Cold War problems." These problems do not involve prespecified matching targets; hence they produce outcomes which are not obvious in advance. In a Cold War problem, DNA strands encode two populations of "offers." In every generation these encoded offers are separately evolved by each of two proposers according to their own private preferences. When the two populations are combined, DGGE physically separates the most nearly matched pairs of offers.
Partially matched offers are returned to their respective proposers to become the "parents" of the next generation. Cold War problems are two-party specializations of multi-party coalition games with sidepayments. This project contributes to two disciplines. Evolutionary computation gains access to populations billions of times larger than are practical with conventional computers. Molecular biology is enhanced by laboratory techniques which combine both crossover and random mutation.

EIA-0130385
Russell J. Deaton
University of Arkansas

Title: Modeling and Manufacture of Huge DNA Oligonucleotide Libraries for Computation

Computing with DNA, with its advantages of massive parallelism and huge information density, promises a number of revolutionary applications, as well as the potential to solve problems beyond the capabilities of conventional computers. A critical barrier, however, is unplanned crosshybridization among oligonucleotides. In order for the computations to be reliable and efficient, and to scale to larger problems, the DNA sequences have to be designed to minimize these unplanned crosshybridizations. Though pairwise hybridization is well modeled and understood, design of such libraries is challenging because of the huge number of pairwise hybridization's, and the conflicting constraints of maximizing the library size while minimizing crosshybridization.Therefore, to overcome these limitations, huge libraries of non-crosshybridizing DNA oligonucleotides are manufactured by in vitro evolution with a PCR-based protocol that selects from a random pool those oligonucleotides that are maximally mismatched. In addition, because enumeration of all pairwise hybridization energetic in a huge library is computationally prohibitive, a statistical approach, which is based upon spin glass physics, is used to model the library. The model is the basis for a set of analysis and design tools for application to the libraries.

Because of the fundamental importance of DNA hybridization in DNA computing, the modeling and manufacture of huge libraries of DNA oligonucleotides is producing foundational principles and results for the field. The size of the largest libraries of non-crosshybridizing oligonucleotides is also the limit on the size of feasible computation. The libraries are an enabling resource not only for large-scale DNA computations, but also biotechnology applications, such as reusable, universal DNA microarrays. In addition, the libraries, as well as the software tools, are available for reproduction and use by other researchers in DNA computing and biotechnology.

Intellectual Merit:

In a DNA memory, information is encoded into DNA sequences and retrieved through template-matching hybridization reactions among DNA oligonucleotides. The template matching, hybridization reaction between DNA oligonucleotides is important in biotechnology and medicine (DNA microarrays),and nanotechnology (DNA directed self-assembly of nanostructures).The project should lead to a better understanding of how information can be encoded into an ensemble of hybridizing DNA oligonucleotides, and to better models and
ways of characterizing large ensembles.

Simple protocols can be used to manipulate the contents of the memory to achieve information processing. In the statistical DNA memory, an ensemble of DNA molecules are trained with test tube protocols to reproduce particular input/output mappings, similar to artificial neural networks. Rather than a one to one mapping, information is encoded probabilistically into the DNA sequences and their hybridization interactions. These two architectures will be experimentally tested and modeled computationally and physically, and finally simulated to better understand how information is stored and manipulated through DNA template-matching hybridization reactions.

Broader Impacts:

Graduate students will participate in the project, and thus, will be trained in the interdisciplinary knowledge and methods required of computational research using biological systems. They will be mentored to produce research publications, attend professional conferences and write graduate theses.

Curricular modules associated with the research will be developed for incorporation into both biological and computer curricula. These modules will provide instruction and demonstrations in the topic that show the interplay between the disciplines, as well as experimental, theoretical, and simulation methods.

The goal is to produce students that are better prepared for careers and challenges in the emerging synthesis of biology and computation. The project results will be disseminated through a dedicated web site, and through conference and journals in the relevant disciplines.