DNA computing

Biocomputers can be an alternative for traditional "silicon-based" computers, which continuous development may be limited due to further miniaturization (imposed by the Heisenberg Uncertainty Principle) and increasing the amount of information between the central processing unit and the main memory (von Neuman bottleneck). The idea of DNA computing came true for the first time in 1994, when Adleman solved the Hamiltonian Path Problem using short DNA oligomers and DNA ligase. In the early 2000s a series of biocomputer models was presented with a seminal work of Shapiro and his colleguas who presented molecular 2 state finite automaton, in which the restriction enzyme, FokI, constituted hardware and short DNA oligomers were software as well as input/output signals. DNA molecules provided also energy for this machine. DNA computing can be exploited in many applications, from study on the gene expression pattern to diagnosis and therapy of cancer. The idea of DNA computing is still in progress in research both in vitro and in vivo and at least promising results of these research allow to have a hope for a breakthrough in the computer science.     

快速高效的DNA连接

DNA片段的连接在基因操作过程中应用广泛。通常情况下利用T4DNALigase必须经过长达16小时才能完成连接反应,而且反应常常受到DNA末端结构等的影响。宝生物工程（大连）有限公司（TaKaRa）的DNA连接系统（TaKaRaDNALigationKitVer。2）由于其独特的反应液体系,可以将反应时间缩短至半个小时,且不受DNA结构等的影响,大大地节省了反应时间,方便了实验操作。此外,在使用本试剂盒时,由于只需简单地向DNA溶液中加入一种溶液,可以在极小的反应体积下,短时间内高效地完成各种形式的DNA连接（图1、2）。并且反应液可以直接用…     

Ligation of highly modified bacteriophage DNA

After digestion by TaqI or nicking by DNAase I, five highly modified bacteriophage DNAs were tested as substrates for T4 DNA ligase. The DNAs used were from phages T4, XP12, PBS1, SP82, and SP15, which contain as a major base either glucosylated 5-hydroxymethylcytosine, 5-methylcytosine, uracil, 5-hydroxymethyluracil, or phosphoglucuronated, glucosylated 5-(4′,5′-dihydroxypentyl)uracil, respectively. The relative ability of cohesive-ended TaqI fragments of these DNAs and of normal, λ DNA to be ligated was as follows: $\text{λ}\text{DNA}\text{=}\text{XP}\text{12}\text{DNA}\text{>}\text{SP}\text{82}\text{DNA}\text{?}\text{nonglucosylated}\text{T}\text{4}\text{DNA}\text{>}\text{T}\text{4}\text{DNA}\text{=}\text{PBS}\text{1}\text{DNA}\text{?}\text{SP}\text{15}\text{DNA}$. TaqI-T4 DNA fragments were also inefficiently ligated by Escherichia coli DNA ligase. However, annealing-independent ligation of DNAase I-nicked T4, PBS1, and λ DNAs was equally efficient. We conclude that the poor ligation of TaqI fragments of T4 and PBS1 DNAs was due to the hydroxymethylation (and glucosylation) of cytosine residues at T4's cohesive ends and the substitution of uracil residues for thymine residues adjacent to PBS1's cohesive ends destabilizing the annealing of the restriction fragments. Only SP15 DNA with its negatively charged, modified base was unable to serve as a substrate for T4 DNA ligase in an annealing-independent reaction; therefore, its modification directly interfered with enzyme binding or catalysis.     

Precise Sequential DNA Ligation on A Solid Substrate: Solid-Based Rapid Sequential Ligation of Multiple DNA Molecules

Ligation, the joining of DNA fragments, is a fundamental procedure in molecular cloning and is indispensable to the production of genetically modified organisms that can be used for basic research, the applied biosciences, or both. Given that many genes cooperate in various pathways, incorporating multiple gene cassettes in tandem in a transgenic DNA construct for the purpose of genetic modification is often necessary when generating organisms that produce multiple foreign gene products. Here, we describe a novel method, designated PRESSO (precise sequential DNA ligation on a solid substrate), for the tandem ligation of multiple DNA fragments. We amplified donor DNA fragments with non-palindromic ends, and ligated the fragment to acceptor DNA fragments on solid beads. After the final donor DNA fragments, which included vector sequences, were joined to the construct that contained the array of fragments, the ligation product (the construct) was thereby released from the beads via digestion with a rare-cut meganuclease; the freed linear construct was circularized via an intra-molecular ligation. PRESSO allowed us to rapidly and efficiently join multiple genes in an optimized order and orientation. This method can overcome many technical challenges in functional genomics during the post-sequencing generation.     

