Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben

2003 | Buch

Self-assembling DNA Graphs Kapitel lesen Erstes Kapitel lesen

DNA Computing

8th International Workshop on DNA-Based Computers, DNA8 Sapporo, Japan, June 10–13, 2002 Revised Papers

herausgegeben von: Masami Hagiya, Azuma Ohuchi

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Biomolecular computing has emerged as an interdisciplinary ?eld that draws - gether chemistry, computer science, mathematics, molecular biology, and physics. Our knowledge on DNA nanotechnology and biomolecular computing increases exponentially with every passing year. The international meeting on DNA Based Computers has been a forum where scientists with di?erent backgrounds, yet sharing a common interest in biomolecular computing, meet and present their latest results. Continuing this tradition, the 8th International Meeting on DNA Based Computers (DNA8) focuses on the current theoretical and experimental results with the greatest impact. Papers and poster presentations were sought in all areas that relate to b- molecular computing, including (but not restricted to): algorithms and appli- tions, analysis of laboratory techniques/theoretical models, computational p- cesses in vitro and in vivo, DNA-computing-based biotechnological applications, DNA devices, error evaluation and correction, in vitro evolution, models of biomolecular computing (using DNA and/or other molecules), molecular - sign, nucleic acid chemistry, and simulation tools. Papers and posters with new experimental results were particularly encouraged. Authors who wished their work to be considered for either oral or poster presentation were asked to select from one of two submission “tracks”: – Track A - Full Paper – Track B - One-Page Abstract For authors with late-breaking results, or who were submitting their manuscript to a scienti?c journal, a one-page abstract, rather than a full paper, could be submitted in Track B. Authors could (optionally) include a preprint of their full paper, for consideration only by the program committee.

Inhaltsverzeichnis

Frontmatter

Self-assembly and Autonomous Molecular Computation

Self-assembling DNA Graphs
Abstract
We show experimental results of constructing non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections.
Phiset Sa-Ardyen, Nataša Jonoska, Nadrian C. Seeman
DNA Nanotubes: Construction and Characterization of Filaments Composed of TX-tile Lattice
Abstract
DNA-based nanotechnology is currently being developed for use in biomolecular computation, fabrication of 2D tile lattices, and engineering of 3D periodic matter. Here we present recent results on the construction and characterization of DNA nanotubes – a new self-assembling superstructure composed of DNA tiles. Triple-crossover (TAO) tiles modified with thiol-containing dsDNA stems projected out of the tile plane were utilized as the basic building block. TAO nanotubes display a constant diameter of approximately 25 nm and have been observed with lengths up to 20 microns. We present high resolution images of the constructs from transmission electron microscopy (TEM) and atomic force microscopy (AFM) as well as preliminary data on successful metallization of the nanotubes. DNA nanotubes represent a potentialb reakthrough in the self-assembly of nanometer scale circuits for electronics layout since they can be targeted to connect at specific locations on largerscale structures and can subsequently be metallized to form nanometer scale wires. The dimensions of these nanotubes are also perfectly suited for applications involving interconnection of molecular scale devices with macroscale components fabricated by conventional photolithographic methods.
Dage Liu, John H. Reif, Thomas H. La Bean
The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA
Abstract
We provide designs for the first autonomous DNA nanomechanical devices that execute cycles of motion without external environmental changes. These DNA devices translate across a circular strand of ssDNA and rotate simultaneously. The designs use various energy sources to fuel the movements, include (i) ATP consumption by DNA ligase in conjunction with restriction enzyme operations, (ii) DNA hybridization energy in trapped states, and (iii) kinetic (heat) energy. We show that each of these energy sources can be used to fuel random bidirectional movements that acquire after n steps an expected translational deviation of \( O(\sqrt n ) \) . For the devices using the first two fuel sources, the rate of stepping is accelerated over the rate of random drift due to kinetic (heat) energy. Our first DNA device, which we call walking DNA, achieves random bidirectional motion around a circular ssDNA strand by use of DNA ligase and two restriction enzymes. Our other DNA device, which we call rolling DNA, achieves random bidirectional motion without use of DNA ligase or any restriction enzyme, and instead using either hybridization energy (also possibly just using kinetic (heat) energy at a unfeasible low rate of resulting movement).
John H. Reif
Cascading Whiplash PCR with a Nicking Enzyme
Abstract
Whiplash PCR has been proposed as a unique mechanism realizing autonomous inference machines and used in various applications of DNA coumputing. However, it is not easy to increase step sizes within a single molecule because of back annealing. This paper proposes a sheme to cascade results of WPCR from molecules to molecules by using a nicking enzyme. We also show preliminary experiments to produce output fragments continuously from WPCR.
Daisuke Matsuda, Masayuki Yamamura

