Biomedical subjects

A E Condon

Publications and source records attributed to A E Condon.

6 recordsLinked to original sources

PubMed2001

On combinatorial DNA word design.

We consider the problem of designing DNA codes, namely sets of equi-length words over the alphabet [A, C, G, T] that satisfy certain combinatorial constraints. This problem is motivated by the task of reliably storing and retrieving information in synthetic DNA strands for use in DNA computing or as molecular bar codes in chemical libraries. The primary constraints that we consider, defined with respect to a parameter d, are as follows: for every pair of words w, x in a code, there are at least d mismatches between w and x if w not equal x and also between the reverse of w and the Watson-Crick complement of x. Extending classical results from coding theory, we present several upper and lower bounds on the maximum size of such DNA codes and give methods for constructing such codes. An additional constraint that is relevant to the design of DNA codes is that the free energies and enthalpies of the code words, and thus the melting temperatures, be similar. We describe dynamic programming algorithms that can (a) calculate the total number of words of length n whose free energy value, as approximated by a formula of Breslauer et al. (1986) falls in a given range, and (b) output a random such word. These algorithms are intended for use in heuristic algorithms for constructing DNA codes.

Algorithms↗

PubMed2000

DNA computing on surfaces.

DNA computing was proposed as a means of solving a class of intractable computational problems in which the computing time can grow exponentially with problem size (the 'NP-complete' or non-deterministic polynomial time complete problems). The principle of the technique has been demonstrated experimentally for a simple example of the hamiltonian path problem (in this case, finding an airline flight path between several cities, such that each city is visited only once). DNA computational approaches to the solution of other problems have also been investigated. One technique involves the immobilization and manipulation of combinatorial mixtures of DNA on a support. A set of DNA molecules encoding all candidate solutions to the computational problem of interest is synthesized and attached to the surface. Successive cycles of hybridization operations and exonuclease digestion are used to identify and eliminate those members of the set that are not solutions. Upon completion of all the multistep cycles, the solution to the computational problem is identified using a polymerase chain reaction to amplify the remaining molecules, which are then hybridized to an addressed array. The advantages of this approach are its scalability and potential to be automated (the use of solid-phase formats simplifies the complex repetitive chemical processes, as has been demonstrated in DNA and protein synthesis). Here we report the use of this method to solve a NP-complete problem. We consider a small example of the satisfiability problem (SAT), in which the values of a set of boolean variables satisfying certain logical constraints are determined.

Computing Methodologies↗

PubMed1999

Progress toward demonstration of a surface based DNA computation: a one word approach to solve a model satisfiability problem.

A multi-base encoding strategy is used in a one word approach to surface-based DNA computation. In this designed DNA model system, a set of 16 oligonucleotides, each a 16mer, is used with the format 5'-FFFFvvvvvvvvFFFF-3' in which 4-8 bits of data are stored in eight central variable ('v') base locations, and the remaining fixed ('F') base locations are used as a word label. The detailed implementations are reported here. In order to achieve perfect discrimination between each oligonucleotide, the efficiency and specificity of hybridization discrimination of the set of 16 oligonucleotides were examined by carrying out the hybridization of each individual fluorescently tagged complement to an array of 16 addressed immobilized oligonucleotides. A series of preliminary hybridization experiments are presented and further studies about hybridization, enzymatic destruction, read out and demonstrations of a SAT problem are forthcoming.

Animals↗

PubMed1999

Surface-based DNA computing operations: DESTROY and READOUT.

DNA computing on surfaces is where complex combinatorial mixtures of DNA molecules are immobilized on a substrate and subsets are tagged and enzymatically modified (DESTROY) in repeated cycles of the DNA computation. A restriction enzyme has been chosen for the surface DESTROY operation. For the READOUT operation, both cycle sequencing and PCR amplification followed by addressed array hybridization were studied to determine the DNA sequences after the computations.

Animals↗

PubMed1998

A surface-based approach to DNA computation.

A scalable approach to DNA-based computations is described. Complex combinatorial mixtures of DNA molecules encoding all possible answers to a computational problem are synthesized and attached to the surface of a solid support. This set of molecules is queried in successive MARK (hybridization) and DESTROY (enzymatic digestion) operations. Determination of the sequence of the DNA molecules remaining on the surface after completion of these operations yields the answer to the computational problem. Experimental demonstrations of aspects of the strategy are presented.

Automation↗

PubMed1997

Demonstration of a word design strategy for DNA computing on surfaces.

A strategy for DNA computing on surfaces using linked sets of 'DNA words' that are short oligonucleotides (16mers) is proposed. The 16mer words have the format 5'-FFFFvvvvvvvvFFFF-3' in which 4-8 bits of data are stored in 8 variable ('v') base locations, and the remaining fixed ('F') base locations are used as a word label. Using a template and map strategy, a set of 108 8mers each of which possesses at least a 4 base mismatch with the complements to all the other members of the set (4bm complements) are identified for use as a variable base sequence set. In addition, sets of 4 and 12 word labels of the form ABCD....DCBA that are respectively 8bm and 6bm complements with each other are identified. The 16mers are chosen to have a G/C content of 50% in order to make the thermodynamic stability of the perfectly matched hybridized DNA duplexes similar; a simple pairwise additive method is used to estimate the perfect match and mismatch hybridization thermodynamics. A series of preliminary experiments are presented that use small arrays of 16mers attached to chemically modified gold surfaces and fluorescently labeled complements to study the hybridization adsorption and enzymatic manipulation of the oligonucleotides.

Base Sequence↗