New computing paradigms suggested by DNA computing: computing by carving

Inspired by the experiments in the emerging area of DNA computing, a somewhat unusual type of computation strategy was recently proposed by one of us: to generate a (large) set of candidate solutions of a problem, then remove the non-solutions such that what remains is the set of solutions. This has been called a computation by carving. This idea leads both to a speculation with possible important consequences--computing non-recursively enumerable languages--and to interesting theoretical computer science (formal language) questions.     

Three dimensional DNA structures in computing

We show that 3-dimensional graph structures can be used for solving computational problems with DNA molecules. Vertex building blocks consisting of k-armed (k = 3 or 4) branched junction molecules are used to form graphs. We present procedures for the 3-SAT and 3-vertex-colorability problems. Construction of one graph structure (in many copies) is sufficient to determine the solution to the problem. In our proposed procedure for 3-SAT, the number of steps required is equal to the number of variables in the formula. For the 3-vertex-colorability problem, the procedure requires a constant number of steps regardless of the size of the graph.     

一种平末端连接的有效方法

转化效率与质粒大小成反比,而当质粒大于１５ｋｂ时,转化效率将成为限制因素,此时提高连接效率极为必要,特别是对于具有普遍性而效率又低的平末端连接。我们在连接反应体系中,加入相应的产生平末端质粒载体的限制性内切酶Ｈｐａ Ｉ、或ＥｃｏＲ Ｖ,与不加Ｈｐａ Ｉ,或ＥｃｏＲ Ｖ的连接反应相对照,连接产物转化大肠杆菌ＪＭ１０９后,产生的转化子比率分别为１９．９％和１０．３％（ｐＦｐ７）,３２．６％和９．７％（     

Optically programming DNA computing in microflow reactors

The programmability and the integration of biochemical processing protocols are addressed for DNA computing using photochemical and microsystem techniques. A magnetically switchable selective transfer module (STM) is presented which implements the basic sequence-specific DNA filtering operation under constant flow. Secondly, a single steady flow system of STMs is presented which solves an arbitrary instance of the maximal clique problem of given maximum size N. Values of N up to about 100 should be achievable with current lithographic techniques. The specific problem is encoded in an initial labeling pattern of each module with one of 2N DNA oligonucleotides, identical for all instances of maximal clique. Thirdly, a method for optically programming the DNA labeling process via photochemical lithography is proposed, allowing different problem instances to be specified. No hydrodynamic switching of flows is required during operation -- the STMs are synchronously clocked by an external magnet. An experimental implementation of this architecture is under construction and will be reported elsewhere.     

Ligation of restriction endonuclease-generated DNA fragments using immobilized T4 DNA ligase

Phosphorylation of terminal deoxynucleotidyl transferase within leukemic cells has been demonstrated, using ³²P labelling of intact cells in culture, followed by immunoprecipitation of the cellular extracts using an anti-terminal transferase antiserum. The phosphate linkage was found to involve serine and threonine residues. Purified calf thymus terminal transferase served as a substrate for cyclic AMP independent protein kinase obtained from leukemic cells. Phosphorylation $\text{in vitro}$ of terminal transferase was accompanied by increased activity and decreased inhibition by excess ribo-ATP. These results indicate that terminal transferase is a physiologic cyclic AMP independent protein kinase substrate, and that this reaction may be important in its control.     

Ligation of newly replicated DNA controls the timing of DNA mismatch repair

1. Download : Download high-res image (133KB)
2. Download : Download full-size image

     

Ligation mediated fluorescent labeling of DNA sequencing primers.

Automated DNA sequencing utilizing fluorescently labeled primers is a proven methodology for generating quality sequence data. However, for directed primer walking strategies this necessitates synthesis and labeling of a unique primer for each sequencing reaction. Here, we describe a rapid ligation-based method of generating labeled sequencing primers. An unlabeled 5'-phosphorylated sequencing primer is ligated to a fluorescent oligonucleotide by use of a bridge primer which is complementary to portions of the previous two oligonucleotides, thus aligning them properly for ligation. The resulting fluorescent hybrid primer can be utilized directly in cycle sequencing reactions without any prior purification.     