Molecular Evolution and Application to Biotechnology

A PNA-mediated Whiplash PCR-based Program for In Vitro Protein Evolution
Abstract
The directed evolution of proteins, using an in vitro domainal shuffling strategy was proposed in (J. Kolkman and W. Stemmer, Nat. Biotech. 19, 423 (2001). Due to backhybridization during parallel overlap assembly, however this method appears unlikely to be an efficient means of iteratively generating massive, combinatorial libraries of shuffled genes. Furthermore, recombination at the domainal level (30-300 residues) appears too coarse to effect the evolution of proteins with substantially new folds. In this work, the compact structural unit, or module (10-25 residues long), and the associated pseudo-module are adopted as the fundamental units of protein structure, so that a protein may be modelled as an N to C-terminal walk on a directed graph composed of pseudomodules. An in vitro method, employing PNA-mediated Whiplash PCR (PWPCR), RNA-protein fusion, and restriction-based recombination is then presented for evolving protein sets with high affinity for a given selection motif, subject to the constraint that each represents a walk on a predefined pseudo-module digraph. Simulations predict PWPCR to be a reasonably high efficiency method of producing massive, recombined gene libraries encoding for proteins shorter than about 600 residues.
John A. Rose, Mitsunori Takano, Akira Suyama
Engineering Signal Processing in Cells: Towards Molecular Concentration Band Detection
Abstract
We seek to couple protein-ligand interactions with synthetic gene networks in order to equip cells with the ability to process internal and environmental information in novel ways. In this paper, we propose and analyze a new genetic signal processing circuit that can be configured to detect various chemical concentration ranges of ligand molecules. These molecules freely difiuse from the environment into the cell. The circuit detects acyl-homoserine lactone ligand molecules, determines if the molecular concentration falls within two prespecifid thresholds, and reports the outcome with a fluorescent protein. In the analysis of the circuit and the description of preliminary experimental results, we demonstrate how to adjust the concentration band thresholds by altering the kinetic properties of specific genetic elements, such as ribosome binding site effiencies or dna-binding protein affnities to their operators.
Subhayu Basu, David Karig, Ron Weiss

Applications to Mathematical Problems

Temperature Gradient-Based DNA Computing for Graph Problems with Weighted Edges
Abstract
We propose an encoding method of numerical data in DNA using temperature gradient. We introduce melting temperature (Tm) for this purpose. Melting temperature is a unique characteristic to manipulate the hybridization and denaturation processes that used in the key steps in DNA computing such as the solution generation step and the amplification step. DNA strands of lower melting temperature tend to denature with ease and also be easily amplified by slightly modified polymerase chain reaction, called denaturation temperature gradient polymerase chain reaction. Using these properties, we implement a local search molecular algorithm using temperature gradient, which is contrasted to conventional exhaustive search molecular algorithms. The proposed methods are verified by solving an instance of the travelling salesman problem. We could effectively amplify the correct solution and the use of temperature gradient made the detection of solutions easier.
Ji Youn Lee, Soo-Yong Shin, Sirk June Augh, Tai Hyun Park, Byoung-Tak Zhang
Shortening the Computational Time of the Fluorescent DNA Computing
Abstract
We present a method to shorten the computational time of the fluorescent DNA computing. Fluorescent DNA computing is proposed to solve intractable computation problems such as SAT problems. They use two groups of fluorescent DNA strands. One group of fluorescent DNA represents that a constraint of the given problem is satisfied, and another group represents that a constraint is unsatisfied. The calculation is executed by hybridizing them competitively to DNA beads or spots on DNA microarray. Though the biological operation used in the fluorescent DNA computing is simple, it needs the same number of beads or spots on microarray as the number of candidate solutions. In this paper, we prove that one bead or spot can represent plural candidate solutions through SAT problem, and show the algorithm and an experimental result of the fluorescent DNA computing.
Yoichi Takenaka, Akihiro Hashimoto
How Efficiently Can Room at the Bottom Be Traded Away for Speed at the Top?
Extended Abstract
Abstract
Given exponential 2n space, we know that an Adleman- Lipton [1],[9] computation can decide many hard problems – such as boolean formula and boolean circuit evaluation – in a number of steps that is linear in the problem size n. We wish to better understand how to design biomolecular algorithms that trade away “weakly exponential” 2 n/c , c > 1, space to achieve low running times and analyze the efficiency of their space-time utilization relative to that of their best extant classical/biomolecular counterparts. We present deterministic and probabilistic parallel algorithms for the Covering Code Creation and k-SAT problems which are based on the biomolecular setting as abstracted by a randomized framework that augments that of the sticker model of Roweis et al. [13]. We illustrate the power of the randomized framework by analyzing the space-time efficiency of these biomolecular algorithms relative to the best extant classical deterministic/probabilistic algorithms [6],[14] which inspired ours. This work points to the proposed randomized sticker model as a logical tool of independent interest.
Pilar de la Torre
Hierarchical DNA Memory Based on Nested PCR
Abstract
This paper presents a hierarchical DNA memory based on nested PCR. Each DNA strand in memory consists of address blocks and a data block. In order to access specific data, we specify the order of the address primers, and nested PCR are performed by using these primers. Our laboratory experiments are also presented to demonstrate the feasibility of the proposed memory.
Satoshi Kashiwamura, Masahito Yamamoto, Atsushi Kameda, Toshikazu Shiba, Azuma Ohuchi
Binary Arithmetic for DNA Computers
Abstract
We propose a (recursive) DNA algorithm for adding two binary numbers which require O(log n) bio-steps using only O(n) different type of DNA strands, where n is the size of the binary string representing the largest of the two numbers. The salient feature of our technique is that the input strands and the output strands have exactly the same structure which makes it fully procedural unlike most methods proposed so far. Logical operations of binary numbers can easily be performed by our method and hence can be used for cryptographic purpose.
Rana Barua, Janardan Misra
Implementation of a Random Walk Method for Solving 3-SAT on Circular DNA Molecules
Abstract
In a DNA computation a select operation is used to separate DNA molecules with different sequences. The implementation of the select operation requires specialized hardware and non-standard modification of DNA molecules by adding e.g., magnetic beads to a primer sequence or using other methods to separate DNA in solution. In this paper we consider DNA computations which use enzymatic reactions and secondary structure formation to perform computations.We show that it is possible to implement an efficient (exponential-time) probabilistic algorithm to solve instances of the satisfiability problem on circular single stranded DNA.
Hubert Hug, Rainer Schuler
Version Space Learning with DNA Molecules
Abstract
Version space is used in inductive concept learning to represent the hypothesis space where the goal concept is expressed as a conjunction of attribute values. The size of the version space increases exponentially with the number of attributes. We present an efficient method for representing the version space with DNA molecules and demonstrate its effectiveness by experimental results. Primitive operations to maintain a version space are derived and their DNA implementations are described. We also propose a novel method for robust decision-making that exploits the huge number of DNA molecules representing the version space.
Hee-Woong Lim, Ji-Eun Yun, Hae-Man Jang, Young-Gyu Chai, Suk-In Yoo, Byoung-Tak Zhang
DNA Implementation of Theorem Proving with Resolution Refutation in Propositional Logic
Abstract
Theorem proving is a classical AI problem having a broad range of applications. Since its complexity grows exponentially with the size of the problem, many researchers have proposed methods to parallelize the theorem proving process. Here, we use the massive parallelism of molecular reactions to implement parallel theorem provers. In particular, we show that the resolution refutation proof procedure can be naturally and efficiently implemented by DNA hybridization. Novel DNA encoding schemes, i.e. linear encoding and hairpin encoding, are presented and their effectiveness is verified by biochemical experiments.
In-Hee Lee, Ji-Yoon Park, Hae-Man Jang, Young-Gyu Chai, Byoung-Tak Zhang
Universal Biochip Readout of Directed Hamiltonian Path Problems
Abstract
A universal design for a biochip that reads out DNA encoded graphs is enhanced by a readout technique that may resolve multiple solutions of Hamiltonian path problems. A single laboratory step is used. DNA encoded graphs are labeled with many quantum dot barcodes and then hybridized to the universal biochip. Optical readouts, one for each barcode, yield multiple partial readouts that may isolate individual paths. Computer heuristics then seek additional individual paths.
David Harlan Wood, Catherine L. Taylor Clelland, Carter Bancroft

Nucleic Acid Sequence Design

Algorithms for Testing That Sets of DNA Words Concatenate without Secondary Structure
Abstract
We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S, for some finite set S of equi-length words, are structure-free.
Mirela Andronescu, Danielle Dees, Laura Slaybaugh, Yinglei Zhao, Anne Condon, Barry Cohen, Steven Skiena
A PCR-based Protocol for In Vitro Selection of Non-crosshybridizing Oligonucleotides
Abstract
DNA computing often requires oligonucleotides that do not produce erroneous cross-hybridizations. By using in vitro evolution, huge libraries of non-crosshybridizing oligonucleotides might be evolved in the test tube. As a first step, a fitness function that corresponds to non-crosshybridization has to be implemented in an experimental protocol. Therefore, a modified version of PCR that selects non-crosshybridizing oligonucleotides was designed and tested. Experiments confirmed that the PCR-based protocol did amplify maximally mismatched oligonucleotides selectively over those that were more closely matched. In addition, a reaction temperature window was identified in which discrimination between matched and mismatched might be obtained. These results are a first step toward practical manufacture of very large libraries of non-crosshybridizing oligonucleotides in the test tube.
Russell Deaton, Junghuei Chen, Hong Bi, Max Garzon, Harvey Rubin, David Harlan Wood
On Template Method for DNA Sequence Design
Abstract
The design of DNA sequences is one of the most practical and important research topics in DNA computing. Although the design of DNA sequences is dependent on the protocol of biological experiments, it is highly required to establish a method for the systematic design of DNA sequences, which could be applied to various design constraints. Recently, Arita proposed an interesting design method, called template method, for DNA word design. The current paper discusses on some extensions of the template method, where we propose a variant of template method, the use of multiple templates, and show their effectiveness. Furthermore, we also present some theoretical properties of templates.
Satoshi Kobayashi, Tomohiro Kondo, Masanori Arita
From RNA Secondary Structure to Coding Theory: A Combinatorial Approach
Abstract
We use combinatorial analysis to transform a special case of the computational problem of designing RNA base sequences with a given minimal free energy secondary structure into a coding theory question. The function of RNA molecules is largely determined by their molecular form,wh ich in turn is significantly related to the base pairings of the secondary structure. Hence,thi s is crucial initial work in the design of RNA molecules with desired three-dimensional structures and specific functional properties. The biological importance of RNA only continues to grow with the discoveries of many different RNA molecules having vital functions other than mediating the production of proteins from DNA. Furthermore,RNA has the same potential as DNA in terms of nanotechnology and biomolecular computing.
Christine E. Heitsch, Anne E. Condon, Holger H. Hoos
Stochastic Local Search Algorithms for DNA Word Design
Abstract
We present results on the performance of a stochastic local search algorithm for the design of DNA codes, namely sets of equallength words over the nucleotides alphabet A,C,G, T that satisfy certain combinatorial constraints. Using empirical analysis of the algorithm, we gain insight on goodd esign principles. We report several cases in which our algorithm finds word sets that match or exceed the best previously known constructions.1
Dan C. Tulpan, Holger H. Hoos, Anne E. Condon
NACST/Seq: A Sequence Design System with Multiobjective Optimization
Abstract
The importance of DNA sequence design for reliable DNA computing is well recognized. In this paper, we describe a DNA sequence optimization system NACST/Seq that is based on a multiobjective genetic algorithm. It uses the concept of Pareto optimization to reflect many realistic characteristics of DNA sequences in real bio-chemical experiments flexibly. This feature allows to recommend multiple candidate sets as well as to generate the DNA sequences, which fit better to a specific DNA computing algorithm. We also describe DNA sequence analyzer that can examine and visualize the properties of given DNA sequences.
Dongmin Kim, Soo-Yong Shin, In-Hee Lee, Byoung-Tak Zhang
A Software Tool for Generating Non-crosshybridizing Libraries of DNA Oligonucleotides
Abstract
Under an all or nothing hybridization model, the problem of finding a library of non-crosshybridizing DNA oligonucleotides is shown to be equivalent to finding an independent set of vertices in a graph. Individual oligonucleotides or Watson-Crick pairs are represented as vertices. Indicating a hybridization, an edge is placed between vertices (oligonucleotides or pairs) if the minimum free energy of hybridization, according to the nearest-neighbor model of duplex thermal stability, is less than some threshold value. Using this equivalence, an algorithm is implemented to find maximal libraries. Sequence designs were generated for a test of a modified PCR protocol. The results indicated that the designed structures formed as planned, and that there was little to no secondary structure present in the single-strands. In addition, simulations to find libraries of 10-mers and 20-mers were done, and the base composition of the non-crosshybridizing libraries was found to be 2/3 A-T and 1/3 G-C under high salt conditions, and closer to uniform for lower salt concentrations.
Russell Deaton, Junghuei Chen, Hong Bi, John A. Rose

Theory

Splicing Systems: Regularity and Below
Abstract
The motivation for the development of splicing theory is recalled. A ttention is restricted to finite splicing systems, which are those having only finitely many rules and finitely many initial strings.Languages generated by such systems are necessarily regular, but not all regular languages can be so generated.Th e splicing systems that arose originally, as models of enzymatic actions, have two special properties called reflexivity and symmetry.We announce the Pixton-Goode procedure for deciding whether a given regular language can be generated by a finite reflexive splicing system.A lthough the correctness of the algorithm is not demonstrated here, two propositions that serve as major tools in the demonstration are stated.One of these is a powerful pumping lemma.Th e concept of the syntactic monoid of a language provides sharp conceptual clarity in this area.We believe that there may be yet unrealized results to be found that interweave splicing theory with subclasses of the class of regular languages and we invite others to join in these investigations.
Tom Head, Dennis Pixton, Elizabeth Goode
On the Computational Power of Insertion-Deletion Systems
Abstract
Gene insertion and deletion are basic phenomena found in DNA processing or RNA editing in molecular biology. The genetic mechanism and development based on these evolutionary transformations have been formulated as a formal system with two operations of insertion and deletion, called insertion-deletion systems ([1], [2]).
We investigate the generative power of insertion-deletion systems (InsDel systems), and show that the family INS 1 1 DEL 1 1 is equal to the family of recursively enumerable languages. This gives a positive answer to an open problem posed in [2] where it was conjectured to be negative.
Akihiro Takahara, Takashi Yokomori
Unexpected Universality Results for Three Classes of P Systems with Symport/Antiport
Abstract
Symport and antiport are biological ways of transporting molecules through membranes in “collaborating” pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute only by using communication), then we introduce a novel way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations - multisets: no ordering - and the data structure of the output - strings: linear ordering). A similar remark holds true for the case of analysing P systems: the sequence of certain distinguished objects taken from the environment during a computation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs.
Mihai Ionescu, Carlos Martín-Vide, Andrei PĂun, Gheorghe PĂun
Conformons-P Systems
Abstract
The combination of atheoretical model of the living cell and membrane computing suggests a new variant of a computational model based on membrane-enclosed compartments defined and presented in this paper for the first time. This variant is based on simple and basic concepts: conformons, a combination of information and energy; locality ofthe interactions of conformons, permitted by the presence of membrane-enclosed compartments; communication via conformons between membrane-enclosed compartments.
The computational power of this new system is sketched. Possible other variants of this model and links with Petri nets are outlined.
Pierluigi Frisco, Sungchul Ji
Parallel Rewriting P Systems with Deadlock
Abstract
We analyze P systems with different parallel methods for string rewriting. The notion of deadlock state is introduced when some rules with mixed target indications are simultaneously applied on a common string. The computational power of systems with and without deadlock is analyzed and a lower bound for the generative power is given, for some parallelism methods. Some open problems are also formulated.
Daniela Besozzi, Claudio Ferretti, Giancarlo Mauri, Claudio Zandron
A DNA-based Computational Model Using a Specific Type of Restriction Enzyme
Abstract
The restriction enzyme is an important device which provides cutting operations of DNA strands to construct a DNA-based computational model such as splicing systems [3]. In this paper, we employ a specific type of restriction enzyme which cut on both sides of their recognition sequences [6], and propose a new DNA-based computational model which has several advantages compared with conventional models. The new computational model is shown to achieve universal computability using only natural DNA-based methods such as annealing, cut, ligation and circular strands without any practically hard assumption. Furthermore, while the generative power of the computational model is shown to be universal, the parsing (accepting) computation ability is more appealed. That is, given any string, the model computes whether it accepts the string, and most conventional DNA-based model have not offer this accepting process. We show that the new computational model efficiently computes the parsing process for context-free grammars and finite sequential transducers.
Yasubumi Sakakibara, Hiroshi Imai
Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations
Abstract
A time-varying distributed H system (TVDH system) is a splicing system which has the following feature: at different moments one uses different sets of splicing rules (these sets are called components of TVDH system). The number of components is called the degree of the TVDH system. The passage from a component to another one is specified in a cycle. It was proved by the first two authors (2001) that TVDH systems of degree one generate all recursively enumerable languages. The proof was made by a sequential modelling of Turing machines. This solution is not a fully parallel one. A. Păun (1999) presented a complete parallel solution for TVDH systems of degree four by modelling type-0 formal grammars. His result was improved by the first two authors by reducing the number of components of such TVDH systems down to three (2000). In this paper we improve the last result by reducing the number of components of such TVDH systems down to two. This question remains open for one component, i.e. is it possible to construct TVDH systems of degree one which completely uses the parallel nature of molecular computations based on splicing operations (say model type-0 formal grammars)?
Maurice Margenstern, Yurii Rogozhin, Sergey Verlan
Backmatter
Metadaten
Titel
DNA Computing
herausgegeben von
Masami Hagiya
Azuma Ohuchi
Copyright-Jahr
2003
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-540-36440-5
Print ISBN
978-3-540-00531-5
DOI
https://doi.org/10.1007/3-540-36440-4