Sequence-Dependent Structural Variations of DNA Revealed by Chemical Ligation

Abstract

The comparative study of nick-sealing efficiency under the action of BrCN or water-soluble carbodiimide was carried out for 14 dinucleotide combinations in double helix. The difference between the lowest (17%, GpG) and the highest (94%, CpT) coupling yields was found to be more than five fold, both condensing reagents showing a similar sequence-specific trend. A strong correlation observed between coupling yields at different dinucleotide combinations and ³¹P NMR parameters supports the idea that variations in chemical ligation efficiency arise from sequence-specific modulations of the helix geometry and confirms close similarity of the intrinsic fine structure of intact and nicked DNAs.     

DNA computing the Hamiltonian path problem

The directed Hamiltonian path (DHP) problem is one of the hard computational problems for which there is no practical algorithm on a conventional computer available. Many problems, including the traveling sales person problem and the longest path problem, can be translated into the DHP problem, which implies that an algorithm for DHP can also solve all the translated problems. To study the robustness of the laboratory protocol of the pioneering DNA computing for the DHP problem performed by Leonard Adleman (1994), we investigated how the graph size, multiplicity of the Hamiltonian paths, and the size of oligonucleotides that encode the vertices would affect the laboratory procedures. We applied Adleman's protocol with 18-mer oligonucleotide per node to a graph with 8 vertices and 14 edges containing two Hamiltonian paths (Adleman used 20-mer oligonucleotides for a graph with 7 nodes, 14 edges and one Hamiltonian path). We found that depending on the graph characteristics such as the number of short cycles, the oligonucleotide size, and the hybridization conditions that used to encode the graph, the protocol should be executed with different parameters from Adleman's.     

The bounded complexity of DNA computing

This paper proposes a new approach to analyzing DNA-based algorithms in molecular computation. Such protocols are characterized abstractly by: encoding, tube operations and extraction. Implementation of these approaches involves encoding in a multiset of molecules that are assembled in a tube having a number of physical attributes. The physico-chemical state of a tube can be changed by a prescribed number of elementary operations. Based on realistic definitions of these elementary operations, we define complexity of a DNA-based algorithm using the physico-chemical property of each operation. We show that new algorithms for Hamiltonian path are about twice as efficient as Adleman's original one and that a recent algorithm for Max-Clique provides a similar increase in efficiency. Consequences of this approach to tube complexity and DNA computing are discussed.     

DNA computing using single-molecule hybridization detection

DNA computing aims at using nucleic acids for computing. Since micromolar DNA solutions can act as billions of parallel nanoprocessors, DNA computers can in theory solve optimization problems that require vast search spaces. However, the actual parallelism currently being achieved is at least a hundred million-fold lower than the number of DNA molecules used. This is due to the quantity of DNA molecules of one species that is required to produce a detectable output to the computations. In order to miniaturize the computation and considerably reduce the amount of DNA needed, we have combined DNA computing with single-molecule detection. Reliable hybridization detection was achieved at the level of single DNA molecules with fluorescence cross-correlation spectroscopy. To illustrate the use of this approach, we implemented a DNA-based computation and solved a 4-variable 4-clause instance of the computationally hard Satisfiability (SAT) problem.     

Production of random DNA oligomers for scalable DNA computing

While remarkably complex networks of connected DNA molecules can form from a relatively small number of distinct oligomer strands, a large computational space created by DNA reactions would ultimately require the use of many distinct DNA strands. The automatic synthesis of this many distinct strands is economically prohibitive. We present here a new approach to producing distinct DNA oligomers based on the polymerase chain reaction (PCR) amplification of a few random template sequences. As an example, we designed a DNA template sequence consisting of a 50-mer random DNA segment flanked by two 20-mer invariant primer sequences. Amplification of a dilute sample containing about 30 different template molecules allows us to obtain around 10¹¹ copies of these molecules and their complements. We demonstrate the use of these amplicons to implement some of the vector operations that will be required in a DNA implementation of an analog neural network.