Lecture Notes in Computer Science Edited by G. Goos, J. Hartmanis, and J. van Leeuwen
2568
3
Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Tokyo
Masami Hagiya Azuma Ohuchi (Eds.)
DNA Computing 8th International Workshop on DNA-Based Computers, DNA8 Sapporo, Japan, June 10-13, 2002 Revised Papers
13
Series Editors Gerhard Goos, Karlsruhe University, Germany Juris Hartmanis, Cornell University, NY, USA Jan van Leeuwen, Utrecht University, The Netherlands Volume Editors Masami Hagiya University of Toyko Graduate School of Information Science and Technology Department of Computer Science 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8565, Japan E-mail:
[email protected] Azuma Ohuchi Hokkaido University Graduate School of Engineering Division of Complex Systems Technology N-13, W-8, KITA-KU, Sapporo, 060, Japan E-mail:
[email protected] Cataloging-in-Publication Data applied for A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data is available in the Internet at
.
CR Subject Classification (1998): F.1, F.2.2, I.2.9, J.3 ISSN 0302-9743 ISBN 3-540-00531-5 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science+Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2003 Printed in Germany Typesetting: Camera-ready by author, data conversion by Boller Mediendesign Printed on acid-free paper SPIN: 10872239 06/3142 543210
Preface
Biomolecular computing has emerged as an interdisciplinary field that draws together 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 different 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 biomolecular computing, including (but not restricted to): algorithms and applications, analysis of laboratory techniques/theoretical models, computational processes 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 design, 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 scientific 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. We received 49 submissions in Track A, and 17 submissions in Track B. These submissions were then reviewed by the program committee members, and by some other, external reviewers. In principle, three committee members were allocated for each submission. In considering the returned review reports, all discussions pertaining to the final decisions were made online by the program committee members. The program committee wishes to thank the external reviewers, who spent much valuable time reading submissions. We finally selected 16 oral presentations from Track A. They have been included as full papers in the preliminary proceedings. Note that the competition was extremely tough for Track A submissions. We selected only one third of the submissions for oral presentations. In addition to the 16 oral presentations, we judged that 12 additional submissions in Track A were of good quality and relevance, and therefore decided to include these full papers in the preliminary proceedings. These papers were also selected for presentation as posters, during the conference. As for Track B, we selected 7 oral presentations.
VI
Preface
The meeting was held on June 10–13, 2002, in Hokkaido University, Japan. On the first day of the meeting, we had four tutorials in two tracks: one track on computer science and the other on biotechnology. Both tracks consisted of a basic tutorial held in the morning and an advanced one in the afternoon. The basic computer science tutorial was given by Takashi Yokomori (Waseda University) and was titled “Introduction to Natural Computing.” The advanced one was given by John A. Rose (University of Tokyo) and was titled “Nucleic Acid Sequence Design.” The basic biotechnology tutorial was given by Toshikazu Shiba (FUJIREBIO Inc.) and was titled “Introduction to Biotechnology.” The advanced one was given by Nadrian C. Seeman (University of New York) and was titled “DNA Self-assembly.” The next three days were for invited plenary lectures, and regular oral and poster presentations. Invited plenary lectures were by Willem P.C. Stemmer (Maxygen, Inc.), Tomoji Kawai (Osaka University), Akira Suyama (University of Tokyo), Tom Head (Binghamton University), and Bernard Yurke (Lucent Technologies). We were very honored to have these prominent researchers as plenary speakers. It is also our great pleasure to mention here that Tom Head, one of the invited speakers of the meeting, received the award The DNA Computing Scientist of 2002. The award ceremony was held at the banquet of the meeting. A paper by Tom Head, related to his invited lecture, is included in this volume. After the meeting, the full papers in the preliminary proceedings were revised by the authors and reviewed again by the program committee members and the external reviewers. The program committee thanks those reviewers again. This volume contains the final versions of the papers after the second review. Finally, the program committee wishes to thank all those who submitted papers and abstracts for consideration.
November 2002
Masami Hagiya
Organization
DNA8 was organized by Hokkaido University and CREST JST (Japan Science and Technology Corporation) in cooperation with NovusGene Inc. and the European Association for Theoretical Computer Science (EATCS).
Program Committee Masami Hagiya Anne Condon Lila Kari Thom LaBean Giancarlo Mauri John McCaskill
University of Tokyo, Japan (Program Chair) University of British Columbia, Canada University of Western Ontario, Canada Duke University, USA Universita degli Studi di Milano-Bicocca, Italy GMD-National Research Center for Information Technology, Germany Institute of Mathematics of the Romanian Academy, Romania University of Tokyo, Japan New York University, USA Tokyo Institute of Technology, Japan California Institute of Technology, USA University of Delaware, USA
Gheorghe Paun John Rose Ned Seeman Masayuki Yamamura Erik Winfree David Wood
Organizing Committee Azuma Ohuchi Masahito Yamamoto Toshikazu Shiba Hidenori Kawamura Masami Hagiya Akira Suyama Masayuki Yamamura
Hokkaido University, Japan (Organizing Committee Chair) Hokkaido University, Japan Hokkaido University, Japan Hokkaido University, Japan University of Tokyo, Japan University of Tokyo, Japan Tokyo Institute of Technology, Japan
External Reviewers J. Ackermann M. Arita D. Besozzi M. Daley R. Deaton
C. Ferretti A. Leporati E. Losseva V. Mitrana A. Nishikawa
A. Paun T. Ruecker Y. Sakakibara K. Sakamoto H. Someya
VIII
Organization
G. Stefan M. Takano H. Uejima
K. Wakabayashi G. Wozniak M. Yamamoto
T. Yokomori C. Zandron
Sponsoring Institutions Hokkaido University CREST JST (Japan Science and Technology Corporation) NovusGene Inc. European Association for Theoretical Computer Science (EATCS)
Table of Contents
Self-assembly and Autonomous Molecular Computation Self-assembling DNA Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Phiset Sa-Ardyen, Nataˇsa Jonoska, Nadrian C. Seeman
1
DNA Nanotubes: Construction and Characterization of Filaments Composed of TX-tile Lattice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Dage Liu, John H. Reif, Thomas H. LaBean The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 John H. Reif Cascading Whiplash PCR with a Nicking Enzyme . . . . . . . . . . . . . . . . . . . . . . 38 Daisuke Matsuda, Masayuki Yamamura
Molecular Evolution and Application to Biotechnology A PNA-mediated Whiplash PCR-based Program for In Vitro Protein Evolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 John A. Rose, Mitsunori Takano, Akira Suyama Engineering Signal Processing in Cells: Towards Molecular Concentration Band Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Subhayu Basu, David Karig, Ron Weiss
Applications to Mathematical Problems Temperature Gradient-Based DNA Computing for Graph Problems with Weighted Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 Ji Youn Lee, Soo-Yong Shin, Sirk June Augh, Tai Hyun Park, Byoung-Tak Zhang Shortening the Computational Time of the Fluorescent DNA Computing . . 85 Yoichi Takenaka and Akihiro Hashimoto How Efficiently Can Room at the Bottom Be Traded Away for Speed at the Top? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Pilar de la Torre Hierarchical DNA Memory Based on Nested PCR . . . . . . . . . . . . . . . . . . . . . . 112 Satoshi Kashiwamura, Masahito Yamamoto, Atsushi Kameda, Toshikazu Shiba, Azuma Ohuchi
X
Table of Contents
Binary Arithmetic for DNA Computers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Rana Barua, Janardan Misra Implementation of a Random Walk Method for Solving 3-SAT on Circular DNA Molecules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Hubert Hug, Rainer Schuler Version Space Learning with DNA Molecules . . . . . . . . . . . . . . . . . . . . . . . . . . 143 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156 In-Hee Lee, Ji-Yoon Park, Hae-Man Jang Young-Gyu Chai, Byoung-Tak Zhang Universal Biochip Readout of Directed Hamiltonian Path Problems . . . . . . 168 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Russell Deaton, Junghuei Chen, Hong Bi, Max Garzon, Harvey Rubin, David Harlan Wood On Template Method for DNA Sequence Design . . . . . . . . . . . . . . . . . . . . . . 205 Satoshi Kobayashi, Tomohiro Kondo, Masanori Arita From RNA Secondary Structure to Coding Theory: A Combinatorial Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 Christine E. Heitsch, Anne E. Condon, Holger H. Hoos Stochastic Local Search Algorithms for DNA Word Design . . . . . . . . . . . . . . 229 Dan C. Tulpan, Holger H. Hoos, Anne E. Condon NACST/Seq: A Sequence Design System with Multiobjective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 Dongmin Kim, Soo-Yong Shin, In-Hee Lee, Byoung-Tak Zhang A Software Tool for Generating Non-crosshybridizing Libraries of DNA Oligonucleotides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 Russell Deaton, Junghuei Chen, Hong Bi, John A. Rose
Table of Contents
XI
Theory Splicing Systems: Regularity and Below . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 Tom Head, Dennis Pixton, Elizabeth Goode On the Computational Power of Insertion-Deletion Systems . . . . . . . . . . . . . 269 Akihiro Takahara, Takashi Yokomori Unexpected Universality Results for Three Classes of P Systems with Symport/Antiport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 Mihai Ionescu, Carlos Mart´ın-Vide, Andrei P˘ aun, Gheorghe P˘ aun Conformons-P Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 Pierluigi Frisco, Sungchul Ji Parallel Rewriting P Systems with Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 Daniela Besozzi, Claudio Ferretti, Giancarlo Mauri, Claudio Zandron A DNA-based Computational Model Using a Specific Type of Restriction Enzyme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 Yasubumi Sakakibara, Hiroshi Imai Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 Maurice Margenstern, Yurii Rogozhin, Sergey Verlan
Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
Self-assembling DNA Graphs Phiset Sa-Ardyen1 , Nataˇsa Jonoska2, and Nadrian C. Seeman1 1
2
New York University, Department of Chemistry, New York, NY 1003 [email protected], [email protected] University of South Florida, Department of Mathematics, Tampa, FL 33620, [email protected]
Abstract. We show experimental results of constructing non regular graphs using junction molecules as vertices and duplex DNA molecules as edge connections.
1
Introduction
A variety of computational models have been introduced recently that are based on DNA properties and Watson-Crick complementarity. Several researchers have observed that the inherent three dimensional structure of DNA and self-assembling of complex three dimensional structures can be used as computational devices as well as for improving the computational power of some models. DNA tiles that perform computation, made of double and triple cross-over molecules have been proposed for self-assembly of two-dimensional arrays [9,14]. Such arrays made of DNA tiles have been obtained experimentally [10,15]. In the case of triple cross-over molecules, a simple XOR operation was experimentally confirmed [8]. Branched junction molecules and graph-like DNA structures as computational devices have been proposed by several authors [5,6,16,14,13]. Splicing of tree-like structures made of junction molecules and hairpins based on the splicing model proposed by T. Head [4] was suggested in [16]. In [13], the authors propose to simulate Horn clause computation by self-assembly of three junctions and hairpins. Computations of a variety of problems by actual construction of graphs by DNA molecules was proposed in [5,6]. All these models using branched junction molecules and construction of graphs are yet to be confirmed experimentally. Branched junction DNA molecules are already fairly well understood experimentally and in fact they have been used to form certain three dimensional DNA structures such as a DNA cube and a truncated octahedron [1,17]. Although these DNA constructs were made out of junction molecules, they all represent regular graphs, i.e. the degrees of all of the vertices are same. The experimental design and construction of a non-regular graph solely by junction molecules (representing the vertices of the graph) and duplex molecules (representing the edges) has not been obtained. M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 1–9, 2003. c Springer-Verlag Berlin Heidelberg 2003
2
Phiset Sa-Ardyen, Nataˇsa Jonoska, and Nadrian C. Seeman
In this paper we show experimental progress in obtaining such non-regular DNA graph structures. A graph made of 5 vertices and 8 edges was chosen for self-assembly. For construction of the DNA graph we use junction molecules that represent the vertices and duplex molecules that represent the edges. The molecules have vertex-edge specific sticky ends and use WC complementarity for self-assembling the graph. In section 2 we explain the design of the oligos. The experimental results are shown in section 3.
2
Design of the Self-assembly
In [6,7] the graph depicted in Figure 1 (a) was used as an example to show how the three-vertex colorability and the Hamiltonian path problem could be solved by construction of the graph. For our experiment we chose the same graph. Since the vertex v5 has degree two, for the experiment we used one duplex molecule to represent the vertex v5 and the edges connecting v5 with v1 and v4 . Hence, the designed experiment uses 5 vertices and 8 edges as depicted in Figure 1(b). V
V
V4
5
6
V4
V3
V
e6
5
e7 e3
V
1 (a)
2
V
V3 e4
e8 V
e5
e1
1
V
e2
2
(b)
Fig. 1. The graph to be DNA self-assembled. The five vertices were designed to be junction molecules, 3-armed junctions for vertices v1 , v3 , v4 and v5 and a 4-armed junction molecule for v2 . The sticky ends were designed such that once the molecules hybridize and are ligated to form the graph structure, the final ligation product is one cyclic molecule (maybe one or more knots) which can be distinguished from the partially formed linear products by two-dimensional gel electrophoresis techniques. This final structure is depicted in Figure 2. Six DNA strands are involved in the construction of each edge that connects two vertices of the graph: two strands from the junction molecule representing one of the vertices, two strands from the junction molecule representing the other vertex molecule and two strands to form the duplex molecule that represents the edge (see Figure 3). The distances between the vertices were designed such that e1 = {v1 , v2 }; e2 = {v2 , v3 }; e5 = {v3 , v4 }; e8 = {v5 , v1 } are all 4 helical turns, i.e. the length
Self-assembling DNA Graphs 1 0 1 0 0 1 1 0 0 1 0 01 1
V4
1 0 0 1 0 1 1 0 1 0
V5
* 00 11 00 11 1 0 0 1 00 11
0 1 0 1 0 1 1 00 *1
* 00 11 0 1 1 0 00 11
11 00 1 0 00 11
0 1 0 1 00 1 1 0 1 0 1 0 1 0 1 0 1 1 00 *1
V1
1 0 1 0 0 1 0 1 1 0 1 0 00 11 1 0 00 11 0 1 00 11
V3
1 0 1 0 1 0 0 1 0 1 1 0 1 0
1 0 1 0 0 1 0 1 0 1 0 1
0 1 0 1 00 1 1 *
3
1 0 00 11 00 011 1
1 0 1 00 1 V2
Fig. 2. The final DNA structure representing the graph in Figure 1 (b). The double helix is not depicted and the shaded area represents the position of the sticky ends. The stars indicate the 5 ends that have been labeled with γ−32 PATP for the experiment with results shown in Fig. 7. The hairpins added to the four edges e3 , e4 , e6 and e7 are not presented.
vertex 1
edge
vertex 2
Fig. 3. Six DNA strands involved in assembling an edge connection.
of these DNA segments is 42 base pairs. In order to attain desired flexibility the other distances were longer. The edges e3 = {v2 , v5 }; e4 = {v2 , v4 }; e7 = {v3 , v5 } were chosen to be 6 helical turns, i.e. 63 base pairs. The longest segment of 8 helical turns (i.e. 84bp long) is e6 = {v1 , v4 }. Each of the longer edge molecules e3 , e4 , e6 , e7 contains an additional hairpin of one and a half helical turn in the middle of the molecule. The 3-junctions of the hairpins contain bulges of T’s at each turn, as can be observed in Figure 4. These hairpins are expected to add flexibility to the edge molecules. For similar reasons i.e. for increased flexibility of the junctions, bulges of two T’s were added to the junction molecules at the positions where the arms of the junction meet (Figure 5). Shorter edges obtained by connecting short duplex molecules with the arms of the appropriate junctions use sticky ends of 6 bases. The sticky ends for connection of the longer edges were designed to be 8 bases long.
Phiset Sa-Ardyen, Nataˇsa Jonoska, and Nadrian C. Seeman to V2 gAACCTAggCgCAgTCTC
gAgCTATAgTACATCCAC
to V3
gTACTATAgCTCAACCgA
gCgCCTAggTTCTgCCTA
to V1
to V2
to V3
edge E2
gAATgg CCTAAgTATgTA
CTTAggCCATTCACgAAT
4
to V4
edge E1
edge E5
g T gTgg AgCTCgATC T to V2 T
T
T ACTAgCTTAAgATCg T
CTTAgTTATgC T
TCAATgTTAgA T
T
CAgTgAAgCAgCTCTAgCg
T TT T TCTAACATTgACTgTgTCC CTgCTTCACTg T T
T CgATCTTAAgCTAgT T
to V2
T gATCgAgCTCCACAC T
TT
TT
CgTAgAATCggCgTACCTC to V5
to V4
edge E4
T TT T gCATAACTAAggAgTggTC CCgATTCTACg T T
edge E3
gTAgATAggTAAg gTCAgTAgCAgACATC
CTACTgACCTTACCTATCTAC T
T gAT TggTCgACACTg T
CATgAgACgTCCgAg T T
to V5
TT
TCCTACTAgAC T
T g gAgT TgATgAgCAggATC
TT TT T gTCTAgTAg gAgCgATCCg
T
gCAgTATACTTgACgCAg
T
to V1
edge E8
T CAgTgTCgACCAATC T
gCACTTCCATTACTgTTATCg
T CTCggACgTCTCATg T
to V1
CAAgTATACTgCCAAGCA
to V4
TT TT T CgATAACAgTAATg gAAgTgCgCTCAgAg
edge E6
TCATCAACTCCT
to V5
TT
to V3
edge E7
Fig. 4. DNA sequences for the edges. For the purposes of later, more detailed analysis, a unique restriction site was incorporated into the sequence of each edge. For the longer edge molecules, these restriction sites were included in the sequences of the hairpins. The sequences for each of the strands were designed by use of the program SEQUIN [11]. The sticky ends were designed by DNASequenceGenerator [3]. In use of SEQUIN, a special care was taken so that no “sticky end” sequence appears in the whole final product more than once. In the design of the 4-junction molecule that represents v2 we took advantage of the already well understood J1 molecule [12], and the first 8 bases of the arms of v2 contain the exact sequence of J1.
3
Experimental Results
The shorter DNA oligonucleotides used in five of the vertices and four of the shorter edges were ordered from IDT, Inc., non-phosphorylated. The longer molecules were synthesized on an Applied Biosystems 380 automatic DNA synthesizer. In contrast to the shorter oligonucleotides, these were phosphorylated with their syntheses. All molecules were purified by electrophoresis. 3.1
Preliminaries
All oligonucleotides were subjected to phosphorylation using kinase labeling. First, junction molecules and edge molecules were annealed by heating each
T ACTCgTgCAgTggACCACTC
T
Tg
Ag
gT
gC
gA
TC
AC
Ag C
CT
CA
g
TT
g
CAACTgAAggTggAT
T gAACggACATAgCggATCgC
T
CCggTATCA
TA
T
gCgATggACTACATA T C
vertex 4
gA
CA
TC
gT
T
gA
vertex 5
CT
gg
AT
Tg
Ag
gA
gg
TA
Cg
to V2 gT
CA
gA
AT
Tg
CT
gT
T Tg
TC
Tg
AT
AC
g T T T
TA
Ag
Ag
CA
TT
Cg
T
TA
TC
Cg
Ag
AT
to V1
gT
gC
CC
Tg
to V5
CA Tg
gC
CA
CT
g
TC
CC A
gA
T T CA
gA
to V1 gT
gT
gC
CT
C
CT
gg
T CA gg
gA
AT
Cg
vertex 3
CT
to V3
Tg
TA
T
to V3
CTATgTCCgTTC T
T A
to V2
gTCCATCgC T
T gC
CT
C TA
to V3
A
CC A
to V2
vertex 2
CA
A
CT
gC
gA T T C
Ag
TC
gT
Ag
Tg
to V4
TC C
T
T
ggCTTACgCgAgACT TA
T
Cg
vertex 1
CTTCAgTTg T
to V4
CA
T CCTAACgCTACAggACACAg
TgTAgCgTTAgg T
A
T
TT
gCgTAAgCC T
T TgATACCggTCggTT
TC
to V1
5
to v5
CACTgCACgAgT T
CC
to V5
g TA
to V4
CCAgTTCTAggAA T
TTCCTAgAACTggCTCTgAgC
Self-assembling DNA Graphs
gC
Ta
gA
g
to V2
gT
CT
g
Fig. 5. DNA sequences for the vertices. solution to 90o C for two minutes and slowly cooled to room temperature. Formation of each of the junction molecules and the edge molecules as well as the stoichiometry was established on 12% non-denaturing polyacrylamide gels. Figure 6 shows non-denaturing gels for two of the junctions representing vertices v2 and v5 . The lanes indicated by the arrows show the junction molecule with all of the strands. The remaining lanes show partial complexes that contain only one, two, or in the case of the four junction, three of the strands. From the lanes containing the junction molecule it is clear that almost all molecules are included in the formation of the complex and there are no stoichiometry problems. Similar experiments were performed with the other junctions and the hairpins. These results are not shown here. Four strands of the expected final product were chosen to be labeled with γ−32 P-ATP. One strand at each of the junctions representing vertices v1 , v3 , v4 and v5 were labeled. The labeled strands are marked with a in Figure 2. The labeling of a v2 strand was not succesful and no ligation product was visible. All labels were chosen such that they would appear evenly spread throughout the cyclic molecule that represents the final product. The ligation of the whole graph was done by annealing all junction molecules and edge molecules separately first, according to the determined stoichiometry. Then all these complexes were mixed together and treated with T4 DNA ligase at room temperature overnight. The final single cyclic DNA molecule that represents the graph is 1084 bases long. The gel of the ligation product of these four ligations using four distinctly labeled
6
Phiset Sa-Ardyen, Nataˇsa Jonoska, and Nadrian C. Seeman
Fig. 6. Non-denaturing gels for the junction molecules representing vertices v2 and v5 . strands is presented in Figure 7. The first lane contains a linear marker, and the lanes 2,3,4,5 contain ligation products with labeled strands of junctions at v1 , v3 , v4 and v5 respectively. It is clear that a band of approximately 1078 bases, i.e. the length of the expected final product has been formed in each reaction. Having this band in all four lanes indicates that all four labeled strands are included in formation of the molecules of this length. 3.2
Final Product Results
For obtaining the final cyclic molecule, the above procedure was slightly modified. There are 32 ligation sites in the self-assembly. Even with 90% efficiency of the ligase, we will not have more than 3% of the final product. By labeling a trace of the strands we are facing the possibility that the final cyclic molecule might not be visible on autoradiograph. The band of the expected size that is clearly visible in Figure 7 was eluted, but the eluted amount was hardly detectible and all additional experiments did not produce a visible product. For the two-dimensional electrophoresis we modified the labeling protocol. The junction and edge molecules were annealed as before, but this time prior to the phosphorylation. After annealing, all junctions and edge molecules were subjected to γ−32 P-ATP labeling for one hour with kinase. To improve the phosphorylation, unlabeled ATP molecules were added for additional 7 minutes. We expected that with this process the visibility of a small yield of the final circular product would improve. In Figure 8, a two dimensional gel is presented. The first dimension was run on the 3.5% denaturing gel and the second dimension on 5%. The circled cyclic
Self-assembling DNA Graphs
7
Fig. 7. Ligation product of self-assembly of the whole graph run on a superdenaturing gel.
bands (gel areas) denoted A-H were extracted and eluted. The final cyclic product has a very complex secondary structure and in fact it might take the form of many topoisomers and may appear in the gel at several places off-diagonal. Its behavior could not be predicted, so several different bands that were clearly not linear were tested. After elution, the excised molecules were subjected to linearization (heating at 95o C for 20 minutes). The result of this linearization is presented on the right in Figure 8. Lanes 3 and 6 corresponding to the excised areas B and E from the twodimensional gel show a unique clear band of the expected size of approximately 1100 bases. There appears to be no product in the lanes corresponding to A, G, H. On the other hand, there seem to be too many bands in the lanes corresponding to C and D. At this point there is no analysis of these extra bands. They may correspond to a dimer (double cover) molecule of the expected graph. Lane F shows two molecules, none of the size that was expected. Since the position of the area marked F in the two dimensional gel is somewhat below the curve of the other excised areas, it might not contain the target product.
8
Phiset Sa-Ardyen, Nataˇsa Jonoska, and Nadrian C. Seeman
Fig. 8. 2d denaturing gel of the ligation product (left) and a denaturing gel of the linearization of the bands extracted from the 2d-gel (right).
4
Concluding Remarks
Theoretically, by the design of the oligonucleotides and the sticky ends of the junctions such that the target molecule representing the graph is one circular molecule (or knot), the results in Figure 8 suggest that we sometimes form the expected product. Although our experiments up to this point are very encouraging, we have not confirmed with certainty that the desired cyclic molecule has been obtained. Such a confirmation would be obtained by sequencing the final product and confirming with the sequence of the designed oligonucleotides. Since the yield of the resulting molecules is very low, the extracted product from the two dimensional gel will need to be amplified by PCR. In that regard the restriction sites at the hairpins of the longer edges can be utilized to specify the primers to be picked for the PCR reaction. Acknowledgement This work has been supported by grants GM-29554 from NIGMS, N00014-98-1-0093 from ONR, grants CTS-9986512, EIA-0086015, EIA0074808, DMR-01138790, and CTS-0103002 from NSF, and F30602-01-2-0561 from DARPA /AFOSR.
References 1. J.H. Chen, N.C. Seeman, Synthesis from DNA of a molecule with the connectivity of a cube, Nature 350 (1991) 631-633.
Self-assembling DNA Graphs
9
2. J.H. Chen, N.R. Kallenbach, N.C. Seeman, A specific quadrilateral synthesized from DNA branched junctions, J. Am. Chem. Soc. 111 (1989) 6402-6407. 3. U. Feldkamp, S. Saghafi, H. Rauhe, DNASequenceGenerator: A program for the construction of DNA sequences, DNA Computing: Proceedings of the 7th International Meeting on DNA Based Computers (N. Jonoska, N.C. Seeman editors), Springer LNCS 2340 (2002) 23-32. 4. T. Head, Formal language theory and DNA: an analysis of generative capacity of recombinant behaviours, Bul. of Mathematical Biology 49 (1987) 735-759. 5. N. Jonoska, S. Karl, M. Saito, Creating 3-dimensional graph structures with DNA, DNA computers III, (H. Rubin, D. Wood editors), AMS DIMACS series 48 (1999) 123-135. 6. N. Jonoska, S. Karl, M. Saito, Three dimensional DNA structures in computing, BioSystems 52 (1999) 143-153. 7. N. Jonoska, 3D DNA patterns and computing, Pattern formation in biology, vision and dynamics, (A.Carbone, M.Gromov, P.Pruzinkiewicz editors) World Scientific Publishing Company, Singapore (1999) 310-324. 8. C. Mao, T.H. LaBean, J.H. Reif, N.C. Seeman, Logical computation using algorithmic self-assembly of DNA triple-crossover molecules, Nature 407 (2000) 493-496. 9. J.H. Reif, Local parallel biomolecular computation, in DNA Based Computers III (H. Rubin, D.H. Wood edtors) AMS DIMACS series 48 (1999) 217-254. 10. P.W.K. Rothemund, Using lateral capillary forces to compute by self-assembly, Proc. of Nat. Acad. Sci. (USA) 97 (2000) 984-989. 11. N.C. Seeman, De novo design of sequences for nucleic acid structural engineering J. of Biomolecular Structure & Dynamics 8 (3) (1990) 573-581. 12. N.C. Seeman, N.R. Kallenbach, Nucleic acid junctions: a successful experiment in macromolecular design, Molecular Structure: Chemical Reactivity and Biological Activity (J.J. Stezowski, J.L. Huang, M.C. Shao editors) Oxford Univ. Press, Oxford (1988) 189-194. 13. H. Uejima, M. Hagiya, S. Kobayashi, Horn clause computation by self-assembly of DNA molecules, DNA Computing: Proceedings of the 7th International Meeting on DNA Based Computers (N. Jonoska, N.C. Seeman editors), Springer LNCS 2340 (2002) 308-320. 14. E. Winfree, X. Yang, N.C. Seeman, Universal computation via self-assembly of DNA: some theory and experiments, DNA computers II, (L. Landweber, E. Baum editors), AMS DIMACS series 44 (1998) 191-214. 15. E. Winfree, F. Liu, L.A. Wenzler, N.C. Seeman, Design and self-assembly of twodimensional DNA crystals, Nature 394 (1998) 539-544. 16. Y. Sakakibara, C. Ferretti, Splicing on tree-like structures, DNA computers III, (H. Rubin, D.H. Wood editors.) AMS DIMACS series 48 (1999) 361-275. 17. Y. Zhang, N.C. Seeman, The construction of a DNA truncated octahedron, J. Am. Chem. Soc. 160 (1994) 1661-1669.
DNA Nanotubes: Construction and Characterization of Filaments Composed of TX-tile Lattice Dage Liu, John H. Reif, and Thomas H. LaBean Department of Computer Science Duke University, Durham, NC 27708 USA {liudg, reif, thl}@cs.duke.edu
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 potential breakthrough 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.
1 1.1
Background & Introduction Self-assembling DNA Nanostructures
Adleman’s initial report of the experimental implementation of an artificial computer utilizing DNA molecules as integral components has helped to spur widespread interest in the use of DNA in information processing systems [1]. DNA-based computing can be thought of as a subfield of the broader endeavor known as DNA nanotechnology [2], [3], [4], [5], [6]. These enterprises seek to engineer synthetic DNA polymers to encode information necessary for realization of desired structures or processes on the molecular level. Properly designed sets of DNA oligonucleotides are able to self-assemble into complex, highly organized structures. The major advantage of DNA as a self-assembling structural material over all other currently known chemical systems is DNA’s well-understood base-pairing M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 10–21, 2003. c Springer-Verlag Berlin Heidelberg 2003
DNA Nanotubes
11
rules which essentially act as a programming language with which to input organizational instructions. In particular, B-form DNA, the structure adopted by double-stranded DNA (dsDNA) under standard solution conditions, consists of the famous, anti-parallel, double-helix of complementary strands. Its specifically programmable molecular recognition ability, as well as the huge diversity of available sequences, make DNA ideal for controlling the assembly of nanostructures. Annealing of complementary strands is achieved by simply heating dissolved oligonucleotide strands above their dissociation temperature then cooling them very slowly thus allowing strands to find their sequence complements and bind. Unpaired, single-strand regions (ssDNA) extending from the ends of doublestrand domains can be used to specifically bind other dsDNA displaying a complementary ssDNA sticky-end. Regions of ssDNA therefore, can act as address codes capable of orienting attached substructures to neighboring points in 3space. If DNA is appended to nanoscale objects and chemical moieties, it can act as smart glue for organizing such objects and group in space. An obvious advantage of DNA self-assembly for fabrication is the simultaneous creation of millions or billions of copies of a desired structure due to the massive parallelism inherent in molecular processes. 1.2
DNA Tiles, Lattices, and Templates
DAO
TAE
Fig. 1. Example DNA tiles. DAO 2 double helices, 2 crossovers. TAE 3 double helices, 4 crossovers. TAO tiles with some important features of each were used in construction of the nanotubes. DNA nanotechnology and some approaches to DNA-based computing rely on unusual structural motifs including the immobile branched junction [2], [7] which is a stable analogue of the Holliday intermediate in genetic recombination [8]. Normal, linear double-strand DNA can only be used to form linear, 1D structures, while DNA complexes containing stable branched junction motifs
12
Dage Liu, John H. Reif, and Thomas H. LaBean
can be used to construct 2D and 3D lattices. The smallest stable complexes contain two branched junctions (also known as “crossovers”) connecting two double helices [9] where the helices are designed to be co-planar and are said to be linked by strand exchange at the crossover points. One strand from each helix crosses over and begins base-pairing on the opposite helix. These complexes are known as DX tiles; TX tiles contain three coplanar double-helices linked at each of four crossover points. An example of a DX and a TX tile are shown in Figure 1. DNA tiles can be programmed to assemble in large 2-dimensional sheets or lattices by properly designing their sticky-ends. Lattices composed of hundreds of thousands of DX or TX tiles and extending up to at least 10 microns on their long edge have been created and examined by AFM and TEM [10], [11]. Surface features of DX lattices have been manipulated not only by addition of hairpins directed out of the lattice plane, but also by enzymatic cleavage and by annealing of DNA carrying sticky-ends complementary to projecting ssDNA [12]. Besides being attractive structural members for simple lattice formation, multi-helix tiles have been utilized as components of self-assembling DNA computers [13], [14], [15]. Shown in Figure 2 is a schematic of a simple periodic tile lattice composed of two tile types (A and B*) and a TEM image from an assembled lattice. The neighbor relations of tiles in the lattice are shown on the far left. Given cornerto-corner tile associations and matching rules as shown, where 1 binds to 1’, 2 to 2’, etc., assembled sheets exhibit the pattern shown with alternating stripes of light (A) and dark (B*) tiles.
1 3
A
2
A
4
A
A B* B*
A
A
4’ 2’
3’
B*
A
1’
A
A
A
A
B* A
B* A
B*
B* A
B*
B* A
B*
A B*
B*
B*
B*
B* A
B*
B*
A
A B*
A
B* A
B*
B*
Fig. 2. Schematic and Platinum Rotary Shadow-TEM image of DNA lattice composed of two types of TAO tile: with (dark) and without (light) stem-loops directed out of the lattice plane. Stripes of dark B* tiles are approximately 28 nm apart as expected. Note that individual tiles with 14x6.5 nm edge dimensions are discernible. The TAO tiles used in the construction of the DNA nanotubes described here are very slightly modified versions of those described above and explained in detail previously [11]. One aim of further development of these tile and lattice structures is their use are templates upon which to organize desired patterns of materials other than DNA, for example, metals, carbon nanotubes, proteins, and peptides. Such DNA templates may be useful as scaffolds for the
DNA Nanotubes
13
creation of nanoelectronic circuits and other desired objects and devices requiring nanometer scale feature resolution. Toward this end, we tested various attachment chemistries for modification of tiles and lattices including the incorporation of thiol groups (-SH). Here we report on the interesting filamentous structures which resulted from some of these chemical modifications, analysis of the nanotube structures, preliminary results of metallization of the tubes, and some speculation on their possible future usefulness as nanowire templates and as nano- to micro-scale interconnects.
2 2.1
Materials and Methods DNA Seq. Design, Synthesis, Purification, Annealing
The TAO tiles used here have been extensively described and characterized [11]. Briefly, oligonucleotide sequences were designed using a random hill-climbing algorithm to maximize the likelihood of formation of the desired base-pairing structures while minimizing the chances of spurious pairings; tiles were shown to form as designed by electrophoretic and chemical analyses; and large, flat lattice sheets were observed by AFM imaging. Custom oligonucleotides were ordered (Integrated DNA Technology) and gel purified after receipt. Sequences of oligos used here (in 5’ to 3’ direction) are: Tile type A: A1: TCGGCTATCGAGTGGACACCGAAGACCTAACCGCTTTGCGTTCCTGCTCTAC A2: AGTTAGTGGAGTGGAACGCAAAGCGGTTAGGTCTTCGGACGCTCGTGCAACG A3: ACGAGCGTGGTAGTTTTCTACCTGTCCTGCGAATGAGATGCCACCACAGTCACGGATGGACTCGAT A4: TGCTCGGTAGAGCACCAGATTTTTCTGGACTCCTGGCATCTCATTCGCACCATCCGTGACTGTGGACTAACTCCGCTT
Tile type B*: B1: CGAGCAATGAAGTGGTCACCGTTATAGCCTGGTAGTGAGCTTCCTGCTGTAT B2: ACACAGTGGAGTGGAAGCTCACTACCAGGCTATAACGGACGATGATAAGCGG B3a: AGCCGAATACAGCACCATCTTTTGATGGACTCCTGAATCGACGTAACTT B3b: TTGTTACGTCTTTCTACTCGCACCTTCGCTGAGTTTGGACTGTGTCGTTGC B4: ATCATCGTGGTTCTTTTGAACCTGACCTGCGAGGTATGTGATTTTTCACATACTTTAGAGATTCACCAAACTCAGCGAAGGACTTCAT B4a: ATCATCGTGGTTCTTTTGAACCTGACCTGCGAGGTATGTGATTT B4b: TTCACATACTTTAGAGATTCACCAAACTCAGCGAAGGACTTCAT
Strand B3a was ordered with (B3aSH) and without (B3a) a thiol group attached to its 5’ end, while B3b was made with (B3bSH) and without (B3b) a thiol on its 3’ end. The 5’ end of strand B3a and the 3’ end of B3b form a basepaired stem projecting out of the plane of the tile, likewise for B4a and B4b. Thiol modified oligos were delivered with –SSH moieties and were reduced to –SH by treatment with dithiothreitol (DTT) and buffer exchanged into annealing buffer by gel permeation chromatography prior to use (NAP-5 columns, Pharmacia).
14
Dage Liu, John H. Reif, and Thomas H. LaBean
Oligos were annealed to form tiles and lattices in stoichiometric mixtures by heating to 95˚C for 5 minutes and slowly cooling to room temperature in a thermal cycler by dropping 0.1˚C per minute (total annealing time was approximately 12 hours). Exact stoichiometry is determined, if necessary, by titrating pairs of strands designed to hydrogen bond, and visualizing them by nondenaturing gel electrophoresis; absence of monomer is taken to indicate equimolar ratios have been achieved. 2.2
Polyacrylamide Gel Electrophoresis
Gels contain 8 to 10% acrylamide (19:1, acrylamide:bisacrylamide) and a buffer consisting of 40 mM Tris-HCl (pH 8.0), 2 mM EDTA and 12.5mM magnesium acetate (TAEMg) was used for non-denaturing gels, while a Tris-borate EDTA buffer without magnesium was used for denaturing gels which also contained 8.3 M urea. The DNA was dissolved in 10 µL of TAEMg or in water. Tracking dye (1 µL) containing TAEMg, 50% glycerol and 0.2% each of Bromophenol Blue (plus Xylene Cyanol FF in non-denaturing gels) is added to the sample buffer. Gels are run on a Hoefer SE-600 electrophoresis unit at 4 V/cm at room temperature (Non-denaturing) or 55˚C (Denaturing), and exposed to X-ray film for up to 15 hrs or stained with Stains-all (0.01% Stains-All from Sigma, 45% formamide) or ethidium bromide, then photographed. 2.3
TEM (Direct, Negative Stain, Platinum Rotary Shadow)
Transmission electron micrographs were obtained on a Phillips 301 TEM. Direct examination of DNA structures was carried out by pipetting 2-4 µL of annealed DNA solution onto a copper grid which had previously been layered with carbon film. Negative staining involved application of ∼10 µL of 2% uranyl acetate solution to the grid. In all cases excess liquid was blotted from the sample by lightly touching an edge or corner of filter paper to the edge of the grid. Platinum rotary shadow samples were prepared by gently mixing annealed DNA sample with one volume of 80% glycerol, then spraying the mixture onto freshly cleaved mica using a micro capillary and compressed air. The sample was dried on the mica under high vacuum overnight in a Balzer evaporator, tilted to a 4◦ angle, and rotated 180◦ (around the normal to the sample plane) during deposition by thermal evaporation of a thin layer of platinum. The sample was then tilted to 90◦ (flat faced toward the electrodes) and coated with a carbon layer. The carbon/platinum film was floated off the mica onto the surface of a domed droplet of buffer and finally captured on a copper grid. Samples were air dried prior to examination in the TEM. 2.4
AFM (Tapping Mode in Air)
Atomic force micrographs were obtained on a Digital Instruments Nanoscope III with a multimode head by tapping mode in air. AFM tips (Silicon OTESTP)
DNA Nanotubes
15
were obtained from Digital Instruments. Samples were prepared by pipetting annealed DNA solution (∼2 µL) onto freshly cleaved mica (Ted Pella, Inc.), allowed to adhere 2 minutes, rinsed gently by doming a drop of milliQ water onto the mica, then air dried either under a stream of nitrogen or by gentle waving.
3
Experimental
In order to develop DNA tile self-assemblies as templates for nano-scale patterning of various materials we tested chemically modified oligonucleotides in several attachment chemistry schemes. First, thiolated DNA strands were studied for reaction with monofunctional monomaleimido nanogold (1.4 nm) (Nanoprobes, Inc., Yaphank, NY)) and with nanoparticulate gold colloid (4 – 10 nm) formed by the reaction of gold chloride with sodium borohydride. Next, oligos labeled with a free amine on the 5’ or 3’ end were reacted with monofunctional sulfo-N-hydroxysuccinimido nanogold (1.4 nm) (Nanoprobes, Inc.). Finally, thiol modified oligos were studied under conditions which promoted the formation of disulfide and polysulfide structures between tiles and lead to observations of DNA nanotube formation.
Fig. 3. AFM image of TAO AB* Nanotube. Stripes perpendicular to the long axis of the filaments are clearly visible and indicate closed ring structures in successive layers rather than a spiral structure which would have given stripes with noticeable diagonal slant.
Previous imaging of TAO AB* flat, lattice sheets demonstrated lattice fragments with widely varying dimensions and often with rough edges. On the other hand, DNA nanotubes exhibit uniform apparent diameter of approximately 25 nm for lengths of 10 to 20 microns. These structures were observed by AFM and TEM on negative stained samples. AFM peak-peak width measurement
16
Dage Liu, John H. Reif, and Thomas H. LaBean
indicated that the individual subunit is separated by 27 nm. AFM height measurements (Figure 3) give a mean value of ∼4.4 nm, which is twice the height of the two-dimensional DNA nanostructure.
{
{
{
{
SS
A
B*
A
B*
Fig. 4. Schematic drawing of a proposed structure for the DNA nanotubes. Shown are layers consisting of six tiles.
Figure 4 shows a section of the proposed structure of the tubes with B* tile layers alternating with A tile layers, dsDNA helix axes are aligned parallel with the tube axis, sulfur groups are located inside the tube, and there are approximately 6 or 8 tiles per ring layer. Negative stained TEM samples (Figures 5 and 6) have provided images of sufficiently high resolution to observe that B* stripes (from outwardly projecting dsDNA stems) are perpendicular to the long axis of the fibers. This provides good evidence for an even number of tiles per ring layer and flat rings rather than a spiral structure, but based on the tube diameter there may be 8 tiles per layer rather than 6 depending upon how much the tubes are flattened during sample preparation and the extent of feature broadening artifacts in AFM examinations.
400 nm
200 nm
Fig. 5. Negative stained TEM images. The right panel is a zoom in on the structure observed on the far left of the left-hand panel. It appears to show a portion of a long, well-formed nanotube which has torn open along and parallel to the main axis of the tube. B* tube stripes are visible.
DNA Nanotubes
17
It is interesting that the negative stained TEM shows detailed information of the fiber with unit periodicity of 27 nm, in good agreement with the modeled length of AB* tile. The width of the fiber is around 25 nm. These indications show that the modified AB* tiles assembled periodically and their further selfassembly lead to the formation of regular DNA fibers. It is necessary to point out that, for the self-assembled DNA two-dimensional nanostructure sample after the same negative staining treatment, only outlines of the two-dimensional sheets could be discerned by TEM, no further detailed periodic unit structure could be identified (data not shown). The contrast difference between negative stained TEM samples of 2D lattice sheets and nanotubes indicates a significant structural difference between the assemblies. The DNA tube structure containing a hole inside may accommodate relatively more negative staining agent, and thus show relatively stronger contrast and reveal more detailed periodic unit structure. The revealed DNA tube structure by AFM appears relatively fatter than that imaged by TEM, which is due to the well-known convolution effect in AFM images.
250 nm
Fig. 6. TEM of negative stained image. B* tile layers are again discernable along with what appears to be merger or bifurcation structures.
Figure 6 demonstrates another structural feature observed with low but significant frequency – the bifurcation or merging of tubes. Further experiments are required to clarify whether these are actual forks in the tile superstructures or if they are artifacts of the sample preparation and examination, however, they may turn out to be useful for targeted binding and interconnect formation if their formation can be in some way controlled. Burial of the sulfur moieties within the tubes makes logical sense because disulfide bridges and poly-sulfide rings are preferred structures formed by thiol groups under physiologic-like solution conditions such as those employed here. Internalized sulfur is also indicated by the lack of thiol available for gold binding on the outer surface of the tubes and by the tubes’ ability to bind nanogold on their surface if amino groups are added
18
Dage Liu, John H. Reif, and Thomas H. LaBean
to the dsDNA stem on the face opposite the thiol containing stem on the B* tiles (see Figure 9).
Fig. 7. Negative stained TEM image of a large colloidal gold particle apparently bound to the very end of a DNA nanotube where some exposure of sulfur could occur.
The possible existence of free thiols on the outer surface of the nanotubes was probed using two different gold reagents with reactivity toward sulfur – monomaleimido nanogold and fresh colloidal gold nanoparticles. The monofunctional nanogold failed to react significantly with the tube surfaces, while the colloidal gold displayed the interesting reactivity illustrated in Figure 7. With very low background levels of unbound gold, the bound gold particles showed a very high probability of attachment to the ends of nanotubes and not to the outer surface anywhere else along the tubes’ length. The indication is that sulfur which is buried within the tubes becomes exposed to some extent at the open ends of the nanotubes. This observation, besides offering prima facia evidence of the location of the sulfur groups, may also be exploited in future work on targeted binding or formation of electrical contacts with the ends of DNA nanotubes. To test the effect of thiol oxidation state on nanotube formation, the same set of oligos was annealed in the presence of 20 mM dithiothreitol (DTT). AFM observation of this sample showed a DNA nanostructure rather different than the nanotubes (Figure 8). The former appears to be two sheets of self-assembled DNA nanostructure stacked one on top the other. There may be interactions between –SH group from one sheet to another sheet. Further experiments must be completed to clarify an interpretation of this observation. To test metallization of the DNA nanotubes in order to produce functional nanowires and also to further characterize the orientation of TAO tiles in the tubular lattices, primary amine groups were added to the oligonucleotides (B4a and B4b) which base-pair to form the dsDNA stem projecting out of the tile plane and on the tile face opposite that of the thiol-containing stem. According
DNA Nanotubes
19
Fig. 8. AFM image of nanotube forming oligonucleotides which were annealed in the presence of 20 mM DTT.
to our model of the nanotubes, this should place the primary amines on the outside of the tubes and accessible to reaction with to sulfo-N-hydroxy-succinimido nanogold.
a
Fig. 9. AFM images of DNA nanotubes with 1.4 nm gold particles bound to the outer surface (left panel), with 1.4 nm gold followed by 2 minute reaction with silver enhancement reagent (middle panel), and 1.4 nm gold with 5 minute silver enhancement.
As shown in Figure 9, incorporation of amine modified oligo allowed reaction with the monofunctional nanogold reagent which successfully bound 1.4 nm gold particles to the outside surface of the assembled tubes. Reaction with unmodified tubes resulted in no gold labeling (data not shown). Also shown in Figure 9 are progressive time points of chemical silver deposition onto the prebound gold nanoparticles. Silver deposition is one possible route to the complete metallization of DNA nanotubes for formation of functional nanowires. The sil-
20
Dage Liu, John H. Reif, and Thomas H. LaBean
ver enhancement reagent does not deposit silver efficiently onto DNA nanotubes in the absence of bound nanogold.
4
Discussion and Conclusions
Use of a programmable, self-assembling polymer like DNA appears to be one of the most promising avenues available for positioning components for molecule electronics and for targeted connections which can subsequently be metallized to form functional nanowires. The annealing of oligonucleotides has already been used to direct specific association of gold nanospheres into 3D clusters [16], [17], [18]. Nanometer-scale gold rods have also been bound to one another via hybridization of oligonucleotides [19]. The assembly of a silver wire between two prefabricated leads by a DNA hybridization technique has also been reported [20]. However, previous studies have utilized only linear dsDNA, therefore the available structures were limited and fine control of associations was not sufficiently diverse to allow for a wide selection of programmable superstructures. The length scale of the DNA nanotubes described here is intermediate between the molecular world where distances are measured in ˚ Angstroms (10−10 meters) and the macro world, the lower end of which can be measured in microns (10−6 meters). One eventual goal of this line of basic research and materials development is the fabrication of reliable interconnects useful in bridging between these disparate length scales. Acknowledgements. This work was supported in part by research grants from DARPA/NSF (NSF-CCR-97-25021), from NSF (NSF-EIA-00-86015), and from a sponsored research agreement with Taiko Denki Co., Ltd., Tokyo.
References 1. Adleman, L.M. (1994) Molecular computation of solutions to combinatorial problems. Science 266, 1021-1024. 2. Seeman, N.C. (1982) Nucleic Acid Junctions and Lattices. J. Theor. Biol. 99, 237247 . 3. Seeman, N.C. (1999) “DNA engineering and its application to nanotechnology”, Trends in Biotechnology 17, 437-443. 4. Reif, J.H., LaBean, T.H., and Seeman, N.C., (2001) Challenges and Applications for Self-Assembled DNA Nanostructures, Proc. Sixth International Workshop on DNA-Based Computers, Leiden, The Netherlands, June, 2000. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Edited by A. Condon and G. Rozenberg. Lecture Notes in Computer Science, Springer-Verlag, Berlin Heidelberg, vol. 2054, pp. 173-198. 5. LaBean, T.H. (in press, 2002) Introduction to Self-Assembling DNA Nanostructures for Computation and Nanofabrication. in CBGI 2001, Proceedings from Computational Biology and Genome Informatics, held 3/2001 Durham, NC, World Scientific Publishing.
DNA Nanotubes
21
6. Reif, J.H. (to appear, 2002) DNA Lattices: A Programmable Method for Molecular Scale Patterning and Computation, to appear in the special issue on BioComputation, Computer and Scientific Engineering Journal of the Computer Society. 2002. 7. Seeman, N.C.; Chen, J.-H.; Kallenbach, N.R., 1989 Electrophoresis 10 345-354. 8. Holliday, R. (1964) Genet. Res. 5, 282-304. 9. Fu, T.-J. and Seeman, N.C. (1993) Biochemistry 32, 3211-3220. 10. Winfree, E., Liu, F., Wenzler, L.A., and Seeman, N.C. (1998) “Design and SelfAssembly of Two-Dimensional DNA Crystals”, Nature 394, 539-544. 11. LaBean, T. H., Yan, H., Kopatsch, J., Liu, F., Winfree, E., Reif, J.H. & Seeman, N.C. (2000) “The construction, analysis, ligation and self-assembly of DNA triple crossover complexes”, J. Am. Chem. Soc. 122, 1848-1860. 12. Liu, F. R., Sha, R. J. and Seeman, N. C. (1999) Modifying the surface features of two-dimensional DNA crystals, J. Am. Chem. Soc. 121, 917-922. 13. LaBean, T.H., Winfree, E., and Reif, J.H. (2000) “Experimental progress in computation by self-assembly of DNA tilings”, 5th DIMACS Workshop on DNA Based Computers, MIT, June, 1999. DNA Based Computers, V, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (ed. E. Winfree), American Mathematical Society, 2000. 14. Winfree, E., Yang, X., Seeman, NC, “Universal Computation via Self-assembly of DNA: Some Theory and Experiments.” In DNA Based Computers II: DIMACS Workshop, June 10-12, 1996 (Volume 44 in DIMACS). Laura F. Landweber and Eric B. Baum, editors. American Mathematical Society, 1998, 191–213. 15. Mao, C., LaBean, T.H., Reif, J.H., and Seeman, N.C. (2000) “Logical computation using algorithmic self-assembly of DNA triple-crossover molecules”, Nature, 407 493-496. 16. Alivisatos, A.P., K.P. Johnsson, X. Peng, T.E. Wilson, C.J. Loweth, M.P. Bruchez Jr., and P.G. Schultz (1996) Organization of ’nanocrystal molecules’ using DNA. Nature, 382, 609-611. 17. Mirkin, C.A., Letsinger, R.L., Mucic, R.C., and Storhoff, J.J. (1996) “A DNABased Method For Rationally Assembling Nanoparticles Into Macroscopic Materials”, Nature 382, 607-609. 18. Mucic, R. C.; Storhoff, J. J.; Mirkin, C. A.; Letsinger, R. L., (1998) “DNA-directed synthesis of binary nanoparticle network materials”, J. Am. Chem. Soc. 120, 1267412675. 19. Mbindyo, J.K.N., Reiss, B.D., Martin, B.R., Keating, C.D., Natan, M.J., and Mallouk, T.E. (2001) Advanced Materials 13, 249-254. 20. Braun, E., Eichen, Y., Sivan, U., and Ben-Yoseph, (1998), G. DNA-templated assembly and electrode attachment of a conducting silver wire, Nature 391, 775778.
The Design of Autonomous DNA Nanomechanical Devices: Walking and Rolling DNA John H. Reif Department of Computer Science, Duke University, Box 90129, Durham, NC 27708-0129. [email protected]
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( 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).
1
Introduction
Prior Work. Nanomechanical devices built of DNA have been developed using two distinct approaches: (i) Seeman’s group [MSS+99] used rotational transitions of dsDNA conformations between the B-form (right handed) to the Z-form (left-handed) controlled by ionic effector molecules and extended this technique to be DNA sequence dependant [YZS+02]. (ii) Yurke and Turberfield[YTM+00, YMT00,TYM00] demonstrated a series of DNA nanomechanical devices that used a fuel DNA strands acting as a hybridization catalyst to generate a sequence of motions in another tweezers strand of DNA; the two strands of DNA bind and unbind with the overhangs to alternately open and shut the tweezers.
Supported by DARPA/AFSOR F30602-01-2-0561, NSF ITR EIA-0086015, DARPA/NSF CCR-9725021. Paper URL: http://www.cs.duke.edu/∼reif/paper/DNAmotor/DNAmotor.pdf
M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 22–37, 2003. c Springer-Verlag Berlin Heidelberg 2003
The Design of Autonomous DNA Nanomechanical Devices
23
These prior DNA nanomechanical devices have some key restrictions that restrict their use: (a) they can only execute one type of motion (rotational or translational). It seems feasible to re-design these DNA nanomechanical devices to have both translational and rotational motion, but this still needs to be done. (b) More importantly, these prior DNA devices require environmental changes such as temperature cycling or bead treatment of biotin-streptavidin beads to make repeated motions. The Technical Challenge. A key challenge, which we address in this paper, is to make an autonomous DNA nanomechanical device that executes cycles of motion (either rotational or translational or both) without external environmental changes. Our Results. We provide designs for two autonomous DNA nanomechanical devices. Both move across a circular ssDNA strand which we call a road and simultaneously exhibit both translational and rotational movement. However, they use distinct energy sources to fuel the movements. (i) Our first nanomechanical device design, which we call walking DNA, uses as its energy source ATP consumption by DNA ligase in conjunction with two restriction enzyme operations. Our walking DNA construction, though technically quite distinct and with a different objective, might be viewed as analogous to Shapiro’s recent autonomous DNA computing machine [BPA+01].
Rolling DNA Device
Walking DNA Device dsDNA Walker
ssDNA Road:
ssDNA Road:
Bidirectional Translational & Rotational Movement
ssDNA Roller:
Bidirectional Random Translational& Rotational Movement
Fig. 1. (a)The DNA Walking Mechanism. (b)The DNA Rolling Mechanism. (ii) Our next nanomechanical device design, which we call rolling DNA (Note: the illustration on the right in Figure 1has been simplified; the small wheel loop DNA strand would in fact be topologically linked (intertwined) with the road strand of DNA). It makes no use of DNA ligase or any restriction enzyme. Instead, it uses as its energy source the hybridization energy of DNA in temporally trapped states. This involves the use of fuel DNA and the application of DNA catalyst techniques for liberating DNA from these loops conformations, and to harness their energy as they transit into lower energy conformations. Unlike the prior work of [YTM+00,YMT00,TYM00], our resulting nanomechanical device is autonomous. We also observe that a similar movement, but possibly at an
24
John H. Reif
unusable lower rate, can also be achieved using this basic design using simply kinetic (heat) energy. Potential Applications. In principle, these DNA nanomechanical devices can be incorporated at multiple sites of larger DNA nanostructures such as selfassembled DNA lattices. The DNA nanomechanical devices might be used to induced movements to hold state information and to sequence between distinct conformations. Possible applications include: (a) Array Automata: The state information could be stored at each site of a regular DNA lattice (see [WLW98,S99,LYK+00,LWR00,MLR+00,RLS01,R01]), and additional mechanisms for finite state transiting would provide for the capability of a cellular array automata. (b) Nanofabrication: These capabilities might be used to selectively control nanofabrication stages. The size or shape of a DNA lattice may be programmed through the control of such sequence-dependent devices and this might be used to execute a series of foldings (similar to Japanese paper folding techniques) of the DNA lattice to form a variety of 3D conformations and geometries.
2
Our Walking DNA Device
Here we describe a DNA nanomechanical device (see Figure 1a) that achieves autonomous bidirectional translational and rotational motion along a DNA strand. We will be using, as the energy source, ATP consumption by DNA ligase in conjunction with restriction enzyme operations. We will use the following notation: (i) superscript R to denote the reverse of a sequence, and (ii) overbar to denote the complement of an ssDNA sequence. Overview of Our Walking DNA Device Construction. The basic idea is to form a circular repeating strand R of ssDNA we call the road, which will be written in 5 to 3 direction from left to right. The road (See Figure 2 ) will consist of an even number n of subsequences, which we call steppingstones, indexed from 0 to n-1 modulo n. The ith steppingstone consists of a length L(where L is between 15 to 20 base pairs) sequence Ai of ssDNA. (In our constructions, the Ai repeat with a period of 2.) A0
A1
A2 …An-1
An … …
Fig. 2. The DNA Road. Let us designate the direction 5 to 3 to be direction right on the road R, and let us designate the direction 3 to 5 to be direction left on the road R. At any given time, there is a unique a partial duplex DNA strand Wi which we call the th i th walker with 3 ends Ai−1 and Ai that are hybridized to consecutive (i − 1) th and i steppingstones Ai−1 and Ai , respectively, as illustrated on the left in Figure 3.
The Design of Autonomous DNA Nanomechanical Devices
Wi
Wi+1:
A i-1
A0
25
A1 … Ai-1
Step
Ai
Ai
Ai+1
A0
A1 … Ai-1
Ai
A i+1
Ai
Ai+1
Fig. 3. A Step of the DNA Walker The Goal of the Device Construction. The below construction will have the goal of getting the ith walker Wi to reform to another partial duplex DNA strand, namely the (i+1)th walker Wi+1 which is shifted one unit over to the left or the right. In the case of the latter movement to the right, the movement results in the 3 ends Ai and AI+1 being hybridized to consecutive ith and (i + 1)th steppingstones Ai and Ai+1 , respectively, as illustrated on the right in Figure 3(the movement to the left is reversed). Hence, the movement we will achieve is bidirectional, translational movement either in the 5 to 3 direction (from left to right) on the road, or in the 3 to 5 direction. We will describe in detail the movement in the 5 to 3 direction, and then observe that the in the 3 to 5 direction is also feasible. We cycle back in 2 stages, so that Wi+2 = Wi for each stage i. To achieve the movements, we will use two distinct type-2 restriction enzymes. We will also make use of DNA ligase, which provides a source of energy (though ATP consumption) and a high degree of irreversibility. Simultaneous Translational and Rotational Movements. Due to the well known secondary structure of B-form dsDNA (rotating 2π radians every approx 10.5 bases), it follows that in each such step of translational movement, the walker will rotate around the axis of the road by approximately L2π/10.5 = Lπ/5.25 radians. Hence the DNA walker construction will execute a very simple type of motion with simultaneous translation and rotation. Avoiding Unwanted Interactions. To ensure there is no interaction between a walker and more than one distinct road at a time, we use a sufficiently low road concentration and solid support attachment of the roads. To ensure there is no interaction between a road and more than one walker, we use a sufficiently low walker concentration. Details of Our Device Construction. In the following detailed description given below, we describe the sequence of movements involving all the components: walker, road, restriction enzymes and ligase. And we provide a sequence of cartoon Figure s illustrating these movements. Definition of the Walker and Oglionucleotides used in Walking DNA Construction: For each i = 0, 1, we define ssDNA (in the 5‘ to 3‘ direction): R R R Ci−1 C i B i Ai R . Here Bi (a) Gi = BiR CiR C i−1 B i−1 Ai−1 and (b) Hi = Bi−1 Ci and the previously defined Ai are distinct oglionucleotides of low annealing cross-affinity. To ensure we cycle back in 2 stages, the subscripts of the Ai Bi Ci are taken modulo 2, and so: Ai+1 = Ai−1 , Bi+1 = Bi−1 and Ci+1 = Ci−1
26
John H. Reif
for each i. Note that Gi has subsequence BiR CiR C i−1 B i−1 and Hi has, as a R R subsequence, the reverse complement Bi−1 Ci−1 C i B i of that subsequence. We th define the i walker Wi to be the partial duplex resulting by hybridization of Gi and Hi at these reverse complementary subsequences, with ssDNA 3‘ overhangs Ai−1 and Ai , as given in Figure 4.
BiR B iR
Ai
CiR C i-1 C iR
Fig. 4. (a)The DNA walker. (b)The DNA stepper. We inductively assume that ith walker Wi has the 3 end Ai−1 of its component strand Gi hybridized to steppingstone Ai−1 on the road R and the 3 end Ai of its component strand Hi hybridized to steppingstone Ai on the road R. Definition of the Stepper: To aid us in this movement, for each i = 0, 1 we include in solution the following partial duplex Si which we call the i th stepper strand illustrated on the right in Figure 4. Note that each of the ith steppingstone Ai subsequences will hybridize with a complementary subsequence Ai of the ith stepper Si . We assume that this occurs at each steppingstone, except the steppingstones where the walker’s ends are hybridized, as illustrated on the left in Figure 5.
Ci
A
0
A0
A1 …
A i-1
Ai
A1 … Ai-1 Ai
A
i+1
Ai+1
… …
Restriction Enzyme Cleavage
CiR
A0
A1 …
A i-1
Ai
A
A0
A1 … Ai-1
Ai
A
Fig. 5. Cleavage of the DNA walker. Restriction Enzyme Cleavage of the Walker: For each i = 0, 1, we use a type two restriction enzyme that matches with the duplex subsequence containing Ci−1 Bi−1 and its complement C i−1 B i−1 within Wi , and then cleaves Wi just before C i and just after Ci , as illustrated on the right in Figure 6. This can result in the following products: (P1) A i th truncated walker T Wi (still attached to the ith steppingstone Si ) consisting of a partial duplex with an ssDNA overhang (Ci )R at one 3 end, as illustrated on the left in Figure 6, and also (P2) A partial duplex, as also illustrated on the right in Figure 6, which we can observe is the (i − 1)th stepper Si−1 , still attached to the (i − 1)th steppingstone
The Design of Autonomous DNA Nanomechanical Devices
27
Si−1 (To see this is the (i − 1)th stepper Si−1 , note that the right illustration in Figure 6can be flipped left to right and top to bottom so as to be equivalently viewed as C i ; since C i = C i−2 , this above cleavage product is identical to above defined (i − 1)th stepper Si−1 .) with an ssDNA overhang (C i )R at one 3 end.
Ai
BiR CiR B iR
Products of
Cleavage
Fig. 6. Products of the cleavage of the DNA walker. We assume that the sequences of sufficiently short length that the only strands with an ssDNA subsequence C i which can possibly hybridize with the ssDNA subsequence Ci of the above ith truncated walker T Wi are the adjacent steppers Si−1 and Si+1 . Reversals. It will be important to observe, when at the end of this section further below we observe bi-directionality of the movement of the walker, that the walker has two possible (dual) restriction enzyme recognition sites, and so the dual use of the two restriction enzymes also can result in other pair of products, resulting in a reversal of movement. However, to simplify the discussion, we ignore these reversals for the moment. Stalls. Observe that it is certainly quite possible that the above cleavage operation might simply be reversed by re-hybridization of subsequence C i of stepper Si−1 with the complementary subsequence Ci of the above truncated walker T Wi (and possibly a subsequent ligation), reforming the original walker Wi . We will call this restriction enzyme cutting and then re-hybridization a stall event for Wi . Each stall event has a constant probability q, where 0 < q < 1. The consecutive repetition of stall events for Wi might continue any number of times, but as we shall see, the likelihood drops rapidly with the number of repeated stall events. To see this, observe that the number of repeats has, by definition, a geometric probability distribution with geometric parameter p = 1 − q. This geometric probability distribution is known to have expectation E = p/(1 − p), which is a fixed constant. Furthermore, the probability of sE repeats of consecutive stall events for Wi (that is, a factor s more than the expected number E) can be shown to drop exponentially with s, for s > 2. The Stepping of the Walker. In the following, we now consider the case where there have been possibly already been a number of stall events for Wi , but now there is not a further repeat of a stall event for Wi . In this case, we show that what eventually occurs is the intended modification of the truncated walker T Wi into the (i + 1)th walker Wi+1 . Observe that by flipping the left Figure 6for TDi (the flip is top to bottom and left to right), the truncated walker TDi can be redrawn as illustrated on the right in Figure 7and the (i + 1)th stepper strand Si+1 is by definition as illustrated on the left in Figure 7.
28
John H. Reif
Bi
A iR
Ci Bi
Hybridization
Fig. 7. Hybridization with the DNA walker. This (i + 1)th stepper strand Si+1 was assumed to be hybridized with a complementary subsequence Ai+1 of (i + 1)th stepper Si+1 . This (i + 1)th stepper strand Si+1 can also hybridize with the truncated walker T Wi at their C i and Ci ssDNA overhangs, to form the duplex as illustrated on the left in Figure 8, and the DNA ligase can concatenate the strands, forming the following duplex as illustrated on the right in Figure 8.
ligation
Fig. 8. Ligation within the DNA walker. But the above duplex is by definition the (i + 1)th walker Wi+1 . We now claim that this (i + 1)th walker Wi+1 has its 3 ends hybridized to consecutive steppingstones Ai and Ai+1 in its required position as given on the right of Figure 9.
Ci
CiR
A0
A1 …
A i-1
Ai
A i+1
A0
A1 …
A i-1
Ai
A i+1 …
A0
A1 … Ai-1
Ai
Ai+1
A0
A1 …
Ai-1
Ai
Ai+1 …
Fig. 9. State after one cycle of stepping by the DNA walker. This follows since: (a) A 3 end of the ith walker Wi was assumed to be hybridized with a complementary subsequence Ai of stepper Si , so that the same 3 end of the ith truncated walker T Wi remains hybridized with a complementary subsequence Ai of stepper Si , and further the (i + 1)th walker Wi+1 inherits this hybridization of that 3 end. (b) A 3 end of the (i + 1)th steppingstone subsequence Ai+1 was assumed to be hybridized with a complementary subsequence Ai+1 of stepper Si+1 , so it follows the (i + 1)th walker Wi+1 inherits this
The Design of Autonomous DNA Nanomechanical Devices
29
hybridization of that 3 end. The above described movement of the ith walker Wi to reformed (i + 1)th walker Wi+1 on the road R is always from direction 3 to 5 once ligation occurs, and it is very unlikely to be reversed after that. The above discussion of the feasibility of movement in the 3 direction can be summarized as follows:. We assumed the situation STATE(i) where: (a) walker Wi has the 3 end of Gi hybridized to steppingstone Ai−1 and the 3 end of Hi hybridized to steppingstone Ai , and also (b) the steppingstone Ak subsequence is hybridized with a complementary subsequence Ak of stepper Sk , for each k, where k < i − 1ork > i. The above discussion has demonstrated that given STATE(i), and then in an expected constant number of phases, it is feasible for us to have a movement in the 3 direction on the road to STATE(i+1). But this does not complete our description of all possible movements of the walking DNA construction. Feasible Reverse Movements. The above does not ensure the movement is only in the 5 direction along the road. In the above subsection titled “Restriction Enzyme Cleavage of the Walker” we described a pair of products (P1) and (P2) that can result from the use of the restriction enzymes described there. (To simplify the description of 3 movements, we temporarily ignored other possible products in that above discussion.) We now observe that the walker actually has two possible (dual) restriction enzyme recognition sites, so dual use of the two restriction enzymes defined there also can result in: (P1 ) A partial duplex, consisting of the ith stepper Si (still attached to the ith steppingstone Si ) with th an ssDNA overhang (Ci−1 )R at one 3 end, or (P1 ) A (i − 1) truncated walker th T Wi−1 (still attached to the (i − 1) steppingstone Si−1 ) consisting of a partial duplex with an ssDNA overhang ( C i−1 )R at one 3 end. By a similar argument to the above, it can easily be shown: there is also a feasible movement of the walker in the 5 direction on the road from STATE(i) to STATE(i-1). By symmetry, both these possible movements have equal likelihood. Summarizing, we have shown that there are two equally likely movements: (forward) in the 3 direction on the road from STATE(i) to STATE(i+1), and (reverse) in the 5 direction on the road from STATE(i) to STATE(i-1). Expected Drift Via Random Translational Movement and the Use of Latching. We have shown that the resulting movement forms a random, bidirectional translational movements in both directions along the road. Due to the symmetry of the construction, both translational movements would have equal probability in either direction. It is well known (see Feller [F82]) from the theory of random walks in 1 dimension, that the expected deviation after n steps is √ O( n ). We can easily modify the above design to include a “latching mechanism” that fixes the wheels position at specified locations along the road. This can be done by appending to each 3 end of the walker an additional “latching” sequence and also inserting the complements of these “latching” sequences at a specified pair of locations along the road, which can fix (via their hybridization) the walker’s location once the locations are reached and these “latching” hybridizations occur.
30
3
John H. Reif
Our Rolling DNA Device
It is an interesting question whether bidirectional autonomous motion can be achieved without use of DNA ligase or any restriction enzyme and also without changes in the environmental condition of the system. Here we answer the question positively. We give a description of a DNA device (see Figure 1b), that we call Rolling DNA, which achieves bidirectional autonomous motion, without use of DNA ligase or any restriction enzyme and also without changes in the environmental condition of the system. The motion is random and bidirectional, forming a random walk across a DNA strand. Overview of our Rolling DNA Construction. Let A0 , A1 , B0 , B1 each be distinct oglionucleotides of low annealing cross-affinity, consisting of L (L R R R R typically would be between 15 to 20) bases pairs, and let A0 , A1 , B 0 , B 1 each be their respective reverse complements. Let a0 , a1 be oglionucleotides derived from A0 , A1 by changing a small number of bases, so their annealing affinity R R with A0 , A1 respectively is somewhat reduced, but still moderately high. A R hybridization between A0 and reverse complementary sequence A0 (or between R A1 and reverse complementary A1 ) will be called a strong hybridization, where R as a hybridization between a0 and A0 R (or between a1 and A1 ) will be called a weak hybridization. We assume that at the appropiate temporature, strong hybridization will be able to displace a weak hybridization. We now define (using descriptive names) some DNA strands that will be of use: (i) The road (See Figure 10) consists of an ssDNA with a0 , a1 , a0 , a1 , a0 , a1 , . . . in direction from 5 to 3 , consisting of a large number of repetitions of the sequences a0 , a1 .
a0
a1
a0
a1
a0
a1 … …
Fig. 10. The DNA wheel’s road. R
R
R
R
(ii) The wheel consists of a cyclic ssDNA of base length 4L with A0 , A1 , A0 , A1 in direction from 5 to 3 ; this corresponds to A1 , A0 , A1 , A0 in direction from 3 to 5 . (Note: in the following we will illustrate the wheel with the subsequences at the top of the wheel labeled in the 5 to 3 direction, and the subsequences at the bottom of the wheel labeled in the 3 to 5 direction.) The wheel has two distinguished positions with respect to the road: (0) A type 0 wheel position, as illustrated on the left in Figure 11 , where two of the wheel subsequences A0 , A1 are weakly hybridized to a consecutive pair of subsequences R R a0 , a1 on the road. (Note that the left in Figure 11 lists A1 , A0 at top of the circular DNA wheel in the 5 to 3 direction, where as the second pair below the wheel are written in the opposite 3 to 5 direction as A0 , A1 . Also, note that for
The Design of Autonomous DNA Nanomechanical Devices
31 R
R
sake of simplicity in the left in Figure 11 illustration the subsequences A1 , A0 at the top of the wheel are illustrated as not hybridized to any other sequences, but in fact they may also be weakly hybridized to a further consecutive pair of subsequences a0 , a1 of the road.) (1) A type 1 wheel position, as illustrated on the right in Figure 11 , where two of the wheel subsequences A1 , A0 are weakly hybridized to a consecutive pair of subsequences a1 , a0 on the road. (Note again R R that the right in Figure 11 lists A0 , A1 at top of the circular DNA wheel in the 5 to 3 direction, where as the second pair below the wheel are written in the opposite 3 to 5 direction as A1 , A0 . Also, again note that for sake of simplicity R R in the illustration on the right in Figure 11 the subsequences A0 , A1 at the top of the wheel are illustrated as not hybridized to any other sequences, but in fact they may also be weakly hybridized to a further consecutive pair of subsequences a1 , a0 of the road.)
a0
A 1R
A 0R
A0
A1
a1 a0
a1
A 0R
a0
a1 …
Step
…
… a0
A 1R
A1
A0
a1
a0
a1
a0
a1 …
Fig. 11. One step of the wheel’s movement. Note In the Figure 11 illustration the binding of the wheel with the road has been simplified; the wheel DNA strand would in fact be topologically linked (intertwined) with the road strand of DNA. Avoiding Unwanted Interactions. To ensure there is no interaction between a wheel and more than one distinct road at a time (e.g., to ensure the wheel is not sandwiched between two road strands), we use a sufficiently low road concentration and solid support attachment of the roads. To ensure there is no interaction between a road and more than one wheel, we use a sufficiently low wheel concentration. Random Translational Movement Fueled by Heat Energy. Note that the kinetics (similar to those occurring in branch migrations classically found in Holiday junctions with exact symmetry, and very well understood), will allow for a slow rate of random movements of the wheel in direction 5 to 3 or its reverse, resulting in transitions between these two position types. Note that these translational movements would be in both directions along the road. Due to the symmetry of the construction, both translational movements would have equal probability in either direction. √ As noted in the previous section, the expected deviation after n steps is O( n ). Again, it is possible to modify the above design to include a “latching mechanism” that fixes the wheels position at specified locations along the road (e.g., by hybridization with an additional pair of complementary ssDNA strands inserted into in the wheel and also at
32
John H. Reif
a specified pair of locations along the road, which can fix the wheel’s location once the locations are reached and these annealing occur). In each such step of translational movement, the wheel will simultaneously rotate around its center by 2π/4 = π/2 radians. Again, due to the well-known secondary structure of B-form dsDNA (rotating 2Π radians every approxamately 10.5 bases), it follows that the wheel will also rotate around the axis of the road by approximately L2π/10.5 = Lπ/5.25 radians. Hence the above Rolling DNA construction, even without the further elements described below, can be viewed as executing a very simple type of autonomous motion, which is both translational and rotational, fueled by kinetic (heat) energy. (The physics literature is full of schemes – some possibly violating the laws of thermodynamics, and others theoretically feasible but of very limited use - for harnessing heat energy to fuel nanomechanical motion. For a feasible method using heat energy, see [HLN01].) However, by the laws of thermodynamics, this random autonomous motion will eventually reverse itself. Hence, we feel it would likely be too slow to be of use if it is fueled only by heat energy, and we do not feel it could do useful work. We next face the challenge of accelerating this random walk movement via some other energy source. Accelerated Random Movement Fueled by DNA Hybridization. Our construction, further detailed below, will provide for an acceleration of this random walk movement, by the use of fuel DNA strands, which provide a facility of energy exchange. This initial conformation of the fuel DNA is a state, which temporarily traps its hybridization energy. We will describe the application of DNA catalyst techniques for liberating DNA from these loop conformations, and harness their energy as they transition into lower energy conformations. (Note: We wish to emphasize that the idea of using fuel DNA strands and hybridization catalysts to generate a sequence of motions is not a new idea; it was used by Yurke and Turberfield [YTM+00,YMT00,TYM00] to demonstrate a series of DNA nanomechanical devices such as their DNA tweezers. However, to induce repetitions of the motions by their DNA devices, their devices required external environmental changes; in particular, the use of biotin-streptavidin beads.) The main difference here from that prior work is that here we require no external environmental changes to induce repetitions of the motions by our DNA devices. Instead, we will gradually consume the energy of the DNA fuel loop strands. (This was suggested by Turberfield as a possible mechanism for obtaining autonomous motion.) Details of Our Device Construction. (Note: in the following we will illustrate the fuel strands with the subsequences at the top of the stem loops labeled in the 5 to 3 direction, and the subsequences at the bottom of the stem loops labeled in the 3 to 5 direction.) We define: the type 0 primary fuel strand, as illustrated on the left in Figure 12, consisting of an ssDNA of base length 4L R with A1 , A0 , B0 , A1 . Initially, we assume an initial loop conformation (prepared in a distinct test tube from the complementary fuel strand) of the type 0 primary fuel strand, as illustrated in the right in Figure 12, with its 5 end segment
The Design of Autonomous DNA Nanomechanical Devices
33
R
Ai annealed to its 3 end segment Ai and its third segment B i annealed to an R additional strand B i (which we call its protection segment). A1
A1
A0
B0
A 1R
Hybridization
A0
A1
B0R B 0R
at the ends of the primary fuel strand.
Fig. 12. The primary fuel strand. A type 0 complementary fuel strand, as illustrated on the left in Figure 13, R R R consists of an ssDNA of base length 4L with A1 , B 0 , A0 , A1 .Similarly, we assume the following initial loop conformation of the type 0 complementary fuel strand, as illustrated in the right in Figure 13, with its 5 end segment Ai R annealed to its last segment AR i and its third segment Ai is annealed to an additional strand Ai (which we call its protection segment). (The type 1 primary fuel strands and type 1 complementary fuel strands are defined identically to the type 0 primary and complementary fuel strands, respectively, but with the subscripts 0 and 1 exchanged.)
B 0R
A1 A1
Hybridization at the ends of the fuel strand.
A0
A0
Fig. 13. The type 0 complementary fuel strand. Energetics of the Fuel Strands. Note that the whole complementarity of the primary and complementary fuel strands of a given type implies that the duplex DNA resulting from their complete hybridization has lower free energy. So eventually, over a sufficiently long time interval, the free energy will drive these two species to a double stranded duplex, which is their lowest energy equilibrium state. (For example, the Seeman lab has previously demonstrated [LGM+92] that when two 4-arm junctions are mixed together at an appropriately high temperature, and cooled, they will go to 4 duplex.) The duplex DNA consisting of the complete hybridization of the type 0 primary and complementary fuel strands is as given in Figure 14. (The duplex consisting of the complete hybridization of the type 1 primary and complementary fuel strands is identical, but with the 0 and 1 subscripts exchanged.) However, we are concerned with the special case where the primary
34
John H. Reif
A1
A0
A1
A0
B0 B0
A 1R
A1R
Fig. 14. Complete hybridization between the fuel strands. fuel strands and the complementary fuel strand are prepared separately to form the initial conformations define above, By setting a sufficiently low temperature, that equilibrium duplex state can be made to take any given time duration to reach on the average. So we will use an appropriately chosen sufficiently low temperature to ensure that initially, the primary and complementary fuel strands of the same type will each hold its own state and are not likely to anneal to each other to form a duplex state for say 5 hours on the average. Many cycles of motions described below will then be feasible within this limited time interval. The Sequence of Events of a Feasible Movement. Now suppose the wheel is in type 0 position with respect to the road. Observe that the 0th primary fuel strand can interact with the wheel in the type 0 position by the following hybridizations: (i) First a hybridization of the second segment A0 of the 0th primary fuel strand R with the reverse complementary segment A0 of the wheel, resulting in the conformation illustrated on the left in Figure 15. (Note that if one or both of the subsequences A1 , A0 at the top of the wheel were previously weakly hybridized to a further consecutive pair of subsequences a1 , a0 on the road, then these weak hybridizations will be displaced by the stronger hybridization of the second segment a0 of the 0th primary fuel strand with the reverse complementary segment R A0 of the wheel.) (ii) Then that single segment hybridization extends to a hybridization of two first segments A1 , A0 (in the 3 to 5 direction) of the 0th primary fuel strand R R with the consecutive reverse complementary segments A1 A0 (in the 3 to 5 direction) of the wheel. (Note again that the previous weakly hybridization of these wheel subsequences with subsequences of the road, will be displaced by the strong hybridization of subsequences of the primary fuel strand with the reverse complementary segment s of the wheel.) (iii) This displaces the prior hybridization of segment A1 of the wheel strand with road segment a1 (which recall is of lower energy). As a consequence of this: (a) The wheel moves by one segment in the 5 direction along the road, effecting a transition of the state of the wheel from the type 0 position to type 1 position. (b)This also displaces the prior hybridization of the 5 end segment A1 with its R 3 end segment A1 of the primary fuel strand, which now is exposed. This results in the conformation illustrated on the right in Figure 15. Next, a type 0 complementary fuel strand consisting of an ssDNA of base length R R 4L with A1 , B 0 , A0 , AR 1 (in the 3 to 5 direction) is now be susceptible to hybridizations with reverse complementary subsequences of the type 0 primary
The Design of Autonomous DNA Nanomechanical Devices
35
Wheel rotation due to displaced hybridization with primary fuel strand.
Fig. 15. A rotation of the DNA wheels. fuel strand, first at that fuel strand’s newly exposed 3 end segment AR 1 and then at B0 . This results in the conformation illustrated on the left in Figure 16.
A 0R
Hybridization between primary & complementary fuel strands.
… a0
A 1R
A1
A0
a1
a0
a1
a0
a1 …
Fig. 16. Hybridization of the DNA fuel strand withthe wheel. We will show below that the formation of a type 0 fuel strand duplex removes the type 0 fuel strands from the wheel, completing the step, as illustrated on the right in Figure 16. (Also, note that for sake of simplicity, in the illustration R R on the right in Figure 16, the subsequences A0 , A1 at the top of the wheel are illustrated as not hybridized to any other sequences, but in fact they may also be weakly hybridized to a further consecutive pair of subsequences a1 , a0 of the road.) The type 0 fuel strand duplex consists of the mutual hybridization of the entire type 0 primary fuel strand with the type 0 complementary fuel strand, as illustrated in the left in Figure 17. Its formation removes the type 0 fuel strands from the wheel. The same resulting duplex of the type 0 fuel strands is also illustrated on the right in Figure 17(it is flipped top to bottom and left to right), so it can be compared with the prior illustrations of the type 0 primary fuel strands:
A1
B 0R
A 0R
A 1R
A1
B0R
A0R
A1R
FLIP
A1
A0
A1
A0
B0 B0
Fig. 17. Flipping of the DNA fuel strand.
A 1R
A1R
36
John H. Reif
We conclude that: (a) There is a feasible transition of the state of the wheel from type 1 position to type 0 position driven by the fuel strands of type 0, where the wheel moves by one segment in the 5 direction along the road. (b) Also, there is also a similarly feasible transition of the state of the wheel from a type 0 position to type 1 position driven by the type 1 fuel strands, where again the wheel moves by one segment in the 5 direction along the road. (This is almost exactly the same as described above, but with 0 and 1 reversed.) Other Feasible Movements. The above does not ensure the movement is only in the 5 direction along the road. In fact, there are multiple other feasible interactions of the wheel with the fuel strands. By a similar argument, it can easily be shown: (c) There is a feasible transition of the state of the wheel from type 1 position to type 0 position driven by the type 0 fuel strands, where the wheel moves by one segment in the 3 direction along the road. (d) There is a feasible transition of the state of the wheel from a type 0 position of to a type 1 position driven by the type 1 fuel strands, where the wheel moves by one segment in the 3 direction along the road. (e) For each i=0, 1, there is a feasible hybridization of the exposed (top) portion of the wheel in a type i position with a fuel strand that makes no transition of the state of the wheel (the wheel remains in a type i position, though the fuel strand is transformed into its duplex state), so the wheel stalls for a moment in its movement along the road. The Accelerated Random Bidirectional Movement of the Wheel. Hence the movement of the wheel with respect to the road remains a random walk with either direction or a momentary stall possible on each step with fixed probability. By symmetry in the construction, it can be shown that the likelihood of each direction (from 5 to 3 , or its reverse) of movement is equally likely. Recall again that for unbiased random walks √ in 1 dimension, that the expected translational deviation after n steps is O( n ). However, the fuel strands appear to considerably accelerate the rate that steps of this random walk are executed (as compared to random movements fueled by kinetic (heat) motion). Hence the acceleration in the rate of these transitions may be of use, and the above has the potential of being feasible design of an autonomous bidirectional DNA nanomechanical device without use of DNA ligase or restriction enzymes.
4
Conclusion
A key open problem is to design and demonstrate a DNA Device achieving unidirectional movement (either translational or rotational). We conjecture such as device will need to use irreversible reactions (e.g., ligation). Acknowledgments. We wish to thank Tingting Jiang, Thom Labean, and Hao Yan and Peng Yin, for their valuable and insightful comments that led to many improvements in this paper. As stated above, Turberfield proposed to us the use of DNA fuel loop strands to provide energy for autonomous motion by DNA devices and some possible mechanisms to use them, but these were distinct from what we have presented.
The Design of Autonomous DNA Nanomechanical Devices
37
References [BPA+01] Benenson, Y., T. Paz-Elizur, R. Adar, E. Keinan, Z. Livneh, and E. Shapiro, Programmable and autonomous computing machine made of biomolecules. Nature, 414, 430 - 434, (2001). [F82] Feller, W., An Introduction to Probability Theory and Its Applications, John Wiley & Sons, New York, (1971) [HLN01] T. Humphrey, H. Linke, and R. Newbury, Pumping Heat with Quantum Ratchets, to appear in Physica E (2001), cond-mat/0103552. [LYK+00] T. H. LaBean, Hao Yan, Jens Kopatsch, Furong Liu, Erik Winfree, John H. Reif, Nadrian C. Seeman. “Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes.” J.Am.Chem.Soc. 122, 1848-1860(2000). [LWR00] T. H. LaBean, E. Winfree, and J.H. Reif, Experimental Progress in Computation by Self-Assembly of DNA Tilings, Gehani, A., T. H. LaBean, and J.H. Reif, DNA-based Cryptography, Proc. DNA Based Computers V: Cambridge, MA, June 14-16, 1999. DIMACS Volume 54, edited by E. Winfree and D.K. Gifford, American Mathematical Society, Providence, RI, pp. 123-140, (2000). URL: http://www.cs.duke.edu/∼reif/paper/DNAtiling/tilings/labean.pdf [LGM+92] M. Lu, Q. Guo, L.A. Marky, N.C. Seeman and N.R. Kallenbach, Thermodynamics of DNA Chain Branching Journal of Molecular Biology 223, 781-789 (1992). [MLR+00] C. Mao, T. LaBean, J.H. Reif and N.C. Seeman, Logical Computation Using Algorithmic Self-Assembly of DNA Triple Crossover Molecules, Nature 407, 493-496 (2000). [MSS+99] C. Mao, W. Sun, Z. Shen and N.C. Seeman, A DNA Nanomechanical Device Based on the B-Z Transition, Nature 397, 144-146 (1999). [RLS01] J.H. Reif, T.H. LaBean, and N.C. Seeman, Challenges and Applications for Self-Assembled DNA Nanostructures, Proc. Sixth Inter.l Workshop on DNA-Based Computers, Leiden, The Neth., June, 2000. DIMACS Ed. by A. Condon and G. Rozenberg. Lecture Notes in CS, Springer-Verlag, Berlin Heidelberg, vol. 2054, 2001, pp. 173-198. http://www.cs.duke.edu/∼reif/paper/SELFASSEMBLE/selfassemble.pdf [R01] J. H. Reif, DNA Lattices: A Programmable Method for Molecular Scale Patterning and Computation, to appear in the special issue on Bio-Computation, Computer and Scientific Engineering Journal of the Computer Society. 2001. URL: http://www.cs.duke.edu/∼reif/paper/DNAlattice/DNAlattice.pdf [S99] N.C. Seeman, DNA Engineering and its Application to Nanotechnology, Trends in Biotech. 17, 437-443 (1999). [WLW98] Winfree, F. Liu, L. A. Wenzler, and N.C. Seeman, Design and Self-Assembly of Two-Dimensional DNA Crystals, Nature 394, 539-544 (1998). [YZS+02] H. Yan, X. Zhang, Z. Shen and N.C. Seeman, A robust DNA mechanical device controlled by hybridization topology, Nature, 415,62-65, 2002. [YTM+00] Yurke, B., Turberfield, A. J., Mills, A. P.Jr, Simmel, F. C. & Neumann, J. L. A DNA-fuelled molecular machine made of DNA. Nature 406, 605-608 (2000).
Cascading Whiplash PCR with a Nicking Enzyme Daisuke Matsuda1 and Masayuki Yamamura2 1
2
Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology, 4259 Nagatsuda, Midori-ku, Yokohama 226-8502 Japan; [email protected] CREST, Japan Science and Technology Corporation(JST) and Interdisciplinary Graduate School of Science and Engineering, Tokyo Institute of Technology; [email protected]
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.
1
Introduction
Whiplash PCR(WPCR) was proposed by Hagiya et al, as a unique mechanism to realize autonomous inference machines with single strand DNAs forming hairpin structures [1]. Early WPCR required a certain thermal control like normal PCR. Sakamoto et al. established an isothermal protocol so that DNA molecules act as completely autonomous ways without any outside control [2]. They also proposed an elegant input method for WPCR[3]. WPCR is used not only in abstract computation but also in various applications. Wood et al. used WPCR to represent strategies for game in their research on evolving intelligent agents[4]. Yamamura et al. proposed a memory state copy procedure with WPCR in their research on aqueous computing with PNAs[5]. WPCR has a difficulty called back annealing that the active edge of DNA will hybridize already processed sites more frequently than expected ones. Rose et al. proposed a scheme to inhibit back annealing with bis-PNA. Although the step size will be increased, it is not easy to extend it only with intramolecular activity. This paper proposes a scheme to cascade results of WPCR from molecules to molecules. We expect to ease the difficulty on the step size and also expect new applications by introducing intermolecular activities. This paper consists of 4 sections. Section two proposes a scheme to cascade WPCR with a nicking enzyme. Section three shows preliminary experiments to examine feasibility of proposed idea. Section four discusses on practical and further issues. M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 38–46, 2003. c Springer-Verlag Berlin Heidelberg 2003
Cascading Whiplash PCR with a Nicking Enzyme
2
39
Sheme to Cascade WPCR
We designed a scheme to cascade WPCR by using a nicking enzyme. 2.1
Nicking Enzyme
TypeII and TypeI restriction enzymes are useful in DNA engineering because they cleave DNA at a specific site. Most restriction enzymes catalyze doublestranded cleavage on DNA substrates. But there are some proteins called nicking enzymes that cleave only one DNA strand, and introduce a nick into the DNA molecule. We used N.BstNBI as a nicking enzyme[7]. It recognizes a nonpalindromic sequence,5’-GAGTC- 3’, and cleaves only on the top strand 4 base pairs away from its recognition sequence (5’-GAGTCNNNNˆN-3’). 2.2
Output Reaction and Cascading
Figure1 shows the scheme to cascade results of WPCR from molecules to molecules. In order to cascade WPCR, we must prepare a DNA sequence with a special output site. In final step of WPCR, molecular machine has an output fragment along with a recognition sequence of a nicking enzyme. The nicking enzyme makes nick between the output fragment and the recognition sequence. Finally, the output fragment leaves the molecular machine. It can be considered that the output fragment is new data fragment that defines the state of a system. So, the state of a system is updated because the output fragment joins the set of data fragments. An ssDNA fragment can be used as inputs for other molecular machines[3]. An data fragment consists of two parts, paste part and definition part. The paste part hybridizes to the 3’-end of a rule region, and an initial primer is appended to the 3’-end of the rule region by polymerization using the definition part as a template. The extended rule region can work as a molecular machine for next WPCR. At this point, rule regions have no complementary sequence of definition part.
3
Preliminary Experiments
We designed preliminary experiments to examine the feasibility of proposed idea. 3.1
Mateirials and Methods
Molecular Machine. The DNA sequences used in this paper are listed in Table1.The molecular machine Tran3, in the form shown in Figure2, was commercially synthesized by greiner bio-one. Since the recognition sequence of the enzyme usually contains all kinds of basis (A, T, C, G), C18-spacer is used as a stopper in Tran3. And it can make enzymatic reaction to Tran3 possible. s4 that is complementary strand of s4 plays the part as an output fragment.
40
Daisuke Matsuda and Masayuki Yamamura
5VCVGQH5[UVGO
4WNGTGIKQPU 4WNG 4WNG
&CVCHTCIOGPVU
4WNGP
&CVCC
G
&CVCD &CVCP
H
C
F KPKVKCNRTKOGT
1WVRWVHTCIOGPVU
(KPCNUVGRQH92%4 TGEQIPKVKQPUGSWGPEG
D
QWVRWVHTCIOGPV
E
Fig. 1. The scheme to cascade results of WPCR from molecules to molecules. (a) A molecular machine in an initial state starts WPCR. (b) The nicking enzyme nicks the molecular machine between the output fragment and the recognition sequence. And the output fragment leaves the molecular machine. (c) The Molecular machine restores the output fragment. (d) The output fragment is added into the set of data fragments that define the state of a system, and new state is formed.(e) One of rule regions was paired with one of data fragments. (f) An initial primer is appended to the 3’-end of the rule region by polymerization using the data fragment as a template.
No s0 s1 s2 s3 s4 s5
Sequence CCGTCATCTTCTGCT TACCCTCCCTCACTT CGTCCTCCTCTTGTT GCTTGACTC CATTTCTGGCTCGTC TCGTGCCGTTCGTCCATTTCTGGCTCGTC Table 1. DNA sequences used in this paper
Cascading Whiplash PCR with a Nicking Enzyme
U
U
U
U
U
U
U
41
U
5VQRRGT
Fig. 2. The structure of Tran3. s3 contains the recognition sequence of the nicking enzyme N.BstNBI. And Tran3 is nicked between s3 and s4.
Output Reaction from WPCR. At first, three successive transitions were performed in a reaction mixture containing Tran3 (7pmol), dNTP (60µmol each), Bst DNA Polymerase (4 units, BioLabs inc.), Bst DNA Polymerase buffer, and N.BstNBI buffer. The thermal cycle of WPCR was 64 for 1 min, shift up to 80 in 1 min, 80 for 5 min[3]. And the WPCR consists of 8 reaction cycles. Secondly, the reaction mixture that had undergone WPCR was incubated at 64 for 90 min with the addition of N.BstNBIand the template s4-s5. In this experiment, output reaction is separated from WPCR, so we called this reaction ”separated output reaction”. separated output reaction is a control reaction. In this reaction, two partical reactions(WPCR and output reaction) are performed separately. N.BstNBI and the template s4-s5 were poured into the reaction mixture before WPCR, were used in isothermal and thermal output reaction from WPCR. In contrast to separated output reaction, ”thermal output reaction” underwent two partical reactions continuously. And ”isothermal output reaction” were performed at 64 for 90 min. 3.2
Results
WPCR. The transition products were analyzed on a denaturing 10% polyacrylamide gel stained with ethidium bromide (Figure4). As the result of three successive transitions, it is expected that the reaction mixture contain three kinds of product (Figure3), and Figure4 shows that. Therefore, the molecular machines completely underwent three successive transitions and C18 spacer plays the part as the stopper perfectly. Output Reaction from WPCR. The product of third transition has the double stranded recognition sequence of N.BstNBI, that makes nick between the output fragment s4 and s3. s4 leaves molecular machine, and it plays the part as the primer of s4-s5 that is a template of the output product(Figure5). There is not so great difference among the results of output reaction from WPCR under three conditions (Figure6).
4
Discussion and Conclusion
We proposed a scheme to cascade WPCR from molecules to molecules, and showed preliminary experiments.
42
Daisuke Matsuda and Masayuki Yamamura
U
U
U
U
U
=5VCVG? U
U
U
=5VCVG?
U
U
U U
U
U
U
U
U U
U
U
U
U
U
U
U
=5VCVG?
U U
Fig. 3. The products of the transitions. State1 is the product of first transition, State2 is that of second transition, and State3 is that of third transition.
/
Fig. 4. Gel electrophoresis of the transition products. Lane1 underwent no transition phase. Lane2 underwent WPCR. The band of lane1 shows State1. Lane2 shows State2 (lower band) and State3 (upper band).
=5VCVG?
U
U
U
U
PKEM DGVYGGPUCPFU
=QWVRWVUGSWGPEG? U
U
GZVGPF
=QWVRWVRTQFWEV? Fig. 5. The model of output reaction
Cascading Whiplash PCR with a Nicking Enzyme
/
43
/
C
Fig. 6. The results of output reaction from WPCR. This shows the marker output product (laneM2), the output product of separated output reaction (lane1), that of thermal output reaction (lane2), and that of isothermal output reaction (lane3).
4.1
Discussion about Preliminary Experiments
Since the temperature condition of output reaction and that of incubation phase in WPCR are the same, the output reaction is considered as an extended reaction of WPCR. Therefore, it is natural that the output reaction is performed as an autonomous reaction, and that it does not make much difference whether the efficiency of the autonomous output reaction or that of separated output reaction. And those experiments show that qualitatively. As a result of continuous production of output fragments, the output reaction has the specialty of amplification. But, the pilot experiment of output reaction qualitatively shows that the concentration of the output products tends to converge (data not shown). This means that equilibrium between divorced output fragments and back-annealed output fragments is formed. We suppose the concentration of the output products is decided by two factors that are the concentration of the molecular machines in final step of WPCR and this equilibrium. In order to test this possibility, we hereafter will have to do quantitative analysis. The output product of isothermal output reaction was observed. In previous paper[2],On the contrary, incubation at 80 is recommended because products of transitions are not observed under the conditon at 64. The differences between this paper and previous paper are the polymerase used in experiment and the target observed. Since the target in this paper is the double stranded DNA and is amplified by output reaction, the efficiency of detection is improved. We suppose
44
Daisuke Matsuda and Masayuki Yamamura
those two factors makes observation of WPCR under the condition of 64 possible. In order to say incubation at 64 performs WPCR strictly, we hereafter will have to observe products of transitions.
C=+(##0&$6*'0%?
D=+(##0&$6*'0%? #
# C
$ D
D
C
D UVQRRGT
C
$ D
D
TGEQIPKVKQPUGSWGPEG
%
D
D
% D
C
C
D
TGEQIPKVKQPUGSWGPEG
C
# C
D
D
$
D
D
D
D
% %
%
D
C
D
C
=#CPF$? #
$ D
D
D
D
C
D
C
D
C
D
D
% %
%
%
D
% =#CPF$?
QWVRWVTGCEVKQP %
% %
D
%
D
Fig. 7. Ideas to realize [IF A AND B THEN C] and [IF ¬A AND B THEN C]. The State of system is defined by rule molecules, A and B.
Cascading Whiplash PCR with a Nicking Enzyme
4.2
45
Further Issues
We have a plan to apply proposed method to implement an expert system for medical diagnosis. A molecular machine is synthesized from rule region and data fragment, each concentration of synthesized molecular machines depends on that of data fragments. We expect the concentration of each data fragments will work as the certainty factor of expert systems. For example, we show two concrete ideas to realize logical operation in Figure7. These operations are performed according to the probability that depend on each data fragment concentrations, and the concentration is used as the certainty factor in such meanings. The state of a system is defined by data fragment A and B. (a) shows an idea to realize [IF A AND B THEN C]. Data fragment C is outputted by molecular machine when data fragment A and B exist in a system. (b) shows an idea to realize [IF ¬A AND B THEN C]. In this idea, C is outputted by molecular machine under existence of B. The output of C is blocked by existence of A. Therefore, when both of A and B exist, outputs of C decreases gradually. That is, The output of C can be ignored comparatively if it observed when time fully passes. Consequently, the higher the certainty of A is, the lowwer the certainty of C becomes. We have proposed a scheme to cascade WPCR, and shown a reliability study to produce output fragments by a nicking enzyme. We must develop programinig techniques as discussed, in the next stage. We expect expert systems as nice application field. Direct molecular I/O, that is one of the most fruitful characteristics of DNA computing, leads to micro diagnosis models in Biotechnology on Medicine.
References 1. M.Hagiya, M.Arita, D.Kiga, K.Sakamoto, and S.Yokoyama, ”Towards parallel evaluation of Boolean µ-formulas with molecules”, in (H.Rubin and D.H.Wood,Eds.) DNA Based ComputersIII, (American Mathematical Society, 1999), 57-72. 2. Kensaku Sakamoto, Daisuke Kiga, Ken Komiya, Hidetaka Gouzu, Shigeyuki Yokoyama, Shuji Ikeda, Hiroshi Sugiyama, and Masami Hagiya. State Transitions by Molecules. BioSystems, Vol.52, No.1–3, 1999, pp.81–91. 3. K.Komiya, K.Sakamoto, H.Gouzu, S.Yokoyama, M.Arita, A.Nishikawa, and M.Hagiya, ”Succesive State Transitions with I/O Interface by Molecules”, in (A.Condon and G.Rozenberg, Eds.) DNA Computing, Springer-Verlag LNCS, Vol.2054, (Springer, Berlin, 2001), 17-26. 4. David Harlan Wood, Hong Bi, Steven O. Kimbrough, Dongjun Wu, and Jumghuei Chen. DNA Starts to Lean Poker. DNA7, 7th International Meeting on DNA Based Computers, Preliminary Proceedings, 2001,pp.23-32. 5. Masayuki YAMAMURA, Yusuke HIROTO, and Taku MATOBA. Another Realization of Aqueous Computing with Peptide Nucleic Acid. DNA7, 7th International Meeting on DNA Based Computers, Preliminary Proceedings, 2001,pp.251-259. 6. J.A.Rose, R.J.Deaton, M.Hagiya, A.Suyama: An Equilibrium Analysis of the Efficiency of an Autonomous Molecular Computer, Physical Review E, Vol.65, No.2-1, 2002, 021910, pp.1-13.
46
Daisuke Matsuda and Masayuki Yamamura
7. Richard D. Morgan, Celine Calvet, Matthew Demeter, Refael Agra Huimin Kong.Characterization of the Specific DNA Nicking Activity of Restriction Endonuclease N.BstNBT. Biol. Chem. Vol. 381, 1123-1125 (2000).
A PNA-mediated Whiplash PCR-based Program for In Vitro Protein Evolution John A. Rose1,4 , Mitsunori Takano2 , and Akira Suyama3,4 1
Department of Computer Science, The University of Tokyo, [email protected] 2 Institute of Physics, The University of Tokyo, [email protected] 3 Institute of Physics, The University of Tokyo, [email protected] 4 Japan Science and Technology Corporation (JST-CREST)
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.
1
Introduction
The generation of shuffled dsDNA libraries by DNase I digestion and parallel overlap assembly (POA) (i.e., DNA shuffling) has been established as a powerful means of implementing random recombination between homologous genes [1,2]. Simulations, however predict that this approach is unlikely to be capable of evolving substantially novel protein folds, and that the non-homologous swapping of folded structures (i.e., exon or domain shuffling) is key for optimizing the search of protein sequence space [3]. Many proteins can be modelled as a string of non-overlapping, independently folding elements, or domains, each of which is typically 30-300 residues in length [4]. This has recently prompted the suggestion of protein evolution by in vitro domainal shuffling [5]. In this model, a polynucleotide species encoding for each domain is combined in solution with a set of M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 47–60, 2003. c Springer-Verlag Berlin Heidelberg 2003
48
John A. Rose, Mitsunori Takano, and Akira Suyama
chimeric oligonucleotides, each of which encodes a domain-domain boundary. The iterated annealing, polymerase extension, and dissociation of this strand set (i.e., POA) then results in the production of a library of domain-shuffled dsDNAs. Although this operation preserves domainal integrity during initial shuffling, additional crossover following expression and screening requires either (1) DNase I digestion, which destroys the domainal integrity preserved by the initial process, or (2) a secondary, low-efficiency POA process, in which selected strands are used to implement the iterated extension of a set of added primers. In particular, the efficiency of POA is compromised by the high stability of backhybridized duplexes, relative to extendable hybrids [6,7], in a fashion similar to that reported for Whiplash PCR (WPCR) [8,9]. In a secondary domainal shuffling process, this inefficiency will be exacerbated by both the increased length of backhybrids, and the tendency for strands to stably hybridize away from extendable ends, due to the high sequence similarity conferred by the domainal shuffling strategy. Recombination at the domainal level, which focuses on swapping existing folds, also appears to be too coarse to effect the evolution of substantially new folds. Finally, it is not clear how an iterative DNA shuffling strategy can be designed to ensure that a high proportion of dsDNAs encode promoter and ribosomal binding sites, to facilitate the use of an in vitro system for expression and selection (e.g., RNA-protein fusion [10,11]), which is necessary for overcoming the transfection limit of about 109 strands [12]. In previous theoretical work, the efficiency of WPCR [13] was optimized [8,9], and the resulting architecture, PNA-mediated Whiplash PCR (PWPCR), was adapted to produce an in vitro genetic program for evolving approximate solutions to instances of Hamiltonian Path [14]. For related work, in which WPCR is used to evolve strategies for a simple version of Poker, readers are referred to [15]. In this work, PWPCR is combined with RNA-protein fusion [10,11] to implement a high-efficiency exon shuffling operation. For this purpose, the compact structural unit, or module [16], rather than the domain, is adopted as the basic element of protein structure, so that each shuffled protein represents a walk on a predefined graph, in which each vertex represents a pseudo-module contained in an initial protein set of interest.
2 2.1
Protein Representation The Module Picture of Protein Architecture
The domain, or independently folding unit, is well established as a basic element of protein structure [4]. As pointed out by M. Go, et al. [16,17], however the frequent occurrence of introns within domains belies the view that each exon encodes a domain, and suggests the decomposition of domains into a set of smaller, compact structural unit, or modules, each of which forms a compact structural unit within the larger domain, and corresponds roughly to an exon. Any globular protein with a known 3D structure can be decomposed into an Nterminal to C-terminal sequence of modules, by exploiting either the tendency for module junctions to be buried, or the tendency of modules to form a locally
A PNA-mediated Whiplash PCR-based Program
49
compact unit [17]. Module and exon boundaries have been shown to correlate strongly in ancient proteins [18], supporting the view that ancient conserved proteins were evolved via exon (module) shuffling, as expected by the Exon Theory of Genes [19]. The basic module structure is that of a “unit-turn-unit”, with a length which correlates with the radius of the protein [18]. Typical module lengths vary from 10-25 residues (about half the mean exon length), and are clustered tightly around a mean of 18 residues. Interestingly, this mean length is very close to the optimal length (20 residues) of exchanged segments, reported for simulations of genetic recombination [3]. Longer modules reported for globins (up to 45 residues) are decomposable into a set of shorter modules [20]. The element between the approximate midpoints of adjacent modules (the pseudo-module), which has the general structure of coil-unit-coil, has also been investigated as a basic structural element of proteins [21]. 2.2
The Pseudo-module Generating Graph
The module picture of protein structure suggests that a protein, P which can be decomposed into a N to C-terminal sequence of q + 1 pseudo-modules, may be modelled as a q step tour of the digraph, GP (V, E), composed of q + 1 vertices, V = {Vi : i = 1, . . . , q + 1}, so that Vi represents the ith pseudo-module from P ’s N-terminus, and edges, E = {Ei,i+1 : i = 1, . . . q}, where Es,t is the directed edge between source and target vertices, Vs and Vt , respectively. This pseudomodule graph representation facilitates a discussion of the generation problem for sets of proteins derived from P by various forms of pseudomodule sampling. For instance, the protein set generated by the random sampling of q + 1 pseudomodules from P (colloquially referred to as “shuffling”) corresponds to the set of q-step walks on the fully interconnected graph, GP (V, E † ), with edges, E † = {Ei,j : i, j ∈ {1, . . . , q}}. This model conveniently generalizes to discuss the generation of protein sets by restricted forms of pseudomodule “shuffling”. In particular, it may be desirable to generate a set of proteins by pseudo-module shuffling between (or within) specific regions of P , while other regions remain unshuffled. This constrained sampling on P can be expressed as a set of edges, Es ∈ E † on GP (V, E † ), which preserves the desired pseudo-module adjacencies. The protein set generated under the application of this sampling will then be equal to the set of random walks on the pseudo-module graph, GP (V, Es ). The framework also generalizes straightforwardly to discuss the generation of protein sets by the pseudo-module sampling of multiple proteins. Consider the sampling of a set of n proteins, P = {Pk : k = 1, . . . , n}, each of which can be expressed as a sequence of pseudo-modules, and thus, as a tour of a simple pseudo-module graph, Gk (V (k), E(k)). Furthermore, suppose that each protein, Pk ∈ P is to be sampled subject to an internal sampling constraint, Es (k), and each pair of proteins, Pk , Pk ∈ P is to be sampled subject to the pairwise constraint Es (k, k ), which specifies a set of allowed adjacencies (i.e., a set of edges) between Pk and Pk . The set of proteins which may be generated by means of this sampling procedure is then identical to the set of random
50
John A. Rose, Mitsunori Takano, and Akira Suyama
walks on the pseudo-module graph, GP (V , E ), where V = ∪k V (k), and E = (∪k Es (k)) ∪ (∪k,k Es (k, k )).
3
An In Vitro Genetic Program for Protein Evolution
In this section, an in vitro method is presented for evolving sets of proteins with high affinity for a predefined selection motif, subject to the constraint that each represents a directed walk on a specified pseudo-module graph, GP (V , E ). This method begins with initialization by self-assembly of a set of ssDNAs, each of which encodes a PWPCR program for the generation of a 3’ DNA tail which encodes a walk on GP (V , E ). Initialization is followed by the iterated application of a three step cycle: (1) genotype generation by PWPCR [8] followed by parallel strand conversion to dsDNA, (2) fitness evaluation and selection, by the generation of a set of RNA-protein fusions [10,11] (i.e., the phenotypes), followed by selection based on affinity to an immobilized selection motif, and (3) recombination, using a restriction enzyme-based crossover operation. (a)
_ xt
W as X
_ xs
Y
(b)
PNA (Watson-Crick strand)
at Z
tether H 2 NLys [C C T ]4
Pro
P
_ xi
X
Y
_ Ini
ai Z
as
[ G G A]
4
H[J J T]
_ xt
4
W
af
X
_ T
_ xf
Q
Ini
PNA (Hoogsteen strand)
(c) first edge strand _ _ x2 x 1 a2
initiation strand _ _ Ini a1 x1
a1
_ a1
_ a1
Pro P
second edge strand _ _ x3 x 2 a3
a2
_ _ a2 a2 r-region
_ a3
termination strand _ _ T x 3 Q Ini
a3
_ a3
Fig. 1. PWPCR representation and assembly (see text for details). (a) Generalized edge strand (top), initiation strand (middle), and termination strand (bottom) structure. (b) Targeted PNA2 /DNA triplex formation (at codeword, X). (c) Process of assembly from shorter strands, for a strand which computes the path, V1 → V2 → V3 .
3.1
Initialization
Initialization begins with the construction of four sets of ssDNA strands: (1) an edge strand for each edge, Vs → Vt in the pseudomodule graph of interest, GP (V , E ), where Vs and Vt denote the edge’s source and target vertices, respectively; (2) an initialization strand for each vertex, Vi in GP (V , E ) which is
A PNA-mediated Whiplash PCR-based Program
51
to serve as the initial state of a directed walk on GP (V , E ); (3) a termination strand for each vertex, Vf in GP (V , E ), which may serve as the final state of a directed walk on GP (V , E ); (4) a splinting strand for each vertex in GP (V , E ). Edge strand structure is shown in Fig. 1(a; top structure), where codewords xs , xt , as , and at are edge-specific, while codewords W , X, Y and Z are fixed, for all strands. 5’ to 3’ orientation is indicated by a vertical fin at the strand’s 3’ terminus. An overscore denotes Watson-Crick complementation. as and at identify the source and target vertices of the encoded edge, respectively, and serve to direct the process of PWPCR strand assembly (Fig 1(c)). W and Z encode the 5’ and 3’ halves of one strand of the restriction site of the restriction endonuclease, BseDI (C↓CTTGG) [22], respectively. For convenience, W Z is illustrated as a light, x’ed rectangle. Together, these words enable the directed recombination at this edge (c.f., Sec. 3.4). X, xs , Y , and xt collectively implement the transition, Vs → Vt , by directing primer extension during PWPCR (c.f., Sec. 2). xs and xt are the reverse complements of DNA triplet encodings of the transition’s source and target pseudo-module vertices, respectively. X = (GGA)4 is the target site for formation of a PNA2 /DNA triplex (Fig. 1b), a structure which is known to arrest polymerase extension [23], in order to implement the WPCR/PWPCR operation, polymerization stop. Y = X directs the insertion of word X between words xs and xt , in the extending 3’ tail of the assembled PWPCR strand, which will be used for targeted formation of an additional, backhybridization-inhibiting PNA2 /DNA triplex, during PWPCR. Initiation strand structure is shown in Fig. 1(a; middle structure), where code words xi and ai are strand-specific, while codewords P ro, P , X, Y , Z and Ini are fixed, for all strands. Black oval denotes 5’ biotinylation. P ro encodes a T7 promoter sequence [24] to direct transcription (c.f., Sec. 3.3). P directs primer annealing during PCR. ai identifies the initial vertex specified by the encoded strand, and directs the process of PWPCR strand assembly. X, xi , Y , and Ini collectively serve to initiate PWPCR by directing the appendage of codeword, xi to the 3’ terminus of the fully assembled strand (c.f., Sec. 3.2). Termination strand structure is shown in Fig. 1(a; bottom structure), where xf and af are strand specific, while W , X, T , Y , Q, and Ini are fixed for all strands. af identifies the terminal vertex specified by the encoded strand, and serves to 3’-terminate the process of PWPCR strand assembly. X, T , Y , and xf collectively serve to terminate PWPCR by directing the appendage of the codeword, T to the 3’ terminus of the assembled strand at completion of PWPCR (c.f., Sec. 3.2). Q is a codeword for primer annealing during PCR. Ini encodes a Shine-Delgarno sequence [25], spacer sequence, and start codon, and serves (following transcription) to initiate the translation process (c.f., Sec. 3.3). The splint strand for each vertex, Vi has structure, ai W Zai , where W Z is represented in Fig. 3 as a darkened, x’ed rectangle. Words, ai aid in splinting. The parallel assembly of the initial strand set, which encodes a set of walks on GP (V , E ), is most straightforwardly accomplished by an Adleman-like assembly process [26], implemented by mixing all strands under conditions appropriate for annealing and ligation (T4 DNA ligase). This process is illustrated in
52
John A. Rose, Mitsunori Takano, and Akira Suyama
Fig. 1(c), in the context of the path, V1 → V2 → V3 . In practice, a serial assembly process, beginning with a set of initiation strands, should be more efficient. The elimination of incompletely assembled strands may be accomplished by retaining only the strand set with (a) affinity to Ini, as determined by extraction using the dig-antidig system [27], and (b) a biotinylated 5’ end. The expansion of this architecture to enforce the assembly (and evolution) of PWPCR strands which compute deterministically is discussed in Sec. 5. (a)
Ini
1
Pro P
_ x1
_ Ini a 1
a1
_ x2
_ x 1 a2
a2
_ x3
_ x2
a3
a3
_ T
_ x3
_ Ini a 1
a1
_ x2
_ x 1 a2
a2
_ x3
_ x 2 a3
a3
_ T
_ x3
a2
_ x3
_ x 2 a3
a3
_ T
_ x3
2
x1
Pro P
_ x1
x1
Pro P
_ x1
_ Ini a 1
(b)
a1
_ x 1 a2
_ x2 1
q-1 cycles
2
x3
1
Pro P
_ x1
_ Ini a 1
a1
_ x2
a3
x2
x1
_ _ T x3 Q
3
(c) 4
Pro P
r-region
_ Q
5
Q
Ini
x1
x2
6
_ T x3 T _ Q _ T
Pro P
r-region
Q
Ini
x1
x2
x3 T
Fig. 2. PWPCR-based generation of a dsDNA library (see text for details). (a) The basic PWPCR process. (b) Termination of PWPCR by addition of word, T . (c) Conversion to dsDNA by double primer extension.
3.2
PWPCR-based Generation of a dsDNA Library
The generation of a dsDNA library suitable for expression as a set of proteins on GP (V , E ) is initiated by applying a low salt (20 mM [Na]+ ), excess bis-PNA
A PNA-mediated Whiplash PCR-based Program
53
wash to the initialized ssDNA mixture. This procedure has been reported to result in the rapid attainment of a near unity fractional saturation of dsDNA target sites (codeword X) [28], which is virtually irreversible, at temperatures beneath the PNA2 /DNA melting transition. This set of triplexes will be used to implement polymerization stop. The parallel generation of a protein-encoding 3’ tail for each library strand begins by applying a reaction temperature, Trx which promotes hairpin formation at words, Ini and Ini. As shown in Fig. 2 (a; top structure) for a PWPCR strand encoding the walk, V1 → V2 → V3 , addition of DNA polymerase then results in the self-directed, 3’ extension (horizontal arrow) of each strand, to the adjacent PNA2 /DNA triplex (white oval). This process 3’ appends word X and word xi , which encodes initial (N-terminal) pseudomodule in the strand’s encoded walk (x1 , in Fig. 2). Following extension, the ssDNA mixture is exposed to a low salt, excess bis-PNA wash, which results in the formation of a PNA2 /DNA triplex at word X (Fig. 2(a; middle structure)). As described in [8], this triplex destabilizes each newly extended hairpin, promoting denaturation and renaturation in the configuration required for the next extension (Fig. 2 (a; bottom structure)). The application of q − 1 further cycles of polymerase extension (q = 3, in Fig. 2) and bis-PNA treatment then facilitates the high-efficiency, self-directed appendage of q − 1 additional codewords to the 3’ end of each strand. PWPCR is terminated, for each strand, by the 3’ appendage of a termination codeword, T (Fig. 2(b)). The conversion to dsDNA is accomplished in parallel, for all terminated strands as follows. Bis-PNAs are first denatured and washed (Fig. 2(c), process 3). Unwanted secondary structure is then removed by the annealing and polymerase extension of primer, Q (Fig. 2(c)), process 4), which forms a protecting strand. The annealing and polymerase extension of a second primer T (Fig. 2(c)), process 5), then displaces the protecting strand (Fig. 2(c), process 6), and completes dsDNA conversion. 3.3
Fitness Evaluation and Selection via RNA-protein Fusion
The parallel evaluation and selection of the set of walks on GP (V , E ) represented by the dsDNA library is accomplished in a 7-step process which is essentially identical to the strategy for in vitro selection of proteins by RNA-protein fusion described in [12], which has been experimentally optimized for high efficiency. For clarity, this process (Fig. 3) is described in the context of a strand encoding the short walk, V1 → V2 → V3 . In the first step (Fig. 3(a)), the dsDNA library is used to direct the in vitro synthesis of an mRNA pool, using T7 RNA polymerase [24]. For each dsDNA, transcription is initiated at word, Pro, which encodes a T7 Promoter. Each mRNA transcript (see Fig. 3(b)) is synthesized using the biotinylated strand as the sense strand, and encodes both (1) the r-region, and (2) the triplet code for the walk on GP (V , E ) encoded by the transcribed dsDNA. These two regions are separated by word Ini, which contains a Shine-Delgarno sequence to direct ribosomal binding. Each mRNA transcript is then modified (Fig. 3(b), process
54
John A. Rose, Mitsunori Takano, and Akira Suyama
2) by the addition of a protecting cDNA strand, by the reverse transcriptasemediated extension of the primer, Q. This strand eliminates undesired secondary structure, protects the mRNA transcript’s r-region from specific interaction during affinity-based selection, and copies the r-region into the cDNA protecting strand, which may be conveniently recovered following selection. Next, a short ssDNA strand containing a 5’ puromycin (terminal p), an antibiotic which inhibits translation by mimicking the aminoacyl end of tRNA, is attached to each mRNA’s 3’ end, by splint-mediated ligation (Fig. 3(b), process 3). This group will serve to direct the synthesis of an RNA-protein fusion (RPF) [11] during normal translation.
(a)
T7 RNA polymerase
pro
1
P
x1
Q Ini
r-region
x3
x2
_ T
puromycin
(b)
r-region
P
2
p
RNA transcript x2 x1 Q Ini
x3
_ T
_ Q
3 Protein
5 4 r-region
P
(c)
p
N
Q Ini
x2
x1
_ Q
x3
bound selection motif r-region
P
Q Ini
6
N p
(d)
x3
x1
Pro P
,
7
_ _ Q Ini
(e) Pro P
_ x1
_ _ Ini a 1 a 1 x 2
_ _ x1 a 2 a 2 x3
_ x2 a 3 a 3
_ _ T x 3 Q Ini
Fig. 3. Fitness Evaluation and Selection (see text for details): (a) Transcription; (b) 3’ puromycin attachment; (c) Translation and RNA-protein fusion; (d) Selection by affinity to a bound motif; (e) cDNA recovery and reinitialization by PCR.
A PNA-mediated Whiplash PCR-based Program
55
Translation of the mRNA transcript set (Fig. 3(c), process 4) is accomplished using the E. coli in vitro translation system [29]. For each transcript, translation is initiated by ribosomal binding at the Shine-Delgarno sequence [25] encoded by word, Ini. In the normal course of translation, which proceeds 5’→3’ along the mRNA, the ribosome then pauses at the RNA-DNA interface, allowing the 3’ puromycin to enter the ribosome’s A-site, and be covalently attached by the ribosome to the C-terminus of the nascent peptide, forming a stable RNA-protein fusion (Fig. 3(c), process 5). This process essentially results in the physical linkage of the encoded protein’s genotype and phenotype. The generated protein consists of a pseudomodule sequence, punctuated by short Glycine coils (Gly4 ) generated by the embedded target sequences, X. This minor increase in the length of the coils at pseudomodule boundaries is expected have a negligible impact on the structure and function of the folded protein. In Fig. 3(c), the protein encoded by the path, V1 → V2 → V3 has been expressed as a 3-helix bundle. The RPF library is then subjected to a fitness evaluation and selection procedure (also referred to as screening), based on affinity to an immobilized selection motif (Fig. 3(d), process 6). This motif may be a nucleic acid, protein, or small molecule of interest, such as a transition state analog (TSA) [30]. RPF formation is reported to have negligible impact on the binding specificity of the nascent protein [12]. Following denaturation and purification of the attached set of cDNAs from the selected RPF set (Fig. 3, process 7), the purified cDNA set is PCR amplified using the biotinylated primer, P roP and the 5’ digoxygen-conjugated primer, IniQ. After amplification, which also implements point mutation (albeit somewhat problematically (c.f., Sec. 5)), the resulting dsDNA set is denatured, and the set of digoxygenin-conjugated strands are removed by (anti-dig) antibodies [27]. The remaining strands comprise a biotinylated ssDNA library, each element of which encodes a selected PWPCR program for generating a walk on the pseudo-module graph, GP (V , E ). 3.4
Restriction Enzyme-Based Recombination
Prior to recombination, a subset of psuedomodule-encoding vertices in GP (V ,E ), at which crossover is to be implemented should be identified. Single-point, two parent crossover will then be performed on a subset of the biotinylated ssDNA library, extracted separately for each selected vertex, Vi , by application of the following elementary crossover procedure. For clarity, this basic crossover operation is illustrated in Fig. 3.4 for crossover implemented at V2 , between a strand encoding the path, V1 → V2 → V3 and a second strand (not shown), which encodes a path of the form, Vj → V2 → V4 , where Vj is some vertex in GP (V , E ) other than V2 . The first step (Fig 3.4(a), process 1) is the extraction of a subset of the strands in the ssDNA library which encode a walk that visits Vi , by affinity extraction using the digoxygen-conjugated primer, ai (a2 , in Fig. 3.4(a)). Crossover point formation within the codeword string, ai ZW ai of each strand is then initiated by annealing of primer ai W Zai (Fig 3.4(b), process 2). Restriction with BseDI at the restriction site formed by this process at W Z (crossed box) (Fig 3.4(b), process 3), then results in the division of the strand into a pair
56
John A. Rose, Mitsunori Takano, and Akira Suyama
of restriction fragments, where the biotinylated fragment encodes a partial path ending at vertex i, while the unbiotinylated fragment encodes a partial path beginning at vertex i. The low temperature annealing and ligation of random pairs of biotinylated and unbiotinylated restriction fragments then implements the desired 2-parent, single-point crossover operation at V2 . The viability of each progeny strand (in the sense of encoding a valid, connected walk on GP (V , E )) is ensured by the representation of each parent strand (c.f., Sec. 3.1). In particular, the assembly process ensures that the order of the edges traversed by an encoded walk is identical to the physical ordering (i.e., 5’ to 3’) of the PWPCR rules encoded for executing the traversal, on the strand. Recombination at Vi is completed by strand anchorage, followed by a wash. This elementary crossover operation is to be repeated on a separate extract removed from the ssDNA library for each selected vertex in GP (V , E ), or until the library is exhausted. The merging of all recombined extracts into a single tube completes recombination, and the first round of the genetic program. This process of in vitro evolution should be repeated until a protein having the desired affinity is produced, as determined during fitness-evaluation and selection (screening), or until some predetermined maximum number of rounds have been executed.
_ a2
(a)
Pro P
_ x1
_ _ Ini a1 a 1 x 2
1 _ _ _ x 2 a3 a 3 T x 3 Q Ini
_ _ x 1 a2 a 2 x 3
3 _ _ a2 a2
(b) Pro P
_ x1
_ _ Ini a1 a 1 x 2
2
Pro P
_ x1
_ _ Ini a1 a 1 x 2
_ x1 a 2
_ x3
a2
_ a2
(c)
_ _ _ x 2 a3 a 3 T x 3 Q Ini
_ _ x 1 a2 a 2 x 3
_ _ _ x 2 a3 a 3 T x 3 Q Ini
_ a2
+
a2
_ x4
_ _ _ x 2 a4 a 4 T x 4 Q Ini
4
(d) Pro P
_ x1
_ _ Ini a1 a 1 x 2
_ _ x 1 a2 a 2 x 4
_ _ _ x 2 a4 a 4 T x 4 Q Ini
Fig. 4. Restriction site-based recombination of a PWPCR strand encoding the path, V1 → V2 → V3 , with a strand encoding a path of the form, Vj → V2 → V4 , where Vj is some vertex in GP (V , E ), other than V2 . This operation implemented at common vertex, V2 (see text for details).
A PNA-mediated Whiplash PCR-based Program
4
57
The Efficiency of PWPCR-based Library Generation
The model of PWPCR efficiency reported in [8], which treats the extension of each strand as a Markov chain, and estimates the probability of extension during each effective encounter with DNA polymerase, was applied to estimate the efficiency of library generation by PWPCR. The adopted word lengths were: |xi | = 42 nucleotides (nt) and |X| = |Y | = 12 nt, for a uniform module length of 18 residues; |P | = |Q| = 18 nt; |W | = |Z| = 3 nt; |ai | = 10 nt; |T | = 15 nt; |Ini| = 42 nt. The following modifications were also adopted (values applied in [8] listed in parenthesis): mean pseudomodule codeword GC content = 0.50 (8/15); [Mg2+ ] = 1.0 mM (1.5 mM); PNA target sequence, X = [G2 A]4 (A2 GA2 GA4 ). In [8], the loop lengths of extendable hairpins were modelled by a mean value, which increased as a function of extension number, r. Here, the 5’ to 3’ ordering of each strand’s set of rules for graph traversal allowed the explicit calculation of a loop length for each extendable hairpin, which decreases with r. This is significant, because the extension efficiency is a low order polynomial of the ratio of extendable and backhybridized (i.e., previous) loop sizes.
(b)
1.0 0.8
-2 -3 -4 -55 20
χ(q)
log10 ε r
(a)
5 81 15
r
5
346 73
0.4 0.2 0
77
10
0.6
o
Trx ( C)
0
10
20
30
40
50
q (edges)
Fig. 5. The efficiency of PWPCR-based library generation. (a) Efficiency per strand-polymerase encounter, r vs. extension process, r and Trx ; (b) completion efficiency per strand vs. path length, q (in edges). Fig. 5(a) illustrates the efficiency/effective polymerase encounter, r predicted for a q = 20 implementation (22 extensions), as a function of r and Trx . The first extension (data not shown) is predicted to proceed with nearunity efficiency, at Trx < 71◦ C. The predicted optimal Trx is nearly constant for r > 1, and ranges from 76.5 ◦ C (r = 2) to 77.8 ◦ C (r = 22). For each extension, 1 < r ≤ 22, application of the corresponding optimal Trx is predicted to result in an efficiency of r>1 ≈ 10−2 . Use of a constant Trx = 77.6◦ is predicted to maintain an efficiency of at least 82% of the optimal value, for all r > 1. The simple model of PWPCR kinetics employed in [8] was then applied to estimate the characteristic relaxation time to equilibrium, τ for PWPCR hairpins. In particular, the predictions of an equilibrium model can be expected to be valid only under conditions for which τ < 10tenc , where tenc is the mean time
58
John A. Rose, Mitsunori Takano, and Akira Suyama
between successive polymerase encounters for a given strand. At Trx = 77.6◦ C, predicted relaxation times range from 0.67 sec (r = 2) to 0.052 sec (r = 22), where the variation is due to the decreasing loop size of hairpins implementing successive extensions. The conditions suggested in [8] (27 units of Taq DNA polymerase, with a polymerization cycle time of 60 min), which implement a total of approximately 543 effective encounters/(strand cycle), yielding a mean time between encounters of tenc ≈ 6.7 sec are therefore predicted to just meet the requirement for equilibrium. Fig. 5(b) illustrates the estimated completion efficiency per strand, χ(q), as a function of encoded path length, q (in edges) for a combinatorial PWPCR mixture of 1.2 × 1013 strands, under buffer conditions of [8]. Simulations were performed assuming a uniform reaction temperature of Trx = 77.6 ◦ C, which was predicted to be within 1 C◦ of the optimal Trx for each value of q. As shown, a q = 20 implementation is predicted to complete 84% of the encoded strands, a substantial improvement over [8].
5
Practical Considerations
Based on the simulations presented in Sec. 4, the current method is predicted to be an efficient method of producing massively parallel, recombined gene libraries encoding for proteins shorter than about 600 residues, which compares favorably with the mean protein length of about 350 residues [4]. Although each round of crossover is certain to generate PWPCR strands encoding longer paths, the subset of recombined strands which encodes paths above a fixed threshold length can be removed by size fractionization [27]. The near constancy of the optimal Trx predicted with variations in q also indicates that a single Trx can be selected to implement PWPCR with near uniform efficiency, variations in strand length notwithstanding. A related, and critical issue is the requirement that the thermal stabilities of the set of pseudomodule-encoding DNA words be both approximately uniform, and substantially lower than that of the adjacent PNA2 /DNA triplexes. The uniformity of pseudomodule codeword thermal stability can be ensured by exploiting the degeneracy in the 3rd nucleotide, inherent in the triplet code. Furthermore, as the melting transition of the 10 nt, 20% G/C PNA2 /DNA triplex is reported to occur in a very narrow (5 C◦ in width) temperature range, centered at 85 ◦ C, use of the suggested Trx = 77.6◦ should result in negligible melting of the more stable (12 nt, 67% G/C) triplexes adopted for the current implementation. As pointed out in Sec. 3.3, the current architecture effectively implements point mutation during both PCR (and PWPCR). Each point mutation, however also results in the divergence of the mutated codeword and its matching, unmutated partner, on the strand. Due to the high stability reported for single mismatches in a longer Watson-Crick sequence [31], however this effect should have a negligible impact on PWPCR efficiency, given modest mutation rates. The present implementation does not enforce the assembly or evolution of strands which encode for deterministic PWPCR (i.e., so that each strand encodes
A PNA-mediated Whiplash PCR-based Program
59
for exactly 1 completed protein). If desired, determinism may be enforced in SAT Engine-like style [32], by the codeword assignment, aj = aj , ∀ j ∈ {1, · · · , q + 1}, combined with the use of a fully palindromic restriction site for BseDI (e.g., C↓CTAGG). Hairpins which encode multiple visits to any vertex, Vj will then form very stable hairpin loops at self-complementary words, aj ZW aj , which are then subject to digestion, prior to each round of PWPCR. The downside of this procedure is an increased potential for kinetic trapping in PWPCR hairpins, and a decreased recombination efficiency due to the potential for ligation of biotinylated pairs and unbiotinylated pairs of restriction fragments. Another important issue is the impact on protein structure and function on the Gly4 coils inserted between pseudomodule pairs. Given that these pairs are assumed by the basic model to be punctuated by turns, and glycine is a helixbreaker, the impact of Gly4 insertion on 2◦ structure is likely to be negligible, in general. the impact on 3◦ structure and function appears to be a more complex issue. For coils which primarily provide sufficient flexibility for a turn, a modest length increase is unlikely to impact overall protein functionality. For coils which contain an active residue, on the other hand, both length and placement within the coil may assume greater importance, and will have to be carefully considered during the decomposition of the parent protein into a pseudomodule graph.
Acknowledgements The authors would like to thank M. Hagiya and K. Sakamoto of the University of Tokyo for helpful discussions, and S. Suzuki for help during preparation of the figures. Support provided by a JSPS Postdoctoral Fellowship and Grant-in-Aid, and by JST CREST.
References 1. Stemmer, W., “Rapid evolution of a protein in vitro by DNA shuffling”, Nature 370, 389 (1994). 2. Crameri, A., et al., “DNA shuffling of a family of genes from diverse species accelerates directed evolution”, Nature 391, 288 (1998). 3. Bogarad, L. and Deem, M., “A hierarchical approach to protein molecular evolution”, Proc. Natl. Acad. Sci. USA 96, 2591 (1999). 4. Doolittle, R., “The multiplicity of domains in proteins”, Annu. Rev. Biochem 64, 287 (1995). 5. Kolkman, J. and Stemmer, W., “Directed evolution of proteins by exon shuffling”, Nat. Biotech. 19, 423 (2001). 6. Kaplan, P., “Parallel overlap assembly for the construction of computational DNA libraries”, et al., J. Theor. Biol. 188, 333 (1997). 7. Rose, J., The Fidelity of DNA Computation, Ph.D. Thesis, The University of Memphis, 155 (1999). 8. Rose, J., Deaton, R., Hagiya, M., and Suyama, A., “Equilibrium analysis of the efficiency of an autonomous molecular computer”, Phys. Rev. E 65, Article 021910 (2002); also in V. J. Biol. Phys. 3(2), (2002).
60
John A. Rose, Mitsunori Takano, and Akira Suyama
9. Rose, J., Deaton, R., Hagiya, M., and Suyama, A., “PNA-mediated whiplash PCR”, in Jonaska, N. and Seeman, N. (Eds.), DNA Computing (Springer-Verlag LNCS, Vol. 2340, Springer-Verlag, Berlin, 2002), 104. 10. Nemoto, N., Miyamoto-Sato, E., Husimi, Y., Yanagawa, H., “In vitro virus: Bonding of mRNA bearing puromycin at the 3’-terminal end to the C-terminal end of its encoded protein on the ribosome in vitro”, FEBS Lett. 414, 405 (1997). 11. Roberts, R. and Szostak, J., “RNA-Peptide fusions for the in vitro selection of peptides and proteins”, Proc. Natl. Acad. Sci. U.S.A. 94, 12297 (1997). 12. Liu, R., Barrick, J., Szostak, J., Roberts, R., “Optimized synthesis of RNA-Protein fusions for in vitro protein selection”, Methods Enzymol. 318, 268 (2000). 13. Sakamoto, K. et al., “State transitions by molecules”, BioSystems 52, 81 (1999). 14. Rose, J., Hagiya, M., Deaton, R., and Suyama, A., “A DNA-based in vitro genetic program”, J. Biol. Phys. 28, 493 (2002). 15. Wood, D. H., et al., “DNA starts to learn poker”, in Jonaska, N. and Seeman, N. (Eds.), DNA Computing (Springer-Verlag LNCS, Vol. 2340, Springer-Verlag, Berlin, 2002), 92. 16. Go, M., “Correlation of DNA exonic regions with protein structural units in Haemoglobin”, Nature 291, 90 (1981). 17. Go, M. and Nosaka, M., “Protein architecture and the origin of introns”, Cold Spring Harbor Symp. Quant. Biol. 52, 915 (1987). 18. de Souza, S., “Intron positions correlate with module boundaries in ancient proteins”, et al., Proc. Natl. Acad. Sci. USA , 14632 (1996). 19. Gilbert, W., “Why genes in pieces?”, Nature 271, 501 (1978). 20. Inaba, K. et al., “Structural and functional roles of modules in Hemoglobin”, J. Biol. Chem. 272, 30054-30060 (1997). 21. Inaba, K., Ishimori, K. Imai, K., Morishima, I., “Structural and functional effects of pseudo-module substitution in Hemoglobin subunits”, J. Biol. Chem. 273, 8080 (1998). 22. REBase restriction enzyme database, http://rebase.neb.com. 23. Giovannangeli, C., and Helene, C., “Triplex-forming molecules for modulation of DNA information processing”, Curr. Opin. Molec. Ther. 2, 288 (2000). 24. Milligan, J. and Uhlenbeck, O., “Synthesis of small RNAs using T7 RNA polymerase”, Methods Enzymol. 180, (Acad. Press, 1989), 51. 25. Kozak, M., “Comparison of the initiation of protein synthesis in prokaryotes, eukaryotes, and organelles”, Microbiol. Rev. 47, 1 (1983). 26. Adleman, L., “Molecular computation of solutions to combinatorial problems”, Science 266, 1021 (1994). 27. Sambrook, J., Fritsch, and E., Maniatis, T, Molecular Cloning: A Laboratory Manual, 3rd Ed., (Cold Spring Harbor Press, Cold Spring Harbor, New York, 2001). 28. Kuhn, H., et al., “Kinetic sequence discrimination of cationic bis-PNAs upon targeting of double-stranded DNA”, Nuc. Acids Res. 26, 582 (1998). 29. Ellman, J., et al., “Biosynthetic method for introducing unnatural amino acids site-specifically into proteins”, Methods Enzymol. 202, 301 (1991). 30. Griffiths, A. and Tawfik, D., “Man-made enzymes-from design to in vitro compartmentalisation”, Curr. Opin. Biotech. 11, 338 (2000). 31. Peyret, P., et al., “Nearest-neighbor thermodynamics and NMR of DNA sequences with internal A·A, C·C and T·T mismatches”, Biochemistry 38, 3468 (1999). 32. Sakamoto, K., et al., “Molecular computation by DNA hairpin formation”, Science 288, 1223 (2000).
Engineering Signal Processing in Cells: Towards Molecular Concentration Band Detection Subhayu Basu, David Karig, and Ron Weiss Princeton University, Princeton, New Jersey {basu, dkarig, rweiss}@princeton.edu
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 diffuse from the environment into the cell. The circuit detects acyl-homoserine lactone ligand molecules, determines if the molecular concentration falls within two prespecified 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 efficiencies or dna-binding protein affinities to their operators.
1
Introduction
Cells are complex information processing units that respond in highly sensitive ways to environmental and internal signals. Examples include the movement of bacteria toward higher concentrations of nutrients through the process of chemotaxis, detection of photons by retinal cells and subsequent conversion to bioelectrical nerve signals, release of fuel molecules due to hormones that signal hunger, coordinated secretion of virulence factors and degradative enzymes by bacterial cells using quorum sensing molecules, and cell differentiation based on signal gradients. We strive to engineer cells that process internal and environmental information in novel ways by integrating protein-ligand interactions with synthetic gene networks. Applications include patterned biomaterial fabrication, embedded intelligence in materials, multi-cellular coordinated environmental sensing and effecting, and programmed therapeutics. These applications require synthesis of sophisticated and reliable cell behaviors that instruct cells to process information and make complex decisions based on factors such as extra-cellular conditions and current cell state. In this paper, we propose a new genetic signal processing circuit for detecting tunable ranges of chemical concentrations of ligand molecules that freely diffuse into the cell. The signal processing is performed in engineered Escherichia coli hosts to detect acyl-homoserine lactone (acyl-HSL) quorum sensing molecules. M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 61–72, 2003. c Springer-Verlag Berlin Heidelberg 2003
62
Subhayu Basu, David Karig, and Ron Weiss
OO O O N H
OO O O N H OO O O N H
LuxR
OO
OO O O N H
OLuxR NO H
P(R)
P(X)
X
Z1
P(Z)
Y
P(Y)
W
P(W)
GFP
Z2
Fig. 1. Gene Network for a chemical concentration band detector
The underlying mechanisms rely on ligand molecules binding to cytoplasmic proteins and the binding of cytoplasmic proteins to DNA segments that regulate the expression of other proteins. The genetic circuit consists of components that detect the level of acyl-HSL, determine if the level is within the range of two prespecified thresholds, and report the outcome with a fluorescent protein (Figure 1). The acyl-HSL signal is produced either by naturally occurring organisms [5] or by bacterial hosts engineered to secrete the molecules in order to perform cell-cell communications[12]. The acyl-HSL freely diffuses from the environment into cells and binds to the luxR cytoplasmic protein, enabling the protein to form a dimer. In turn, the dimer complex binds to the DNA and activates the lux P(R) promoter. The activated transcription results in the expression of regulatory proteins (X and Y) that control two series of downstream promoters. Here, DNA-binding repressor proteins X, Y, W, and Z, and their promoter counterparts are carefully chosen or engineered to have desired kinetic properties. The sub-circuit originating from the X protein determines the lower threshold of the acceptable acyl-HSL range, while the sub-circuit originating from the Y protein determines the high threshold. If the acyl-HSL chemical concentration falls within the range, the reporter green fluorescent protein (GFP) is expressed at high levels and can be detected externally. In the analysis of the circuit and the description of preliminary experimental results, we demonstrate how to adjust these thresholds by altering the kinetic properties of specific genetic elements, such as the ribosome binding site (RBS) efficiencies or the dna-binding protein affinities to their operators. The output of the band detection circuit can be coupled to other genetic circuits and regulatory responses. This circuit is therefore useful for monitoring many protein-ligand interactions that affect gene regulation and can serve as a modular component for a variety of signal processing tasks. For example, it can be used in cell-cell communications systems, in the detection of chemical gradients, and in synthetic cell aggregate systems that gather, process, and respond to environmental signals spanning large-scale areas. In the remainder of the paper, we describe relevant work and background (Section 2), introduce the design of the band detection circuit (Section 3), analyze the ability to modify band thresholds (Section 4), report on preliminary
Engineering Signal Processing in Cells
0
P1
R2 P2
[Off]
R3 CFP
63
YFP P3
I2 measure TC
P1
R2
P3
I2
P2
R3
YFP
CFP
Fig. 2. Genetic circuit to measure the device physics of an R3 /P3 cellular gate: digital logic circuit and the genetic regulatory network (Px : promoters, Rx : repressors, CFP/YFP: reporters) experimental results that demonstrate the functioning of certain sub-components of this circuit (Section 5), and offer conclusions and a discussion of the issues in implementing the full circuit (Section 6).
2 2.1
Background Quorum Sensing
Quorum sensing enables coordinated behavior among bacteria[2]. Specifically, acyl-homoserine lactones (acyl-HSLs) diffuse freely through cell walls and serve as intercellular communication signals. Significant accumulation of acyl-HSL results in interaction of this signal chemical with specific DNA-binding R-proteins. This bound complex then activates transcription of a certain gene or sets of genes. Synthesis of acyl-HSLs is mediated by specific I-genes. As an example, the quorum sensing system in Vibrio fischeri, which grows in a symbiotic relationship with sea organisms such as the Hawaiian sepiolid squid, regulates density dependent bioluminescence. In this system, the luxI gene codes for production of LuxI, which is responsible for synthesis of 3-oxohexanoyl-homoserine lactone (3OC6HSL). The luxR gene codes for the LuxR protein, which binds to accumulated 3OC6HSL to activate gene transcription. Previously, we successfully transferred this quorum sensing mechanism to E. coli hosts for use in engineered cell-cell communications[12]. 2.2
Synthetic Gene Networks
Other recent projects have also experimentally demonstrated forward-engineered genetic regulatory networks that perform specific tasks in cells. Becskei’s autorepressive construct[3] is a single gene that negatively regulates itself to achieve
64
Subhayu Basu, David Karig, and Ron Weiss
a more stable output. Gardner’s toggle switch[6] is a genetic system in which two proteins negatively regulate the synthesis of one another. This system is bistable, and sufficiently large perturbations can switch the state of the system. Elowitz’s represillator[4] is a genetic system in which three proteins in a ring negatively repress each other. This system oscillates between low and high values. For the above systems, the analysis and experimental results reveal that the genetic components must be matched to achieve correct system operation, as also discussed in [11]. 2.3
Device Physics of Genetic Circuit Components
We have previously defined genetic process engineering as a method for genetically altering system components until their device physics are properly matched. These components can then be combined into more complex circuits that achieve the desired behavior. For example, ribosome binding sites (RBS) can be mutated to alter rates of translation of mRNA into protein. We constructed genetic circuits to measure the device physics of cellular gates[10], as shown in Figure 2. In one instance of this network, the R2/P2 component consists of a lacI/p(lac) gate and the R3/P3 component consists of a cI/λP (R) gate. In this case, the level of the IPTG inducer molecule (I2) controls the level of the cI input repressor. With matching gates, the logic interconnect of this circuit should result in YFP fluorescence intensities that are inversely correlated with the IPTG input levels. The lowest curve in Figure 2 (RBS R1) shows the transfer curve of a cI/λP (R) inverter prior to genetic process engineering. The transfer curve relates IPTG input concentrations to the median fluorescence of cells grown in a culture at these IPTG concentrations. The cells were grown for several hours in log phase until protein expression reached a steady state. The unmodified cI/λP (R) circuit responds weakly to variations in the IPTG inducer levels. Genetic process engineering was used to modify the cI/λP (R) inverter to obtain improved behavioral characteristics. Ribosome Binding Site (RBS) sequences significantly control the rate of translation from messenger RNA(mRNA) molecules to the proteins for which they code. We replaced the original highly efficient RBS of cI with a weaker RBS site by site-directed mutagenesis and were able to noticeably improve the response of the circuit (Figure 2, RBS R2). In further genetic process engineering (Figure 2, RBS R2/OpMut4), a one base pair mutation to the cI operator site of λP (R) yields a circuit with an improved inverse sigmoidal response to the IPTG signal. The signal processing circuits described in Section 3 are assembled by combining multiple genetic components with matching characteristics into compound circuits. To effectively synthesize these compound circuits, the device physics of circuit components can be engineered using site-directed mutagenesis and molecular evolution techniques. Note that the genetic constructs for digital logic inverters described in this section are also used for the low threshold component of the band detection circuit.
Engineering Signal Processing in Cells 0.4
0.4 mRNA XY mRNA Z1
0.3 mRNA conc
mRNA conc
0.3 0.2 0.1 0 −1 10
65
0.2 0.1
0
10
1
[HSL]
(a) low threshold
10
0 −1 10
mRNAXY mRNA W mRNAZ2
0
10
1
[HSL]
10
(b) high threshold
Fig. 3. Low threshold and high threshold sub-circuits
3
Design of a Chemical Concentration Band Detection Circuit
The proposed construction for a chemical concentration band detector circuit, shown in Figure 1, expresses high levels of the reporter gene (GFP) only when the concentration of the acyl-HSL signal is within a specific range. The genetic circuit consists of three subcircuits: a low threshold detector, a high threshold detector, and a negating combiner. The series of transcriptional regulators that originates from the repressor protein X determines the lower threshold. When acyl-HSL binds to the R-protein, the molecular complex activates transcription of protein X. In turn, high concentrations of protein X repress the production of protein Z from the P(X) promoter (labeled as Z1 because protein Z can also be expressed from the P(W) promoter). Figure 3(a) shows a simulation of the steady state response of P(X) transcription of protein Z with respect to varying HSL concentrations. The simulations illustrate the average messenger RNA (mRNA) levels for X and Z1 in a cell that contains the band detect circuit, with all units denoting µmolar concentrations. As shown, mRNAZ1 is high only if the level of HSL is low. Notice that P(R) is multi-cistronic, coding for both X and Y that are expressed from mRNAXY . However, the translation rates of X and Y are different due to the fact that the carefully chosen RBS efficiencies for the respective proteins differ. In [10] and Section 2, we demonstrate the ability to quantitatively modify the transfer curve characteristics of genetic components by using a variety of RBSs. The second subcircuit, which determines the high threshold, consists of transcriptional regulators that originate from protein Y. Figure 3(b) shows the steady state relationship between HSL input levels and mRNA levels for XY, W, and Z2 . The RBS for Y is weaker than the RBS for X. Therefore Y is produced at lower rates than X for any given level of HSL (Figure 4(a)). As a result of the lower rate of protein Y expression, protein W is still highly expressed in response to high HSL levels when P(X) is already inactivated. This allows P(W) to act
66
Subhayu Basu, David Karig, and Ron Weiss 15
15
protein conc
protein conc
X Y 10
5
0 −1 10
0
[HSL]
10
5
0 −1 10
1
10
X W Z
10
(a) X versus Y expression
0
1
10
[HSL]
10
(b) X and W determine total Z
Fig. 4. Determinants of the band detector
20
20
Z GFP
15 protein conc
protein conc
15
10
10 Z GFP
5
5
0 −1 10
0
10
1
10
(a) original band detector
0 −1 10
0
10
1
[HSL]
10
(b) modified band detector
Fig. 5. Different band detectors from negating Z
as the high threshold detector by transcribing Z only when the HSL input is above a certain level. The last subcircuit combines the output of the two preceding subcircuits and negates their total product to produce the band detector. Figure 4(b) illustrates how the level of Z in the cell is determined by both X and W. Logically, Z is high when either X or W is low (Z = X NAND W). The output protein Z functions as a band-reject circuit. Finally, Figure 5(a) shows how the combined level of Z from transcription of both P(X) and P(W) represses the final GFP output, resulting in a band detector. By tuning reaction kinetics such as RBS efficiencies, protein decay rates, and protein-operator affinities, this synthetic gene network can be configured to respond to different signal ranges. For example, Figure 5(b) shows how to modify the band detector to accept a lower threshold by choosing ribosome binding sites for proteins X and Y that are three-fold more efficient. The simulation results described here were obtained by integrating ordinary differential equations that describe the biochemical reactions of the band de-
2
4
1.8
3.5
1.6
3
1.4
2.5
hsl−width
hsl−mid
Engineering Signal Processing in Cells
1.2 1
67
2 1.5
0.8
1
0.6 0.9
0.5 0.9 0.8
0.1 0.7
0.15 0.2
0.6 0.5 kxlate−X
0.8
0.1 0.7
0.15
0.35
kxlate−Y
(a) HSL midpoint of band detector
0.25
0.5
0.3 0.4
0.2
0.6
0.25 kxlate−X
0.3 0.4
0.35
kxlate−Y
(b) HSL width of band detector
Fig. 6. Impact of modifying X and Y RBS efficiencies on band midpoint and width
tector circuit. Kinetic rates published in the literature for various components, as well as educated guesses[11], were used in the simulations. The simulations demonstrate the qualitative effects of modifying genetic components in the forward engineering of synthetic gene networks. In the graphs, the nonlinear response of the components is due to repressor protein dimerization and the existence of multiple operator sites. We have used both of these common genetic regulatory motifs in previous experiments[10]. The next section analyzes the ability to change band thresholds by modifying various kinetic parameters of the circuit components.
4
Forward Engineering of Band Characteristics
This section examines forward engineering of band characteristics through the modification of two genetic regulatory elements: RBS’s and repressor/operator affinities. Two key characterizations of a band detect circuit are the midpoint of its detection range and the width of this range. The width is defined as the distance between the low and high cutoff points. The cutoff point is the HSL level at which the output of the band detector switches between what a downstream circuit considers high or detectable and what it considers low or undetectable. For the analysis below, we define the cutoffs as the HSL input levels at which the output GFP concentration is 0.3 µM. We assume that GFP concentrations above this threshold can be reliably detected by flow cytometry. Figure 6 depicts the effects of simultaneously changing the RBS efficiencies of X (kxlatex ) and Y (kxlatey ) on the midpoint and width of the band detector. The x and y axes represent the various RBS efficiencies, while the z axis depicts the HSL midpoint and HSL band width. As the RBS efficiency of protein X increases, a given HSL level results in additional translation of protein X. Thus, less mRNAZ1 is transcribed, and the low threshold component of the Z protein
68
Subhayu Basu, David Karig, and Ron Weiss
1.5
3 2.5
hsl−width
hsl−mid
2 1
1.5 1 0.5
0.5 4
0 4 0.5
3
0.5
3
1 1.5
2
2 1
k−bind−X2−P−X
1
3.5 4
k−bind−Y2−P−Y
(a) HSL mid point for band detector
2 2.5
1
3 0
1.5
2
2.5 k−bind−X2−P−X
3 0
3.5 4
k−bind−Y2−P−Y
(b) HSL width for band detector
Fig. 7. Impact of modifying X and Y protein/operator binding affinities
curve shifts left. This shift increases the band width and moves the midpoint left. As the RBS efficiency for Y increases, the high threshold component of the Z protein curve also shifts left, causing the band width to decrease and the midpoint to move left. The impact of simultaneously altering the binding affinities of the X2 and Y2 dimer proteins to their respective promoters is illustrated in Figure 7. If an X2 dimer binds more readily to the promoter responsible for transcription of mRNAZ1 , the low threshold component of the Z protein curve shifts left. This shift in turn causes the width of the band to increase and moves the midpoint to the left. As the strength of Y repression increases, the high threshold component of the Z protein curve shifts left, decreasing the band width and moving the midpoint left. A recurring trend in the analysis here is that changes in the RBS efficiency and the repression strength of Y have a greater impact on the shape of the band than comparable changes in the RBS efficiency and repressive strength of X. One reason that the constants associated with Y have greater impact is that Y influences the Z protein curve through an additional gain stage resulting from the W repressor. Simulations reveal that if the binding constant of W to its promoter and the RBS efficiency of W are reduced, the impact of Y on the HSL midpoint and band width are also reduced (graphs not shown). Another reason for the discrepancy is that Y controls Z values that correspond to a higher range of the HSL input signal than the Z values controlled by X.
5
Preliminary Experimental Results
In this section, we describe preliminary experimental results that demonstrate the functioning of certain subcircuits for performing band detection. Section 2 describes previous results of a low threshold subcircuit tunable by modifications of ribosome binding site efficiencies and repressor/operator affinities. In the next
Engineering Signal Processing in Cells
P3 P
69
Lambda P(R-O12-mut4) RBSII
CFP
EYFP
APr
pCMB-2 4397 bp
lacI
RBS II
pCMB-100
Kan(r)
P(LtetO-1)
4940 bp
P(LAC) tetR
RBS H T0 Term cI ColE1 ORI
p15A ori T1 Term
Fig. 8. pCMB-2 and pCMB-100
two sections, we present new experimental data for detecting a high threshold and for responding to acyl-HSL signals. 5.1
Implementation of a High Threshold Detection Component
To detect molecular concentrations above specific thresholds, we constructed the two plasmids in Figure 8 using standard DNA cloning techniques[1, 8]. The pCMB-2 plasmid contains an ampicillin resistance gene and a medium copy number origin of replication (ColE1 ORI). It also has a tet repressor (TetR) gene coding sequence that is transcribed from the ampicillin p(bla) promoter. The tetR regulates the P(LtetO-1) promoter on the pCMB-100 plasmid (kanamycin resistance, p15A medium copy number origin of replication). The lac repressor (lacI) and cyan fluorescent protein (CFP) from Clontech are transcribed from the P(LtetO-1) promoter. CFP reports the lacI levels. When the anhydrotetracycline (aTc) inducer molecule is introduced into the cell, it binds to TetR and prevents TetR from repressing P(LtetO-1). The aTc inducer molecule functions as the external input to the high threshold circuit component. The lacI protein represses P(lac) and regulates the expression of cI, the λ repressor protein[7]. cI is a highly efficient repressor that exhibits dimerization and cooperative binding to its operator. Finally, the λP (R−O12−mut4) promoter[10] on pCMB-2 is repressed by cI and regulates the expression of the enhanced yellow fluorescent protein (EYFP) output of the circuit. Therefore, the relationship between the aTc input and EYFP output describes the behavior of the high threshold component. To experiment with this circuit, we prepared twelve tubes each of 2ml LB ampicillin/kanamycin solution with different concentrations of aTc. We transformed E. coli STBL2 cells from Invitrogen with both the pCMB-2 and pCMB100 plasmids and picked a single colony into fresh media. The culture was distributed to the twelve different tubes that were shaken at 250RPM and @37◦ C
70
Subhayu Basu, David Karig, and Ron Weiss 10000
Median Fluorescence
1000
100
10
P(bla)
tetR
P(lac)
aTc
pCMB-2/pCMB-100
cI 1 0.1
P(tet)
lacI
CFP
λP(R)
YFP
1
10
100
[aTc] (uM)
Fig. 9. High threshold component of the band detector: circuit design and experimental results for approximately 6 hours until they reached an optical density at 600nm of approximately 0.3. The cells were washed with 0.22µm filter-sterilized phosphate buffered saline (PBS) twice, and the fluorescence levels of the cells were measured using Fluorescence-Activated Cell Sorting (FACS)[9] on a FACSVantage flow cytometer. The machine has two argon excitation lasers, one set at 458nm with an emissions filter of 485/22nm for detecting CFP, and the other laser set at 514nm excitation with an emissions filter of 575/26nm for detecting EYFP. Filters were obtained from Omega Optical. Figure 9 shows the median fluorescence level for the cell populations grown with different aTc inducer concentrations. The EYFP exhibits a strong sigmoidal relationship to the aTc input levels with a sharp transition from low to high output. The results in Figures 9 and 2 demonstrate components that respond specifically to signals bound by low or high thresholds. However, these subcircuits currently respond to either iptg or aTc inputs, and their behavior cannot be compared directly. To synthesize an operational band detector, it is likely that we will need to reduce the strength of the response for the high threshold. The next section describes a circuit that responds to acyl-HSL levels. 5.2
Implementation of an Acyl-HSL Detect Circuit
We previously constructed plasmids for performing cell-cell communications[12]. These plasmids are pSND-1, pPROLAR.A122, and pRCV-3. The pSND-1 plasmid, which has a p(Lac) promoter and a luxI gene sequence, is used to produce acyl-HSL. This plasmid has a ColE1 replication origin and ampicillin resistance. The luxI gene encodes an acyl-homoserine lactone synthesase that uses highly available metabolic precursors found within most gram negative prokaryotic bacteria (acyl-ACP from the fatty acid metabolic cycle, and S-adenosylmethionine from the methionine pathway) to synthesize N-(3-oxohexanoyl)-3-amino-dihydro2-(3H)-furanone, or 3OC6HSL. The pPROLAR.A122 plasmid is used as a negative control and contains only a p15A origin of replication and kanamycin resistance. The pRCV-3 plasmid, which contains a luxP(R) promoter followed by a GFP(LVA) coding sequence from Clontech, and a luxP(L) promoter followed by
Engineering Signal Processing in Cells
71
Fluorescence
1000.00
100.00
10.00
1.00 10
100
1000
HSL
Fig. 10. Median fluorescence of cell cultures with different levels of HSL a luxR coding sequence. pRCV-3 is used for quantifying the response to acyl-HSL signals. The results in [12] report on the relationship between acyl-HSL levels and the corresponding GFP fluorescence induced in pRCV-3. For high levels of an acyl-HSL extract, the level of fluorescence was observed to decrease. The decrease in fluorescence was likely due to the toxicity of the acyl-HSL extract. For this paper, we modified the experimental protocol in order to avoid using the acyl-HSL extract. Cells with pSND-1 plasmids were first grown @37◦ C to an optical density of 0.3. These plasmids produced acyl-HSL, which diffused freely through the cell membrane. The cells were centrifuged at 6000g, and the HSLcontaining supernatant was extracted. At the same time, different cells with pPROLAR.A122 were grown @37◦ C to an optical density of 0.3, and the supernatant was extracted following centrifugation at 6000g. The pPROLAR.A122 supernatant was used to dilute the HSL-containing supernatant to various concentrations. This was done to keep the nutrient concentration the same in all of the tubes while varying the HSL concentrations. Each dilution was aliquotted into a tube containing 1ml of fresh LB with ampicillin and kanamycin. We also added ampicillin and kanamycin as appropriate to keep the final concentrations of these antibiotics the same as in the original 1ml LB/ampicillin/kanamycin solution. A single colony of cells transformed with both the pRCV-3 and the pPROLAR.A122 plasmids was selected and grown in the separate tubes @37◦ C until the cultures reached optical density of approximately 0.3. Next, the cells were washed and resuspended in 0.22µm filter-sterilized PBS, and the fluorescence of the cell population was measured using a FACScan flow cytometer with an argon laser excitation at 488nm and emissions filter of 530/30nm. Figure 10 shows the median fluorescence of each of the different samples that exhibits a direct sigmoidal relationship to increasing HSL concentrations. The cells did not exhibit any decrease in fluorescence as the HSL concentration was increased.
72
6
Subhayu Basu, David Karig, and Ron Weiss
Conclusions
In this paper, we propose to couple protein-ligand interactions with synthetic gene networks for detecting molecular signal concentration bands. The analysis of the circuit demonstrates several factors that can help forward-engineer this circuit to acquire different thresholds for the band detection. We also presented preliminary experimental results of the functioning of the low threshold component, the high threshold component, and the ability to respond to acyl-HSL signals. In the effort to build the complete version of this circuit, great emphasis will be placed on the quantitative characterization of the components, including the study of cell population statistics. To arrive at components with the appropriate device physics, we plan to employ site-directed mutagenesis and molecular evolution techniques. The mechanisms employed and lessons learned in building this particular circuit are likely to be beneficial for the broader goal of building a variety of novel signal processing circuits in cells.
References [1] F. M. Ausubel, R. Brent, R. E. Kingston, D. D. Moore, J. G. Seidman, J. A. Smith, and K. Struhl. Short Protocols in Molecular Biology. Wiley, 1999. [2] B. L. Bassler. How bacteria talk to each other: regulation of gene expression by quorum sensing. Current Opinion in Microbiology, 2:582–587, 1999. [3] A. Becskei and L. Serrano. Engineering stability in gene networks by autoregulation. Nature, 405:590–593, June 2000. [4] M. Elowitz and S. Leibler. A synthetic oscillatory network of transcriptional regulators. Nature, 403:335–338, January 2000. [5] W. C. Fuqua, S. Winans, and E. P. Greenberg. Quorum sensing in bacteria: The luxr-luxi family of cell density-responsive transcriptional regulators. J. Bacteriol, 176:269–275, 1994. [6] T. Gardner, R. Cantor, and J. Collins. Construction of a genetic toggle switch in escherichia coli. Nature, 403:339–342, January 2000. [7] M. Ptashne. A Genetic Switch: Phage lambda and Higher Organisms. Cell Press and Blackwell Scientific Publications, Cambridge, MA, 2 edition, 1986. [8] J. Sambrook, E. F. Fritsch, and T. Maniatis. Molecular Cloning: A Laboratory Manual. Cold Spring Harbor Laboratory Press, Plainview, NY, 1989. [9] H. M. Shapiro. Practical Flow Cytometry. Wiley-Liss, New York, NY, 1995. Third Edition. [10] R. Weiss and S. Basu. The device physics of cellular logic gates. In NSC-1: The First Workshop of Non-Silicon Computing, Boston, Massachusetts, February 2002. [11] R. Weiss, G. Homsy, and T. F. Knight Jr. Toward in-vivo digital circuits. In Dimacs Workshop on Evolution as Computation, Princeton, NJ, January 1999. [12] R. Weiss and T. F. Knight Jr. Engineered communications for microbial robotics. In DNA6: Sixth International Workshop on DNA-Based Computers, DNA2000, pages 1–16, Leiden, The Netherlands, June 2000. Springer-Verlag.
Temperature Gradient-Based DNA Computing for Graph Problems with Weighted Edges Ji Youn Lee1 , Soo-Yong Shin2 , Sirk June Augh3 , Tai Hyun Park1 , and Byoung-Tak Zhang2,3 1
Cell and Microbial Engineering Laboratory School of Chemical Engineering, 2 Biointelligence Laboratory School of Computer Science and Engineering, 3 Center for Bioinformation Technology (CBIT), Seoul National University, Seoul 151-742, Korea {jylee, syshin, sjaugh, thpark, btzhang}@bi.snu.ac.kr
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.
1
Introduction
Since Adleman’s pioneering work[1], DNA computing has been applied to various fields of research including combinatorial optimization [9], massive parallel computing [7], Boolean circuit development [11], nanotechnology [17], huge database [12], and so on. Though many researches achieve the good results, most of these applications do not consider the problem of representing numerical data in DNA molecules. However, many real world applications involve graph problems which have weighted edges. Examples include the shortest path problem, the travelling salesman problem, the minimum spanning tree problem, and the Steiner tree problem [4]. The numerical data representation method in DNA strands is the one of the important issue to extend the field of DNA computing. Though some researchers tried to represent the numerical data using DNA, the results are not satisfactory yet. M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 73–84, 2003. c Springer-Verlag Berlin Heidelberg 2003
74
Ji Youn Lee et al.
In this paper, we propose a novel encoding method that uses temperature gradient to overcome the drawbacks of the previous works. We represent the numerical data using melting temperature gradient, and implement a local search molecular algorithm with the temperature gradient method. The travelling salesman problem (TSP) is used as a benchmark problem for the proposed technology. TSPs are interesting in that their solution requires representing the path weights. This is contrasted with the Hamiltonian path problem where the connection cost is binary. Our bio-lab experiments show that the correct DNA strands are effectively amplified and the detection of optimal solutions made easier. In Section 2, we describe the molecular encoding of numerical data in DNA molecules. Section 3 explains the molecular algorithm and experimental procedure for solving TSP. Section 4 presents the results and discusses them. The conclusions are drawn in Section 5.
2 2.1
Molecular Encoding for Edge Weights of Graph Previous Encoding Methods
Firstly, Narayanan and Zorbalas proposed DNA algorithms to solve travelling salesman problems [8]. Their method makes the length of weight sequences proportional to the edge costs in the edge sequences. This method is inefficient in representing a wide range of weights because, in some cases, one edge sequence with a high weight must be very long. For the same reason, it is also inefficient to represent real values. In addition, the fact that larger weights are encoded as longer sequences is contrary to the biological fact; the longer the sequences are, the more likely they hybridize with other DNA strands, though we have to find the shortest DNA strands. Yamamura et al. proposed a concentration control method to represent the weights [18]. The concentration of each DNA is used as input and output data, i.e. the numerical data is encoded by concentrations of DNAs. This method enables local search among all candidate solutions instead of exhaustive search. However, the concentration control method has some drawbacks in detecting the solutions. One cannot be sure that the most intensive band (in the gel) has the optimal solutions, because the most intensive band can be made by a number of partial non-optimal solutions with low concentration rather than optimal solutions with high concentration. In addition, it is technically difficult to extract a single optimal solution from the most intensive band. In previous work [15], we proposed a method for representing real-values in fixed-length DNA strands using GC contents. Edge sequences contain two components: link sequences and weight sequences. The weight of edges is represented by varying the amount of A/T pairs and G/C pairs in weight sequences. Since there are two hydrogen bonds formed between A and T and three hydrogen bonds between G and C, the hybridizations between the G/C pairs are preferred to those between A/T pairs. Therefore, the search procedure can be guided by including more A/T pairs to higher weight sequences and more G/C
Temperature Gradient-Based DNA Computing for Graph Problems
75
pairs to smaller weight sequences. And we verified our method by the computer simulation. 2.2
Melting Temperature Control Encoding
Based on previous work, we improve the weight representation method by allowing the hybridization process to be controlled by melting temperature. Though the number of hydrogen bonds is an important factor deciding the thermal stability of DNA strands, it is not the only one. The melting temperature (Tm) is the more direct characteristic of the stability of the DNA hybrid and Tm is determined by more complex function consists of various factors including GC content. So, we adopt a melting temperature to encode the DNA strands. Many methods have been proposed to determine the Tm value of DNA duplex. In the absence of destabilizing agents, like formamide or urea, Tm depends on three major parameters: the GC content and thermodynamic factors, the strand concentration, and the salt concentration. If we ignore the reaction conditions, Tm only depends on the GC content and thermodynamic factors. The classical method is using GC content, salt concentration, and the length [16]. But recently a statistical method using the thermodynamic parameters such as ∆H and ∆S is proposed [5, 10]. The latter model is known as the nearest-neighbor (NN) model that is more accurate and applicable to DNA duplex up to 108 bp. We use both the GC content method and the nearest-neighbor method to calculate the Tm. If the sequences are short, the NN method is used, otherwise the classical method is mainly applied. Though Tm of the DNA duplex up to 108 bp can be accurately determined by the NN method, Tm of the longer DNA strands formed after hybridization and ligation depends on the classical method rather than the NN method.
3 3
0 5
3
3 3
1
4 7
9 3
2
AGCT TAGG P1A P1B
1
11 11 3 5
6 3
3 ATCC ATCA TACC P1B W12 P2A
2
7 ATCC GCCT GCTA P1B W13 P3A
3
Fig. 1. Graph for the travelling salesman problem (left) and its example of encoding in DNA (right). The vertex sequence is 5 → 3 and the edge sequence is 3 → 5 . The optimal path for this problem is ‘0 → 1 → 2 → 3 → 4 → 5 → 6 → 0’. The melting temperature control encoding scheme is illustrated for the travelling salesman problem in Fig. 1. Basic representation is similar to Adleman’s
76
Ji Youn Lee et al.
method [1]. The difference is that edge sequences have the weight sequence part in the middle of their sequences, W12 , W13 (Refer to the right part of Fig. 1). To design the sequences for weighted-graph problems using the proposed method, the vertex sequences are designed firstly. Each vertex sequence is designed to have a similar Tm using both the nearest-neighbor and the classical method. That is why the vertex sequences should not affect the hybridization fidelity. Then, the edge sequences are generated. The edge sequence consists of the two parts such as the link sequence (P1B , P2A , P3A ) and the weight sequence (W12 , W13 ). This scheme is motivated from [9]. The link sequences are based on the vertex sequences to be linked and have also a similar Tm, since the link sequences of the edge sequences are decided by the vertex sequence. The weight sequences are designed to have a various Tm according to their representative cost. To produce more variation in generating low cost paths, the weight sequences with smaller weights have a lower Tm. If DNA strands have a lower Tm, it can be easily denatured and also easily amplified by denaturation temperature gradient polymerase chain reaction. For example, as shown in Fig. 1, the first part (P1B ) of the edge sequence is complementary to the last half (P1B ) of the starting vertex sequence. And the last part (P2A ) is complementary to the first half of the ending vertex sequence (P2A ). The weight sequence W12 with cost 3 contains more A/T pairs than the weight sequence W13 with cost 7 to lower the Tm. 2.3
Travelling Salesman Problems
We selected travelling salesman problem as a benchmark. The travelling salesman problem (TSP) is to find a minimum weight (cost) path for a given set of vertices (cities) and edges (roads). In addition, the solution path must contain all the cities given, each only once, and begin from the specified city to which the tour ends [4]. We solve the TSP with 7 nodes, 23 edges and 5 weights as shown in Fig. 1. For convenience, we represent the weights by decimal numbers such as 3, 5, 7, 9, and 11. The example of DNA sequences for solving TSP is shown in Table 1. These sequences are generated by the NACST sequence generator (NACST/Seq) [6]. The sequences are generated to prevent mis-hybridization and unexpected secondary structure using seven constraints such as similarity, H-measure, Hmeasure in the 3’-end, GC ratio, continuity, the unexpected secondary structure, and melting temperature [14, 13]. For the vertex sequences, Tm ranges 55o C to 60o C using the NN model with 1M salt concentration and 10nM oligomer concentration, GC content is restricted to 50%, the unexpected secondary structure such as hairpin formation is prohibited. In the weight sequences, Tm is increased by the cost; GC content is varied from 30% to 70% (see Table 1). To avoid the extreme case, i.e. the sequence consists of all C or G, we set the range as 30% ∼ 70%. As the result of evolutionary algorithms, NACST/Seq assigns the 30% to weight 3, 40% to weight 5, and so on. NACST/Seq increases GC content by 10%, as the weight is increased by two. After hybridization and ligation, the long sequences are generated which are not fit to the NN model. Therefore, evolutionary algorithm changed the GC ratio more precisely than melting temperature.
Temperature Gradient-Based DNA Computing for Graph Problems
77
Table 1. Vertex sequences and weight sequences for TSP. Tm is calculated by the NN method with 1M salt concentration and 10nM oligomer concentration. Vertex sequences Sequence (5 → 3 ) AGGCGAGTATGGGGTATATC CCTGTCAACATTGACGCTCA TTATGATTCCACTGGCGCTC ATCGTACTCATGGTCCCTAC CGCTCCATCCTTGATCGTTT CTTCGCTGCTGATAACCTCA GAGTTAGATGTCACGTCACG Weight sequences Edge cost Sequence (5 → 3 ) 3 ATGATAGATATGTAGATTCC GGATGTGATATCGTTCTTGT 5 GGATTAGCAGTGCCTCAGTT 7 TGGCCACGAAGCCTTCCGTT 9 GAGCTGGCTCCTCATCGCGC 11 No. 0 1 2 3 4 5 6
Tm GC% 60.73 50 59.24 50 59.00 50 56.81 50 58.13 50 59.44 50 56.97 50 Tm GC% 47.89 30 54.62 40 58.37 50 64.51 60 68.88 70
Additionally, the higher weight sequences have higher melting temperatures with the NN method.
3 3.1
Molecular Algorithms for TSP Previous Work
Most of the existing DNA computing methods to solve combinatorial optimization problems are similar to Adleman’s in several ways. First, all possible solutions are generated and then the correct solutions among them are selected. Also the previous works [8, 15, 18] on travelling salesman problems or shortest path problems are similar to each other. They only differ in their weight encoding schemes such as sequence length, GC content, and strand concentration. The former two studies were not verified by lab experiments, the last method is proved by lab experiments, though the results are not satisfactory. And last method [18] gives a bias to search space by concentration control. 3.2
Temperature Gradient Algorithms
In order to utilize the massive parallelism of biochemical materials and to guide search space, it is useful to give some biases in the experimental steps. For this purpose, we give some constraints in DNA concentration and the PCR step. By varying the concentration of each oligomer strands [18], we can generate more paths that contains a smaller sum of weights. Also by modifying the PCR protocol, we can specifically amplify and detect the correct solution easier. DNA strands of low melting temperature can
78
Ji Youn Lee et al.
be more strongly amplified in PCR by varying the denaturation protocol. Usually, we vary the annealing temperature to optimize the reaction condition. But by denaturing the dsDNA in the lower temperature in the starting cycles and gradually increasing the denaturation temperature, we can specifically amplify the DNA strands with a lower melting temperature. So we can amplify the correct solutions more than other solutions that have the same length but a higher melting temperature. The whole procedure to solve TSP is shown in Fig. 2. In step 1, we generate the solution set. Steps 2 ∼ 5 find the solution satisfying the restrictions (the starting vertex is the same as the end vertex). Step 6 separates the sequences visiting all vertexes. In steps 7 ∼ 8, we amplify the solutions based on its path cost and find the optimal solution. Finally, we check the path of the solution. Step 1: Hybridization and ligation [Generation of random paths] Step 2: PCR with primer vout (comp.) [Check the end vertex] Step 3: Gel electrophoresis Seperation by size and elution Step 4: PCR with primer vin [Check the start vertex] Step 5: Gel electrophoresis Seperation by size and elution
Step 6: Affinity-separation with a biotin-avidin magnetic beads system [Check the each vertex] Step 7: DTG-PCR with v in and vout (comp.) [Amplify the correct solutions more]
Step 8: Gel electrophoresis separation by size and Tm: TGGE Step 9: Sequencing and readout
Fig. 2. The molecular algorithms for solving TSP.
Oligomer Synthesis All 7 vertexes and 5 weights are designed in 20 mer ssDNA as listed in Table 1. And 23 edges in 40 mer ssDNAs are designed according to their vertexes and weight sequences. All oligomers are 5’-phosphorylated. Other 5’-biotinylated vertexes were prepared for affinity-separation. All oligomers were synthesized at Bioneer Co. Hybridization and Ligation Edge and weight oligomers were differently added by their weights. The amount decreased by 20% according to the weight increase by 2, set on the basis of weight 3 as a 100%. Oligomer mixture was heated to 95o C and slowly cooled to 20o C by 1o C per 1 minute, and stored at 4o C. Mix 5µl of hybridization mixtures and 350 units of T4 DNA ligase (TaKaRa, Japan), ligase buffer (66mM Tris-HCl, pH 7.6, 6.6mM M gCl2 , 10mM DTT, 0.1mM ATP), and add H2 O to a total volume of 10µl. We incubated the reaction mixture for 16 hours at 16oC.
Temperature Gradient-Based DNA Computing for Graph Problems
79
PCR Amplification and Gel Electrophoresis All PCR amplifications were performed on a PTC-200 DNA Engine (MJ Research, MA, USA). For normal amplification, 0.5µM of primer and AccuPower PCR PreMix (Bioneer, Korea) which containing 1 unit of T aq DNA polymerase in 10mM T ris-HCl, pH 9.0, 1.5mM M gCl2 , 40mM KCl, 0.25mM each dNTP were dissolved to distilled water to a total volume of 20µl. And PCR was processed for 34 cycles at 95o C for 30 seconds, at (T m − 5)o C for 30 seconds and at 72o C for 30 seconds. Initial denaturation and prolonged polymerization was executed for 5 minutes. All gel electrophoresis were performed with 2% Agarose-1000 (GibcoBRL, NY, USA) in 0.5X tris-borate-EDTA buffer and the gel was ethidium bromide stained. 50bp DNA Ladder (GibcoBRL, NY, USA) was used as a marker. Affinity Separation We roughly followed the affinity separation protocol in the Adleman’s experiments. The ssDNA for the affinity purification were produced by replacing the forward primer with 5’-biotinylated analog. The amplified product was annealed to streptavidin paramagnetic particles (Promega, Madison, WI) by incubating in 200ml of 0.5× saline sodium citrate (SSC) for 1 hour at room temperature with constant shaking. Particles were washed three times in 300ml of 0.5× SSC and then heated to 80o C in 100ml of ddH2 O for 5 minutes to denature the bound dsDNA. The aqueous phase with ssDNA was retained. For affinity separation, 1nmol of 5’-biotinylated vertex strands was annealed to particles as above and washed three times in 300ml of 0.5× SSC for 1 hour at room temperature with constant shaking. Particles were washed four times in 300ml of 0.5× SSC to remove unbound ssDNA and then heated to 80o C in 100ml of ddH2 O for 5 minutes to release ssDNA bound to the complementary vertex 1. The aqueous phase with ssDNA was retained. This process was then repeated with each vertexes. Denaturation Temperature Gradient PCR For denaturation temperature gradient PCR (DTG-PCR), the denaturation temperature was kept initially 70o C and gradually decreased 1o C per one cycle and kept 95o C for the remaining 10 cycles. Other conditions are identical with normal PCR described in the PCR amplification section. Temperature Gradient Gel Electrophoresis For TGGE analysis, we used 8% denaturing polyacrylamide gel containing 20% formamide and 4.2M urea. The electrophoresis was performed over 55o C ∼ 70o C temperature range at 200 volt for three hours. After the electrophoresis, the gel was silver stained. Cloning and Sequencing After the TGGE, the DNA strands in main band were excised, eluted and PCR amplified. This PCR product was cloned into pBluescript SK+ and sequenced using T7 primer.
80
Ji Youn Lee et al.
(A)
M
1
2
3
(B)
M
1
350bp
(C)
M
1
2
(D)
M
1
M
1
Fig. 3. Gel electrophoresis on a 2% agarose gel. The lanes contain: lane M denotes DNA size marker (50 bp ladder), (A) lanes 1,2: first ligation result, lane 3: oligomer mixture, (B) lane 1: second ligation result, (C) lanes 1,2: first PCR with Vout result, (D) lane 1: second PCR with Vin result
4 4.1
Results and Discussion Random Path Formation and Size Sieving
The start point to solve TSP is generating initial pool, random path formation. Searching a correct solution in the candidate pool is an important step to solve the problem. However, more generation of the possible solution in the candidate pool is readily achievable if we utilize the advantages of molecular computing. The reaction rate of biochemical reaction is related with the reaction constant and the reactant concentrations. Therefore, concentration gradient can be useful to obtain the correct solution. This approach was already tried by [18]. By increasing the concentration of DNA sequences of smaller weights and vice versa, paths which contains a smaller sum of weights will be more frequently generated. In our work, the concentration gradient was only a tool to generate more possible solutions. The hybridization and ligation results are shown in Fig. 3 (A). Compared with the oligomer mixture, the ligated DNA strands became elongated. But,
Temperature Gradient-Based DNA Computing for Graph Problems
81
there are few copies around the 300 bp that indicates the length of paths including 8 vertexes. So we executed the ligation reaction again and obtained an upper shifted ligation product as shown in Fig. 3 (B). However, still shorter DNA strands mainly occupy the ligation product. Ligation is an essential step to generate random paths, so efficient ligation is needed to produce DNA strands long enough to solve large problems. 4.2
PCR with In and Out Vertex and Affinity Purification
After the hybridization and ligation, double-stranded DNAs with sticky ends were generated. We cannot use the primer pair because the start and the end point are identical in TSP and the primer pair is exactly complementary to each other. So we executed PCRs with only one primer. First, we executed PCR with a primer that is complementary with the end vertex (vertex 0). Blunt-ended double-stranded DNAs that end with the vertex 0 will be generated by this PCR. Subsequently, we executed the second PCR with vertex 0, and we could amplify the DNAs that start with vertex 0. We sieved the PCR product by 2% agarose gel electrophoresis (Fig. 3 (C), (D)). The second PCR product appeared in several bands in the gel. We excised and eluted the band around 300 bp and amplified with 5’-biotinylated vertex 0 as a primer. The amplified product was used in the following affinity separation with streptavidin paramagnetic particles. 4.3
Denaturation Temperature Gradient PCR
The DNA strands that passed the implementation procedures up to step 6 have the same length and contains same oligomer segments. So, they have similar characteristics and cannot be easily separated. However, we designed the weight sequence to have different GC content, so the Tm of the correct solution is the lowest among the candidate solutions. Therefore, if we decrease the denaturation temperature to a certain level, mainly DNA strands of correct solutions will be denatured at that temperature, and be amplified. As the denaturation temperature increases, other DNA strands also will be amplified. But the amount of correct solutions will be exponentially increased cycle by cycle, and occupy the major part of the solution. By simple modification of the typical PCR, we can amplify the correct solution and detect it easily. We can show the effectiveness of DTG-PCR by the relative amplification in Fig. 4 (A). Shorter DNA strands in the lane 2 are more amplified by DTG-PCR when compared with the normal PCR product in the lane 1 (See the boxed area in Fig. 4). After the DTG-PCR, we obtained the DNA strands as shown in amplification in Fig. 4 (B). This band might contains four different DNA strands of the possible Hamiltonian paths, ‘0 → 1 → 2 → 3 → 4 → 5 → 6 → 0 (the sum of weights: 21)’, ‘0 → 1 → 6 → 5 → 4 → 3 → 2 → 0 (31)’, ‘0 → 2 → 1 → 3 → 4 → 5 → 6 → 0 (27)’, ‘0 → 2 → 3 → 4 → 5 → 6 → 1 → 0 (31)’. Those strands have the identical length, and they cannot be separated by normal gel electrophoresis. However, we can separate these strands by the temperature gradient gel electrophoresis (TGGE), because they have distinct
82
Ji Youn Lee et al.
(A)
M
1
2
(B)
M
1
(C)
Main band 300bp (8vertex)
Fig. 4. Gel electrophoresis on a 2% agarose gel. The lanes contain: lane M denotes DNA size marker (50 bp ladder), (A) lane 1: normal PCR result, lane 2: DTG-PCR result, (B) lane 1: the final DTG-PCR result, (C) TGGE separation of solutions melting behaviors. Similar work has studied using denaturing gradient gel electrophoresis (DGGE) [3]. 4.4
Temperature Gradient Gel Electrophoresis and Sequencing
TGGE is analogous to DGGE and it is based on the correlation of the melting characteristic of a DNA strand. TGGE is an extremely sensitive method and even fragments differing in only one nucleotide in sequence can be separated by TGGE. Usually this property was used to detect point mutations. But we utilized this electrophoresis method to separate the correct solution from other possible Hamiltonian paths. The GC content of the strands varies from 40.67% to 44.00%, and the melting temperature of the DNA strands are respectively 84.80oC, 86.51oC, 85.68oC, 86.62oC by NN model [5] with 1M salt concentration and 10nM oligomer concentration, and 92.69oC, 94.05oC, 93.51oC, 94.05oC by GC content method. The PCR mixture containing those possible Hamiltonian paths was separated by TGGE, and one main band and other sub bands were observed in Fig 4 (C). The DNA strands in main band were cloned and sequenced, and it showed that the path 0 → 1 → 2 → 3 → 4 → 5 → 6 → 0 has the lowest cost. The sequencing result confirmed the whole experimental procedures. 4.5
Scalability
The solvable problem size is restricted to the capabilities of the current biochemical tools. In case of solving TSP, PCR is the critical step in the procedure. We can amplify DNA strand of up to 40,000 bases with current PCR technology. Though considering this limitation, we can scale up to 1,000 cities problems roughly, if we apply this temperature gradient encoding method. And The another important point of scalability is the ability of separation and detection. We
Temperature Gradient-Based DNA Computing for Graph Problems
83
can separate DNA strands whose GC content differs by 0.49 % with the current resolution of TGGE and this difference is easily achievable with our encoding method. However, there exist some limitations in scaling up to 1,000 city problems. The first and critical problem is that it is impossible to discriminate the solutions which have the identical melting temperatures. And it is not also discriminative when there exist two solutions that melting temperature differences are not exceeding 0.2o C. The second problem is the presence of elaborate and timeconsuming implementation steps. In the experimental view, 1,000 times affinity separation is almost impossible. This is the most time-consuming step in our implementation steps. But, if we introduce the affinity separation method proposed by [2], the affinity separation steps can be automated with high efficiency and can became easier. Other possible obstacle in our encoding method arises when the DNA strands with stable mismatches have lower melting temperature and are amplified exclusively. So the sophisticated sequence design to avoid the stable mismatches is needed.
5
Conclusions
We introduced a temperature gradient method to solve the graph problems with numerical data. This method can overcome the restrictions of other encoding methods and be easily implemented by the simple modification of the existing experimental techniques. We can more strongly amplify the correct solution relatively during the reaction and the solution can be easily detected. This method drives the DNA pool to contain more correct solutions, rather than to search randomly for the correct solution in the DNA pool. We showed the feasibility of our computing method by solving the travelling salesman problem with adequate biochemical tools. The combination of the orthogonal design of DNA sequences and denaturation temperature gradient PCR provides a novel method to solve general graph problems with weighted edges. This is applicable to any Tm-involved implementation steps to amplify low melting temperature DNA strands.
Acknowledgments This research was supported in part by the Ministry of Education & Human Resources Development under the BK21-IT Program and the Ministry of Commerce, Industry and Energy through the Molecular Evolutionary Computing (MEC) Project. The RIACT at Seoul National University provides research facilities for this study.
References [1] L. M. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021–1024, 1994.
84
Ji Youn Lee et al.
[2] R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, and L. Adleman. Solution of a 20-varaible 3-SAT problem on a DNA computer. Science, 296:499– 502, 2002. [3] J. Chen, E. Antipov, B. Lemieux, W. Cede˜ no, and D. H. Wood. In vitro selection for a MAX 1s DNA genetic algorithm. In Proceedings 5th International Workshop on DNA-Based Computers, pages 23–46, 2000. [4] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and company, 1979. [5] J. SantaLucia Jr. A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics. Proc. Natl. Acad. Sci. USA, 95:1460–1465, 1998. [6] D. Kim, S.-Y. Shin, I.-H. Lee, and B.-T. Zhang. NACST/Seq: A sequence design system with multiobjective optimization. In Preliminary Proceedings of 8th International Meeting on DNA Based Computer, pages 241–251, 2002. [7] Q. Liu, L. Wang, A. G. Frutos, A. E. Condon, R. M. Corn, and L. M. Smith. DNA compouting on surface. Nature, 403:175–179, 2000. [8] A. Narayanan and S. Zorbalas. DNA algorithms for computing shortest paths. In Proceedings of Genetic Programming 1998, pages 718–723, 1998. [9] Q. Ouyang, P. D. Kaplan, S. Liu, and A. Libchaber. DNA solution of the maximal clique problem. Science, 278:446–449, 1997. [10] R. Owczarzy, P. M. Vallone, F. J. Gallo, T. M. Paner, M. J. Lane, and A. S. Benight. Predicting sequence-dependent melting stability of short duplex DNA oligomers. Bioploymers, 44:217–239, 1998. [11] G. G. Owenson, M. Amos, D. A. Hodgson, and A. Gibbsons. DNA-based logic. Soft Computing, 5(2):102–105, 2001. [12] J. H. Reif, T. H. LaBean, M. Pirrug, V. S. Rana, B. Guo, C. Kingsford, and G. S. Wickham. Experimental construction of a very large scale DNA database with associatice search capability. In The 7th International Workshop on DNA-Based Computers, pages 241–250. [13] S.-Y. Shin, D. Kim, I.-H. lee, and B.-T. Zhang. Multiobjective evolutionary algorithms to design error-preventing DNA sequences. Technical Report BI-02-003, Seoul National University, School of Computer Science and Engineering, Seoul National University, Seoul, Korea, March 2002. [14] S.-Y. Shin, D.-M. Kim, I.-H. Lee, and B.-T. Zhang. Evolutionary sequence generation for reliable DNA computing. In Proceedings of Congress on Evolutionary Computation 2002, pages 79–84, 2002. [15] S.-Y. Shin, B.-T. Zhang, and S.-S. Jun. Solving traveling salesman problems using molecular programming. In Proceedings of Congerss on Evolutionary Computation 1999, pages 994–1000, 1999. [16] J. G. Wetmur. DNA probes: applications of the principles of nucleic acid hybridization. Crit. Rev. Biochem. Mol. Biol., 26:227–259, 1991. [17] E. Winfree, F. Lin, L. A. Wenzler, and N. C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394(6693):539–545, 1998. [18] M. Yamamura, Y. Hiroto, and T. Matoba. Solutions of shortest path problems by concentration control. In Proceedings of 7th International Workshop on DNABased Computers, pages 231–240, 2001.
Shortening the Computational Time of the Fluorescent DNA Computing Yoichi Takenaka1 and Akihiro Hashimoto2 1
2
Graduate School of Information Science and Technology, Osaka University, Machikaneyama 1-3, Toyonaka, Osaka 560-8531, Japan, [email protected] Faculty of Informatics, Osaka Gakuin University, Kishibe-Minami 2-36-1, Suita, Osaka 564-8511, Japan, [email protected]
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.
1
Introduction
Since Adleman demonstrated the possibility of solving NP-complete problems by using DNA, biomolecular computation has become a new vista of computation that bridges computer science and biochemistry [1]. DNA provides a massive computational parallelism that allows us to tackle intractable combinatorial problems exhaustively. In the area of formal language theory, a great number of theoretical studies [3,12,13] were inspired by this experimental possibility. Recently, there is a growing interest in using SAT as a practical tool for solving real-world problems. In fact, some problems are reported to be solved more efficiently by a SAT-solver than by the specialized algorithm[2,7]. Many researchers on DNA computing also report their studies through SAT. In 1998 and 2000, Smith and Liu proposed a surface-based approach to DNA computation [8,16]. In 2000, Sakamoto et al. proposed a fluorescent DNA computing that uses DNA hairpin formation where the computational paradigm differs from the Adleman-Lipton paradigm [14]. In 2001, Takenaka et al. proposed a fluorescent DNA computing that uses DNA beads, fluorescent DNA and mix & divide method[11][17]. M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 85–94, 2003. c Springer-Verlag Berlin Heidelberg 2003
86
Yoichi Takenaka and Akihiro Hashimoto
In this paper, we present an algorithm that improves the computational time of fluorescent DNA computing through SAT problem. The fluorescent DNA computing uses fluorescent DNA strands and DNA microarray for its calculation. DNA microarray is used to measure the expression of thousands of genes simultaneously[9,15]. There are many spots on the microarray and each spot holds multiple copies of one DNA strand. DNA strands can be labeled by fluorescers such as Cy3 and Cy5. When we hybridize two types of labeled DNA strands on microarray, we can measure the proportion of the number of Cy3labeled DNA strands and Cy5-labeled strands by intensity of the fluorescence. In the fluorescent DNA computing, each candidate solution for a given problem one-to-one corresponds to a DNA strand that is spotted on the microarray. Make Cy3-labeled DNA strands if the candidate solution satisfies a constraint of the problem. Then, make Cy5-labeled one if the candidate solution doesn’t satisfy one of the constraints. After competitive hybridization of these strands on the microarray, the spots only with Cy3 fluorescence hold the strands that correspond to the true solution. As the biological operation used in the fluorescent DNA computing is simple, it holds the potential to solve large-scale problems. In fact, Takenaka et al. shows the way to solve 24-variable SAT problem with DNA beads, which is one of the derivative technologies of DNA microarray and a DNA bead corresponds to a spot in microarray[17]. However, it has a shortcoming; it takes exponential time to read out the solution because one spot represents only one candidate solution in the computing. In this paper, we present an algorithm to avoid this shortcoming by letting one spot represents plural candidate solutions.
2
Definitions
This section introduces the notation used in the paper. Variables are denoted x1 , · · · , xn , and can be assigned truth-values 0 (False) or 1 (True). A literal l is either a variable x or its negation x. A CNF formula ϕ is a conjunction of clauses ω1 , · · · , ωm , where ωi is a disjunction of literals. A clause is said to be satisfied if at least one of its literals assumes value 1, unsatisfied if all of its literals assume value 0. A formula is said to be satisfied if all its clauses are satisfied, and be unsatisfied if at least one clause is unsatisfied. The SAT problem is to decide whether there exists a truth assignment to the variables such that the formula becomes satisfied. There are 2n assignments on the n variables and the assignments are denoted y1 , · · · , y2n . We define a function fϕ (y) that returns the number of clauses in CNF formula ϕ that the assignment y doesn’t satisfy. In the followings, we use a CNF formula (1) as a SAT instance for explanation. It contains 5 variables and 11 clauses. ϕ=
(x2 ∨ x4 ∨ x5 ) ∧ (x2 ∨ x3 ∨ x4 ) ∧ (x1 ∨ x2 ∨ x5 ) ∧ (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x3 ∨ x5 ) ∧ (x3 ∨ x4 ∨ x5 ) ∧ (x2 ∨ x3 ∨ x4 ) ∧ (x1 ∨ x2 ∨ x5 ) (1) ∧ (x1 ∨ x2 ∨ x4 ) ∧ (x1 ∨ x4 ∨ x5 ) ∧ (x3 ∨ x4 ∨ x5 )
Shortening the Computational Time of the Fluorescent DNA Computing
87
Table 1. Assignments and its number of unsatisfied clauses x5 = 0 00 x1 x2 01 11 10
00 1 2 1 1
x3 x4 01 11 1 1 1 3 1 2 1 1
x5 = 1 10 1 2 0 1
00 01 11 10
00 2 2 2 1
x3 x4 01 11 3 2 1 2 1 2 1 1
10 1 1 1 1
Table 1 shows the value of fϕ (y) for each assignment. The CNF formula (1) is satisfiable and a true assignment is (x1 x2 x3 x4 x5 ) = (11100).
3
Fluorescent DNA Computing
DNA strands can be labeled by fluorescers such as Cy3, Cy5, and R110. Assume there are many copies of a DNA strand and they are divided into two groups, and DNA strands in each group are labeled by a different fluorescer. We can measure the proportion of the number of DNA strands between two groups by this labeling technique and “competitive hybridization”. In the followings, we show the steps to measure the proportion. 1. Label the strands of each group by a different fluorescer respectively. 2. Spot the complementary strands on the surface of glycidal methacrylate plate. 3. Hybridize the strands of two groups to the spot competitively. 4. Wash out the strands that don’t hybridize to the spot. 5. Measure the intensity of two fluorescences. The proportion of the intensity is equivalent to the proportion of the number of DNA strands between two groups. We call this measurement “competitive hybridization”. The competitive hybridization is used in the microarray technology that can provide scientists with genome-scale insight into the state of a cell under different conditions. There are many spots on the microarray and each spot holds multiple copies of one DNA strand or one cDNA of a gene. A single microarray experiment measures the relative level of expression of every gene in the organism at the same time[4]. The fluorescent DNA computing uses competitive hybridization and microarray to calculate the solution. Each spot of microarray represents a candidate solution for a given problem. Consider candidates to be the DNA strands that encode candidate solutions. Also, consider co-candidates to be the complementary strands of candidates. The DNA computing by competitive hybridization requires the following five steps.
88
Yoichi Takenaka and Akihiro Hashimoto
00111 01111 11111 10111 00110 01110 11110 10110 00101 01101 11101 10101 00100 01100 11100 10100 00011 01011 11011 10011 00010 01010 11010 10010 00001 01001 11001 10001 00000 01000 11000 10000 2nd step: Labeled by Cy5
1st clause
3rd clause
00100 10100
01010 01110
00000 10000
01000 01100
2nd clause 01001 11001
4th clause 5th clause
01000 10000
11th clause
3rd step: Labeled by Cy3
Fig. 1. Complement strands made in the second and third step
1. Make a microarray each of whose spot holds multiple copies of a candidate. 2. Synthesize all the co-candidates that are labeled with a fluorescer. 3. For each constraint of the problem, synthesize co-candidates that don’t satisfy the constraint and label them with another fluorescer. 4. Hybridize competitively two groups of the co-candidates to the microarray. 5. Measure the intensity of the two fluorescent lights of each spot. We describe these five steps through the formula (1). As this instance has five variables, there are a total of 25 or 32 candidate solutions. In the first step, synthesize all the candidates and attach them to the spot respectively. In the second step, synthesize the co-candidates, and label them with a fluorescer. With loss of generality, use Cy5 as the fluorescer. Left side of Fig. 1 shows the complementary strands to be synthesized. In the figure, each square represents co-candidate and the number in the square means the assignment of (x1 x2 x3 x4 x5 ). Constraints of the SAT are clauses to be satisfied. In the third step, for each clause, synthesize complementary strands of candidates that don’t satisfy the clause. For the first clause (x2 ∨ x4 ∨ x5 ), we synthesize complementary strands of (x1 x2 x3 x4 x5 ) = (00000), (00100), (10000), (10100). Right side of Fig. 1 shows the complementary strands made in this step. Throughout the step, the co-candidate of the assignment yi is synthesized fϕ (yi ) times. For example, the strand of (x1 x2 x3 x4 x5 ) = (01000) are synthesized in second and third clauses. With loss of generality, we use Cy3 as the fluorescer. In the fourth step, competitively hybridize co-candidates synthesized in the second and third steps to candidates on the microarray. After competitive hybridization, the spots with the true assignment hold only Cy5 labeled strands, and the spots with the false assignment hold both Cy5 labeled strands and Cy3 labeled strands. As the assignment (x1 x2 x3 x4 x5 ) = (11100) holds the proportion of Cy5/Cy3=1/0, it is a true assignment and the formula (1) is satisfiable. Now, we count the computational time of the fluorescent DNA computing. As the computing uses O(2n ) spots on the DNA microarray in the first step,
Shortening the Computational Time of the Fluorescent DNA Computing
89
Fig. 2. DNA strands are synthesized by eight rounds of combinatorial synthesis, where in each word, w1-w8, is added in a separate column of a DNA synthesizer.
it seems to need O(2n ) time. In fact, it takes O(n) time with DNA beads and mix & divide combinatorial synthesis [17]. A DNA bead is approximately a 5µm diameter glycidal methacrylate bead that carries multiple copies of a DNA sequence. In [10], DNA strands are composed of eight words (W1 ∼ W8 ) and are synthesized by eight rounds of the mix & divide method. Figure 2 shows schema of the method. The second step takes O(n) time and the third step takes O(nm) time if you encode according to the mix & divide method used in the first step. The fourth step needs a constant time. In the fifth step, as measurement of a fluorescent light takes a constant time per spot and there are 2n spots, it takes O(2n ) time. The total time of the computational time is dominated by the fifth step. Therefore, it takes O(2n ) time.
4
Idea and Mathematical Background
The bottleneck of the fluorescent DNA computing is the number of spots on microarray. As a spot (or a bead) represents one candidate solution, the time required to measure all the fluorescent light becomes O(2n ). Assume that if one spot can represent plural candidate solutions, the computation time will be shortened. This is the idea to shorten the computational time of fluorescent DNA computing. To realize the idea, we bias the quantity of synthesized DNA strands (cocandidates) between the second and third steps of the fluorescent DNA comput-
90
Yoichi Takenaka and Akihiro Hashimoto
Table 2. Proportions of the two fluorescer Cy5/Cy3 x5 = 0 00 x1 x2 01 11 10
00 1/α 1/2α 1/α 1/α
x3 x4 01 11 1/α 1/α 1/α 1/3α 1/α 1/2α 1/α 1/α
x5 = 1 10 1/α 1/2α 1/0 1/α
00 1/2α 1/2α 1/2α 1/α
00 01 11 10
x3 x4 01 11 1/3α 1/2α 1/α 1/2α 1/α 1/2α 1/α 1/α
10 1/α 1/α 1/α 1/α
ing in section 3. Let the quantity of synthesized DNA per one assignment for each clause in the third step be α times more than that in the second step. The proportion of two fluorescers Cy5/Cy3 becomes 1/αfϕ(y) for an assignment y. Table 2 shows the proportions 1/fϕ(y) for formula (1). Let β be the number of candidate solutions that are represented by one spot, and the spot holds same amount of DNA strand (candidate). Then, we define the value γ as the proportion of two fluorescers Cy5/Cy3, which is shown in equation (2). β 1 i=1 1+αf (yi ) αf (yi ) i=1 1+αf (yi )
γ = β
(2)
As f (yi ) becomes larger, the numerator becomes smaller and the denominator becomes larger. Therefore, γ monotonically decreases as f (yi ) increases. Equation (3) shows the value γ of the formula (1) with β = 32. γ=
1+ 0+
20 α+1 20α α+1
+ +
9 2α+1 18α 2α+1
+ +
2 3α+1 6α 3α+1
.
(3)
Using this γ, we prove the existence of threshold T that holds following condition. The formula is
satisfied by an assignment in the spot if γ > T (4) unsatisfied by any assignments in the spot otherwise
Consider the value γ of the spot in two cases: Case1 γupper : minimum value of γ when the formula is satisfied by an assignment in the spot. Case2 γlower : maximum value of γ when the formula is unsatisfied by any assignments in the spot. The threshold T exists if γupper ≥ γlower . Case1: The formula is satisfied by an assignment in the spot. With loss of generality, let y1 be the assignment which satisfies the formula, i.e. f (y1 ) = 0. The lower bound of γupper is calculated as following equations.
Shortening the Computational Time of the Fluorescent DNA Computing
β 1 αf (yi ) 0+ γ = 1+ 1 + αf (yi ) 1 + αf (yi ) i=2 i=2 β β 1 α·m 0+ ≥ 1+ 1+α·m 1+α·m i=2 i=2
β
(where m is the number of clauses) 1 α·m = 1 + (β − 1) (β − 1) 1+α·m 1+α·m 1 α·m (β − 1) > lim 1 + (β − 1) m→∞ 1+α·m 1+α·m 1 = β−1 1 =⇒ γupper > β−1
91
(5)
(6)
(7) (8) (9) (10)
Case2: The formula is not satisfied by any assignments in the spot. From the condition of Case2, each assignment unsatisfies at least one clause. Therefore, f (yi ) ≥ 1 for every i. As the value of γ monotonically increases as f (yi ) decreases, γ holds the largest value when f (yi ) = 1 for every i. Therefore, β β α·1 1 (11) γlower = 1+α·1 1+α·1 i=1 i=1 β β·α 1 = (12) = 1+α 1+α α The threshold T exists if the equation γupper > γlower holds. From the two 1 cases, if β−1 is larger than α1 , the equation holds. As α and β are plus constants, T exists if α > β − 1 and T holds the equation γupper ≥ T > γlower . QED
5
Algorithm
Using the idea described in Section 4, we show the fluorescent DNA computing for a SAT. Let n be the number of variables in the formula, m be the number of clauses, n δ be the number of spots on a microarray, β be 2δ and α be a constant that is larger than β −1. Consider candidates as the DNA strands that encode candidate solutions, and co-candidates as the complementary strands of candidates. The algorithm of the fluorescent DNA computing with our idea is followings. 1. Make disjointed δ groups of β candidates. Then, attach each group of candidates to a spot on a microarray.
92
Yoichi Takenaka and Akihiro Hashimoto
2. Synthesize all the co-candidates that are labeled with a fluorescer. 3. For each clause ω, synthesize co-candidates that don’t satisfy the constraint. Then, adjust the amount of DNA strands as 2αp times as DNA strands synthesized in step 2, where p is the number of literals in ω. Label them with another fluorophore. 4. Hybridize competitively two groups of co-candidates to the microarray. 5. Measure the intensity of two fluorescences for each spot. 6. If the proportion of the two fluorescences for a spot γ is larger than the threshold T , the formula is satisfiable. Else, the formula is unsatisfiable. We use threshold T as average of γupper and γlower , where γupper and γlower are calculated by equation (7) and (12) respectively. The algorithm can only determine the formula is satisfiable or not. When we need to find the assignment that satisfies the formula, we use binary search after the above algorithm. Suppose the algorithm determine a spot with β candidates holds an assignment that satisfies the formula. We divide the β candidates into two groups and re-call the above algorithm. You can reduce the number of candidate solution to β/2, and repeat it until the number of candidate solutions becomes one. In the followings, we show how the algorithm solves SAT through the formula (1). Let the parameters be α = 4, β = 4 and δ = 8. Firstly, we encode 32 candidate solutions to 40-mer DNA sequence. The first half of 20-mer encodes three variables x5 ∼ x3 , and the second half of 20-mer encodes two variables x2 ∼ x1 . We use “DNASequenceGenerator” to determine eight 20-mer sequences [5]. Table 3 shows the encoding scheme. For example, the assignment (x5 x4 x3 x2 x1 ) = (00000) is encoded by AAAGCTCGTCGTTTAAGGAATAGGTGCGTGCATAACTGGG. In the first step, we make a microarray each of whose spot holds four kinds of candidate solutions. Fig. 3 shows the spots and the candidate solutions attached on them. The four assignments in a spot have same values of (x5 x4 x3 ). We use Cy5 and Cy3 as the fluorescer in second and third step. Amount of the DNA strands per a clause generated in third step is α/23 = 4/8 = 1/2 times as much as amount of the DNA strand generated in second step. Before hybridization we adjust density of the DNA strand to 100µM. After hybridization in the fourth step, the ideal values and experimental values of γ of each spot are described in Table 4. As γupper = 4/11 and γlower = 1/4, the threshold T is 27/88 ≈ 0.307. Because an experimental value γ of spot B is 0.335 and it is larger than T , we can determine that the spot B holds an assignment that satisfies the formula. The algorithm takes O(nm + δ) time to determine if the formula is satisfiable or not, and takes O(nm log n + δ) to find an assignment to be satisfied. As δ is 2n /β, the computation time is O(2n ) when β = 1. And when β = O(2n ), the computation time becomes O(nm log n). Therefore, we have to enlarge the value β to reduce the computation time.
Shortening the Computational Time of the Fluorescent DNA Computing
93
Fig. 3. Four candidate solutions are attached on each spot. Table 3. Variables and corresponding DNA sequence (x5 x4 x3) (000) (001) (010) (011) (100) (101) (110) (111)
6
Sequence AAAGCTCGTCGTTTAAGGAA GAAGCCTACTGTACTCTGCG TATCGTGATTTGGAGGTGGA CAGCCACGTAGTAGAGCTAG TACCCAATCGAACTGATAAG TCGGTCAACGGAGGGGGCTC GCGTTTTTGCGAGGCATGTG GCCTAAAGAATTGATCGCTT
(x2 x1) (00) (01) (10) (11)
Sequence TAGGTGCGTGCATAACTGGG CTAAGTGCGGCTGCATGACC TGGGGTTTTATCTTACGACC TGAGATTTTTAACGCCGTTA
Conclusion
We present a method to shorten the computation time of the fluorescent DNA computing for satisfiability problems. The method allows one bead or one spot can represent plural candidate solutions. Then we show an experimental result of the algorithm. As the computation time of the fluorescent DNA computing depends on the number of beads or spots, the method can dramatically reduce computation time of the fluorescent DNA computing.
References 1. Adleman, L.: Molecular computation of solutions to combinatorial problems. Science 266(11), (1994) 1021–1024. 2. Bejar, R., Manya, M.: Solving the round robin problem using propositional logic, In Proc. of 17th National Conference on Artificial Intelligence (AAAI’2000), AAAI press/MIT press (2000), 262–266.
94
Yoichi Takenaka and Akihiro Hashimoto
Table 4. The ideal values and experimental values γ of each spot. Spot A B C D
ideal γ 0.216 0.607 0.250 0.172
experimental γ 0.282 0.335 0.255 0.235
Spot E F G H
ideal γ 0.154 0.250 0.204 0.154
experimental γ 0.124 0.213 0.253 0.234
3. Calude, C.S., P˘ aun, G.: Computing with cells and atoms. Taylor & Francis Publisher, London, (2000). 4. DeRisi, J.L., Iyer, V.R., Brown, P.O.: Exploring the metabolic and genetic control of gene expression on a genomic scale. Science 278, (1997), 680-686. 5. Feldkamp, U., Saghafi, S., Banzhaf, W., Rauhe, H.: DNASequenceGenerator: a program for the construction of DNA sequences. DNA7, 7th International Meeting on DNA Based Computers, Preliminary Proceedings, (2001), 179–188. 6. Garey, R., Johnson, S.: Computers and Intractability, a guide to the theory of NPcompleteness. Freeman and Company (1991). 7. Kautz, H., Selman, B.: Pushing the envelope: planning, propositional logic, and stochastic search, Proc. of 13th National Conference on Artificial Intelligence (AAAI’96), AAAI press/MIT press 2, (1996) 1194–1201. 8. Liu, Q. et al.: DNA computing on surfaces. Nature 403, (2000) 175–179. 9. Lockhart, D., et al.: Expression monitoring by hybridization to high–density oligonucleotide arrays. Nature Biotechnol., 14, (1996) 1675–1680. 10. Brenner, S., et al.: In vitro cloning of complex mixtures of DNA on microbeads: physical separation of differentially expressed cDNAs. PNAS 97, (2000) 1665–1670. 11. Brenner, S., et al.: Gene expression analysis by massively parallel signature sequencing (MPSS) on microbead arrays. Nature Biotechnology 18, (2000) 630–634 12. Paun, G., Rozenberg, G., Salomaa, A.: DNA computing: new computing paradigms. Springer Verlag, (1998). 13. Rozenberg, G., Salomaa, A.: Handbook of formal languages. Springer Verlag, 1–3, (1997). 14. Sakamoto, K., Gouzu, H., Komiya, K., Kiga, D., Yokoyama, S., Yokomori, T., Hagiya, M.: Molecular computation by DNA hairpin formation. Science 288, (2000) 1223–1226. 15. Schena, M., Shalton, D., Davis, R.W., Brown, B.O.: Quantative monitoring of gene expression patterns with a complementary DNA microarray. Science 270, (1995) 467–470. 16. Smith L. M. et al.: A surface-based approach to DNA computation. J. Computational Biology 5, (1998) 255–267. 17. Takenaka, Y., Hashimoto, A.: A proposal of DNA computing on beads with application to SAT problems. DNA7, 7th International Meeting on DNA Based Computers, Preliminary Proceedings, (2001), 331–339.
How Efficiently Can Room at the Bottom Be Traded Away for Speed at the Top? Extended Abstract Pilar de la Torre Department of Computer Science, University of New Hampshire, Durham, New Hampshire 03824, USA [email protected]
Abstract. Given exponential 2n space, we know that an AdlemanLipton [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” 2n/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.
We consider hard computational problems for which the time required by the n best extant classical algorithm is “weakly exponential”, that is 2 c , where c > 1. We wish to better understand how to design biomolecular algorithms that trade away weakly exponential space to achieve as low of a running time as possible, and to analyze the efficiency of their space-time utilization relative to that of their best extant classical/biomolecular counterparts. A bit more formally, let a and b denote classical/biomolecular algorithms with space-time product requirements sta (n) = sa (n) × ta (n) and stb (n) = sb (n) × tb (n) respectively, We propose to compare their relative efficiency by comparing their respective space-time product requirements. We will say that algorithm a is space-time (product) efficient relative to algorithm b up to at most an f (n) factor if sta (n) = O(stb (n)f (n)). We will say that algorithm a is at least an f (n) factor more space-time (product) efficient than algorithm b, if sta (n)f (n) = O(stb (n)). Given a problem for which the best currently known classical time-bound is at most weakly exponential, we strive M. Hagiya and A. Ohuchi (Eds.): DNA8, LNCS 2568, pp. 95–111, 2003. c Springer-Verlag Berlin Heidelberg 2003
96
Pilar de la Torre
to come up with biomolecular/classical algorithms solutions that: (1) are as fast as possible, (2) are space-time product efficient relative to the best extant classical/biomolecular algorithm up to at most a factor f (n) that is bounded by a polynomial in n, and (3) f (n) is as slow growing a function of n as possible. We propose a natural framework for probabilistic computation which consists of the sticker model of Roweis et al. [13]. augmented by two probabilistic primitives: rand-initialize, and rand-partition. The intent is for these primitives to abstract the randomness enjoyed by biomolecules and offer logical access and control of randomness to the algorithm designer. Based on ideas which this writer perceives are part of the DNA computing community folklore, we present thought experiments that describe possible physical implementations for these primitives in the spirit of the sticker model. We illustrate the power of this randomized sticker setting by presenting deterministic and probabilistic parallel algorithms for the Covering Code Creation and k-SAT that exploit parallelism not only at the string (biomolecule) level, but also at the set-of-strings (tube) level and at the bits-within-string level. Notable among our contributions are the following: We develop biomolecular implementations of the previously best classical determinitic and probabilistic algorithms for the two computational problems [6,14] and analyze their relative space-time efficiency. While attempting attempting to do that, we discovered a classical algorithm for Covering Code Creation that is, by an exponential factor, space-time more efficient than the previously best algorithm [6]. We present a randomized biomolecular algorithm that runs in constant time and is, by an n factor, more space-time efficient than the best previously known randomized classical Covering Code Creation [6] algorithm, and is an exponential factor more space-time efficient that the best currently known deterministic or biomoecular competitor. We analyze relative space-time efficiency among a collection of new and previously known classical/biomolecular algorithms. The results of the analysis are summarized in Figure 1. For the Covering Code Creation Problem they are summarized in TABLE I and those for the k-SAT problem in TABLE II. Our results show that, for each of the problems considered, the best known probabilistic sticker algorithm is, by an exponential factor, more space-time efficient than the best known deterministic sticker or classical competitor. This and prior related work, such as that in [2,13,3,7], point to biomolecular settings for probabilistic algorithm design as logical tools of independent interest that deserve and remain to be systematically investigated.
How Efficiently Can Room at the Bottom Be Traded Away
97
TABLE I: Covering Code Creation Problem sec
ref
3
DANTSIN et al. [6]
CLASSICAL DETERMINISTIC
2[1−h(ρ)]n
3
DANTSIN et al. [6]
CLASSICAL DETERMINISTIC
3.4
THIS PAPER
3.3 3.4 3 3.5
algorithm’s time
algorithm’s space×time
22
2[1−h(ρ)]n
2[1−h(ρ)]n 2 2
2[1−h(ρ)+δ]n
Θ(n)
2[1−h(ρ)+δ]n
2[1−h(ρ)+δ]n
STICKER DETERMINISTIC
2[1−h(ρ)+δ]n
2[1−h(ρ)+δ]n
Θ(n)
2[1−h(ρ)+δ]n
THIS PAPER ♠
CLASSICAL DETERMINISTIC
2[1−h(ρ)+o(1)]n
Θ(n)
THIS PAPER ♠
STICKER DETERMINISTIC
2[1−h(ρ)+o(1)]n 2[1−h(ρ)+o(1)]n
DANTSIN et al. [6] ♣
CLASSICAL RANDOMIZED
2[1−h(ρ)]n
STICKER RANDOMIZED rand-initialize
2[1−h(ρ)]n
THIS PAPER ♣
model
covering code covering code size space n
n
2[1−h(ρ)+o(1)]n 2[1−h(ρ)+o(1)]n Θ(n)
2[1−h(ρ)+o(1)]n
Θ(n)
2[1−h(ρ)]n
2[1−h(ρ)]n
2[1−h(ρ)]n
Θ(1)
2[1−h(ρ)]n
TABLE II: k-SAT Problem sec
ref
4
DANTSIN et al. [6]
CLASSICAL DETERMINISTIC
22
4
DANTSIN et al. [6]
CLASSICAL DETERMINISTIC
Θ(n)
4.1
THIS PAPER
STICKER DETERMINISTIC
4.1
THIS PAPER ♠
CLASSICAL DETERMINISTIC
4.1
THIS PAPER ♠
STICKER DETERMINISTIC
2 4.2
model
algorithm’s space
STICKER RANDOMIZED rand-initialize rand-partition
n
2−
2 k+1
2−
2−
2 k+1
n
+ o(1)
Θ(n)
2−
2−
+
2 n k
algorithm’s space×time
n 2 k+1
2 k+1
n
2−
n
2 k+1
+ o(1)
Θ(mn)
2−
2 n k
Θ(knm)
n 2 k+1
2−
2 k+1
+
2 k+1
+
2−
n
2−
+
Θ(mn)
Θ(n)
¨ SCHONING CLASSICAL [14] RANDOMIZED ♣ THIS PAPER ♣
algorithm’s time
n
22
n n
2−
2 k+1
+ o(1)
2−
2 k+1
+ o(1)
2−
2−
n n
2 n k
2 n k
Fig. 1. The results of our relative space-time efficiency analysis, among a collection new and previously known classical/biomolecular algorithms for the Covering Code Creation problem, are summarized in TABLE I and those for the k-SAT problem in TABLE II. Each row of a table corresponds to an algorithm, where the entry in column one indicates the section discussing the algorithm in the article cited in column two. For the table of a given problem, a row annotated with a ♣(randomized) or ♠(deterministic) symbol indicates that its corresponding algorithm has been identified as best of its type based on space-time relative efficiency. Each table entry corresponding to an exponential expression has been represented by a simplified expression that is within a polynomial factor in n of the actual entry.
98
Pilar de la Torre
Related Work The “room at the bottom” in our title is intended to evoke Feynman’s seminal article [8] referenced by Adleman in [1]. Our algorithmic ideas build on those of Sch¨ oning on probabilistic k-SAT [14], and of Dantsin et al. [6] on covering code creation and deterministic k-SAT. Our formulation of the augmented probabilistic sticker model setting and biomolecular algorithms were inspired, and enlightened, by the DNA based models of Lipton [9], Adleman [1]. Bach et al. [2], and Roweis et al. in [13], and the biomolecular algorithm realizations of Chen and Ramchandran [3] and Diaz et al. [7] for classical probabilistic k-SAT algorithms [12,11,14].
1
Augmented Model
We briefly review the basic concepts behind the standard sticker model and explain how we adapt it to describe our algorithms. Our proposed augmentation to the standard sticker model consists of adding two randomized operations, rand-initialize and rand-partition, whose definition and proposed physical realization will be explored below. These are aimed at providing the algorithm designer with access to, and control of, the native randomness enjoyed by DNA molecules. Each of them abstracts a modeling assumption that this writer, as a newcomer to the field, perceives as part of the folklore within the DNA computing literature. The significance of these operations is illustrated by the role they play in the biomolecular algorithmic solution to two computational problems: the Minimal Covering Code Creation Problem in Subsection 3.5 and the k-SAT Problem in Subsection 4.2. 1.1
Operations
As in the standard sticker model, the operations of the augmented model are partitioned into blind operations and boundary operations. Blind Operations. These are the standard combine, separate, set, and clear, to which we add the following rand-partition operation. Let S be a strings multiset and d is a divisor of |S|. • rand-partition(1 : d , S; A, B) creates two multisets A and B such that: (1) A ∪ B = S, and (2) for each string instance s in S, s belongs to A with probability 1/d. For d = 2, rand-partition will also be denoted rand-halving(S; A, B). Boundary Operations. These are the two standard operations read and initialize, to which we add the following rand-initialize operation. Let K, L, and N be integers satisfying L ≤ K and N ≤ 2L . • rand-initialize(K, L, N ; Rrand−init ) creates the (K, L, N ) randomized library multiset Mrand−init = SL,N {0K−L}, where SL,N consists of N strings, which have been drawn one at a time independently at random with replacement from {0, 1}L.
How Efficiently Can Room at the Bottom Be Traded Away
99
For future reference, let us recall that initialize(K, L; Minit ) creates the L (K, L) library set Minit = {0, 1} {0K−L}, for K and L satisfying K ≤ L [13]. It should be noted that the rand-initialize operation can be realized as a computation that requires one initialize, and O(L) set operations, and O(L) rand-partition operations. Our goal, however, is to obtain constant time physical realizations for initialize and rand-initialize. 1.2
Computation and Control
Computation. A computation in the augmented stickers setting begins with either an initialize(K, L; M ) operation or a rand-initialize(N, K, L; M ) operation, which is followed by a sequence of blind operations. Starting from the “initial set” M , this sequence of operations is to yield a designated “answer set”. We consider two possible ways of ending a computation, which depends on the overall purpose of the computation. If the purpose is to decide a language, as in the standard sticker model, then the computation ends by applying the read operation to the “answer set”. In our augmented setting, however, the purpose of a computation may also be to generate a multiset of strings, in which case the answer is the “answer set” itself. Control. The selection and execution of the sequence of blind operations is provided by a sequential or a parallel classical algorithm. Through the configuration of sets and modification of their bit strings, the algorithm can exploit parallelism at two levels: tube parallelism at the set-of-strings level, and molecule parallelism at the string level. In particular, our algorithms exploit tube parallelism via vector-parallel versions of the boundary operations, which will be denoted by combine, separate, set, clear, and rand-partition. They operate on µ-tuples of sets of strings A = A1 , . . . , Aµ .
2
Physical Realization
Possible constant time physical realizations of the standard sticker operations are offered in [13]. Our primary goal here is to come up with a constant time realization for each of the operations rand-partition and rand-initialize that is compatible with those for the standard sticker operations. As it turns out, operation rand-initialize yields a biomolecular algorithm for Covering Creation Problem presented in Section 3.5. This algorithm is trading efficient with respect to the best known classical algorithm for the problem. Specifically, it has as low a running time as possible, its space-time product is polynomially equivalent to that of the best known classical Covering Code Creation algorithm, and it uses a constant number of tubes. Due to space limitations, we outline one physical realization setting below and postpone discussion of alternative settings to the journal version.
100
2.1
Pilar de la Torre
Augmented Physical Setting
As in the original Sticker Model physical setting, information is represented in terms of memory strands and sticker strands. The augmented physical setting however, employs an additional type of strand that we term coin strand or simply coin. A memory strand consists of a sequence r0 r1 . . . rL rL+1 . . . rK of K + 1 regions, each of which is M bases long. The first region, r0 , is a universal region for which there is no sticker-strand available. Based on region r0 , and assisted by an appropriately designed enabling probe, the memory complexes within a given mixture can be separated from sticker strands and coin strands. Sticker strands are M base long strands r1 , . . . , rK where each ri is complementary to region ri . Coin strands are also M base long strands κ1 , κ2 , . . . , κK . Each κi is complementary to sticker-strand ri , and hence identical to region ri of each memory strand. Randomized Partition. A possible realization of rand-halving(S; A, B) can be based in volume-halving: divide the contents of S by pouring one half into A and the rest into B. Analogously, for d > 2, a corresponding volume division yields a realization for rand-partition(1 : d , S; A, B). Randomized Initialization. We now outline a thought experiment that points to how one would attempt to go about generating the library Mrand−init = SL,N {0K−L}, specified by operation rand-initialize(K, L, N ; Mrand−init) in a stickers and coins setting, which is meant to be understood in the context of the physical realization of the sticker model operations as presented in [13]. This experiment was inspired in part by Roweis et al. [13] in their original implementation of the library {0, 1}L{0K−L } which, remarkably enough taps into the native randomness of the biomolecular setting. Thought Experiment. The idea behind this logical experiment for generating a (K, L, N ) randomized library set can be viewed as being composed of two phases: strand synthesis and bit extraction. Strand Synthesis Phase: First, we create two tubes A and B. Tube A contains N strands, which are synthesized identical copies of the memory strand r0 r1 r2 . . . rL rL+1 . . . rK . Tube B comprises, for each i from 1 to L, N coin-strands κi resulting from synthesizing N identical copies for the region ri . Second, we set bits 1, . . . , L to 1(on) in all the memory-strands in A. This could be done by first adding excess sticker-strands r1 ,, . . . , rK , and then removing the excess sticker-strand copies by isolating into tube C the memory-complexes based on the universal region r0 . Bits Extraction Phase: As the initial step, we combine the contents of B and C into a tube R. Within R, the native randomness enjoyed by molecules is first going to be triggered and subsequently extracted as random bits. By raising the temperature of the mixture in R, we trigger the dissociation of all stickerstrands. At this point, for each sticker-strand in R there are two complementary
How Efficiently Can Room at the Bottom Be Traded Away
101
regions available in R: one as a coin-strand and the other as a sub-strand of a memory-strand. In this model, each of them is capable of competing for the sticker-strand attachment with identical probability of success. Next, by letting the solution cool back down we enable the competition. This causes each sticker to randomly choose to attach itself to either a memory-strand or a coin-strand. In this way, one random bit gets recorded on each of the bit regions 1, . . . , L of each memory-strands. Finally, by a separation based on the universal region r0 , the memory-complexes are isolated into the mother tube Mrand . This concludes the description of our thought experiment. We thus model each recorded bit as a random bit (which comes up heads with probability one-half and tails with probability one-half) independently across memory-strands and across bit positions 1, . . . , L within a memory-strand. Thus, at this point, the contents of Mrand−init encode the set SL,N {0K−L } that we have called the (K, L, N ) randomized library multiset.
3
The Covering Code Creation Problem
This section considers two computational problems about covering codes. It presents deterministic classical and sticker model based algorithms for the δ(n)Almost Minimal Covering Creation problem, and a probabilistic sticker model algorithm for the Minimal Covering Creation problem. 3.1
Background
A code of length n is a subset of the Hamming space Hn = {0, 1}n of all nbit strings called points or codewords. The Hamming distance between points x and y is the total number d(x, y) of bit positions in which x and y differ. The sphere or ball of center x, radius r, and normalized radius ρ = r/n is the subset y if y B(x, r) = {y : d(x, y) ≤ r} of Hn . We say that ball B(x, r) covers point r is V (n, r) = |B(x, r)| = belongs to B(x, r). The volume of B(x, r) in H n i=0 n i
. A set S covers x if x belongs to S. A family F of subsets of set X is a set cover of X if every element of X is covered by some set in F . A covering code, or simply a covering, of length n and radius α, is a length n code C such that F = {B(x, α) : x ∈ C} is a set cover of Hn . We say that C has covering radius r if r is the smallest α such that {B(x, α) : x ∈ C} is a set cover of Hn . Let K(n, r) denote the size of the smallest covering code with length n and radius r = ρn. If ρ satisfies 0 < ρ < 1/2, then to within a polynomial factor in n, V (n, r) and K(n, r) can be estimated in terms of 2h(ρ)n and β(n), where h(x) is the binary entropy function (h(0) = 1 and 1/2 h(x) = −x lg x − (1 − x) lg(1 − x) for 0 < x < 1) and β(n) = [nρ(1 − ρ)] . Lemma 1 ([4]). If n and r = ρn are integers satisfying 0 < ρ < 1/2, then 2[1−h(ρ)]n ≤ 2n /V (n, r) ≤ K(n, r) ≤ n2n /V (n, r) ≤ nβ(n)2[1−h(ρ)]n ≤ ν(n), where ν(n) = nβ(n)2[1−h(ρ)]n differs from K(n, ρn) by at most a polynomial factor.
102
Pilar de la Torre
These bounds on K(n, ρn) motivate the following definitions: Definition 1. (1) A covering code C of length n and normalized radius ρ is called minimal if 1 ≤ |C|/2[1−h(ρ)n] ≤ poly(n), that is its size differs from 2[1−h(ρ)]n by at most a polynomial factor. (2) Let δ(n) be a function such that 0 < δ(n) ≤ d < 1 for some constant d. A covering code C of length n and normalized radius ρ is called δ(n)-almostminimal if, 1 ≤ |C|/2[1−h(ρ)]n ≤ 2δ(n)n , that is its size differs from 2[1−h(ρ)]n by at most the exponential factor 2δ(n)n . (3) If δ(n) = δ is a positive constant, we say that C is almost minimal. In particular, if δ(n) = c lg n/n for some constant c > 0, then C is minimal. As observed in [6], the problem of creating a minimal covering for a given length n and radius ρn, can be viewed as being that of finding a subcollection of F = {B(x, ρn) | x ∈ Hn } with the minimum number of balls that covers X = Hn , which is an instance of the Minimum Set Cover problem. Definition 2. Problem. Minimum Set Cover Input: A set X and a family F of subsets of X that covers X. Output: A minimum size subfamily of F that covers X. finds a set The well known classical Greedy Set Cover(X, F ; U) algorithm cover whose size is within 1 + ln |X| of optimal in worst-case time O( S∈F |S|) (see, for example, [5]). Let Greedy Code(n, ρ; C, |C|) denote the classical algorithm that, given n and ρ, computes a covering code C of length n, radius ρn, and cardinality |C| as follows: first it invokes Greedy Set Cover(X, F ; U) with X = Hn , F = {B(x, ρn) : x ∈ Hn }, subsequently it assigns to C the collection of codewords that are centers of balls in U, and it concludes by determining the number |C| of elements in C. The covering C created by this algorithm is a minimal, because |C| is within a factor 1 + ln |Hn | = θ(n) of the minimum, and hence, by Lemma 1 differs from 2[1−h(ρ)]n by at most a polynomial time of this factor. The running algorithm is within a polynomial factor of θ V (n, r)2n = θ 22n poly(n)2h(ρ)n , which is superexponential when ρ satisfies 1 < ρ < 1/2. Lemma 2 ([6]). For each n ≥ 1 and 0 < ρ < 1/2, a minimal covering C of length n and radius ρn can be created by the deterministic classical algorithm Greedy Code(n, ρ; C) in Ω( 2[2+h(ρ)]n worst-case time. As we will discuss next, it is possible to achieve subexponential computing times if we allow the covering to be almost minimal. Systematic treatment of codes, coverings, and the Minimum Set Cover problem can be found, for example, in [4,10,5] and references therein.
How Efficiently Can Room at the Bottom Be Traded Away
3.2
103
Covering Creation Problems
We formulate the optimization covering creation problem as follows Definition 3. Problem. Minimal Covering Creation Input: Integers n and r = ρn, satisfying n ≥ 1 and 0 < ρ < 1/2. Output: A covering C, of length n and radius ρn, that is minimal (i.e. |C| differs from 2[1−h(ρ)]n by at most a polynomial factor poly(n)). The approximation version of the problem is specified by a parameter δ(n) satisfying 0 < δ(n) ≤ d < 1 for some constant d. Definition 4. Problem. δ(n)-Almost Minimal Covering Creation Input: Integers n ≥ 1 and r = ρn where 0 < ρ < 1/2. Output: A covering C, of length n and radius ρn, that is δ(n)-almost minimal (i.e. |C| differs from 2[1−h(ρ)]n by a factor 2δ(n)n ). 3.3
Covering Creation: Classical Deterministic Algorithms
Two main techniques are often used in code theory to find good codes: randomization, which we will apply in the following Section 3.4, and divide-and-conquer, which is behind the deterministic algorithms we are about to describe. The deterministic divide-and-conquer algorithms build long codes from short codes by code concatenation (direct sum). The classical covering creation algorithm presented in [6] proceeds in two phases: Phase one creates a minimal covering Cλ of short length λ = λ(n) by applying the greedy set cover algorithm; Phase two generates the long length n covering Cn by concatenating n/λ copies of Cλ . Exploring an Algorithmic Space-Time Trade-Off In [6], two cases of the above construction are considered: (1) the case λ(n) = c where c is a positive constant (with respect to n), and (2) the case λ(n) = n/c. For the case λ = n/c, the resulting covering code Cn solves the Minimal Covering Creation Problem, but it requires exponential space. For the case λ = c, Cn solves the δ(n)-Almost Minimal Covering Creation Problem where δ is a constant, but it requires a different c (and hence a different algorithm where c depends on δ) for each given δ satisfying 0 < δ < 1/2. In the following reformulation of the results in [6] we let the parameter λ = λ(n) remain temporarily undetermined. In this way we uncover a new covering code algorithm that we will consider as case (3) λ(n) = (1/3 lg n. As Corollary 1 below shows, this algorithm compares favorably with the other two in that the size of the covering it computes is exponentially smaller than that produced by the algorithm corresponding to case λ = c, and it requires only polynomial workspace, unlike the exponential requirement of the algorithm corresponding to case n/c.
104
Pilar de la Torre
We now describe a family of algorithms parameterized by λ = λ(n), each of which creates a covering code of length n and radius ρn based on λ. Each builds such covering Cn in two stages: the first stage computes a good short code Cλ n/λ and the second generates the power code Cn = Cλ . c-Covering Code(n, ρ; Cn , |Cc |) assume. n ≥ 1, 0 < ρ < 1/2, c | n, and an available copy of Cc computed offline by Greedy Code(c, ρ; Cc , |Cc |). 1. Compute Cn = Ccn/c .
Flex Code n, ρ, λ(n); Cn , |Cλ(n) | assume: n ≥ 1, 0 < ρ < 1/2, λ(n) | n. 1. Greedy Code(λ(n), ρ; Cλ(n) , |Cλ(n) |) n/λ(n) 2. Compute Cn = Cλ(n) .
Lemma 3. Let 0 < ρ < 1/2, λ = λ(n, ρ) a positive integer, and n a multiple of λ. Let Cλ be the covering of length λ and radius ρλ and size at most 1/2 λ3/2 [ρ(1 − ρ)] 2[1−h(ρ)]λ computed by algorithm Greedy Code in time O(23λ ) and space O(2λ ). Then, n/λ
1. Cλ
is a code of length n, radius ρn, and size at most 2[1−h(ρ)]n 2[
3 lg λ 2λ
]n .
2. It can be computed by c-Covering Code if λ = c, and Flex Code otherwise. 3. The workspace requirement for this classical computation is O((n/λ(n))23λ(n) ), which is polynomial for λ(n) = O(lg n) and is exponential otherwise. 4. The time requirement is O(23λ + 2[1−h(ρ)]n 2
3 lg λ 2λ n
).
The following corollary give us bounds for the size of the covering computed by the algorithms under consideration and their time and space requirements. The algorithms corresponding to parameter values λ(n) = c and λ(n) = n/c where c is a constant, were considered in [6]. Corollary 1. 1. Given an integer n multiple of 6, a covering code of length n, radius ρn, and size at most poly(n)2[1−h(ρ)]n can be computed by Flex Code with λ(n) = n/6. This algorithm requires time poly(n)2[1−h(ρ)]n , and exponential workspace Ω(2n/2 ). 2. Given δ > 0 there is an integer constant c = c(δ, ρ) such that for each multiple n of c a covering code of length n, radius ρn, and size at most poly(n)2[1−h(ρ)]n 2δn can be computed by the classical algorithm c–Covering Code. This algorithm requires poly(n)2[1−h(ρ)]n 2δn time, and polynomial O(n) workspace. 3. Given an n multiple of an integer 13 lg n, a covering code of length n, radius lg lg n ρn, and size at most 2[1−h(ρ)+o( lg n )]n is computed by the classical algorithm lg lg n Flex Code with λ(n) = (1/3) lg n. It requires 2[1−h(ρ)+o( lg n )]n time, and polynomial θ(n) workspace.
How Efficiently Can Room at the Bottom Be Traded Away
3.4
105
δ(n)-Almost Minimal Covering Creation
This section gives two sticker model algorithms for the Covering Code problem. Power Code(λ, Cλ , n, L ; T1 ) 1. Let (K, L) be a sticker memory library T1 with K = L + n, L = (n/λ) lg |Cb | + L . That is, T1 = {0, 1}(n/λ) lg |Cλ |+L {0}n . 2. For t = 1 to n/λ { 2.1 Separate T1 into tubes T1 , . . . T|Cλ | , based on (t − 1) lg |Cλ | + 1, . . . , t lg |Cλ |: For l ← 1 to lg |Cλ | { For all σ, 1 ≤ σ ≤ 2l , in parallel { separate (Tσ , (t − 1) lg |Cλ | + σ; T2σ−1 , T2σ ) } 2.2 For each w ∈ Cλ = {w1 , . . . , w|Cλ | } and each strand s in Tj , copy wj into s’s substrand sL+(t−1)λ+1 sL+tλ . For all j, 1 ≤ j ≤ |Cλ |, in parallel { For l ← 1 to λ { If the lth bit of wj equals 1, then j , (t − 1)λ + j). } } set(T 2.3. Parallel Merge T1 , . . . , T|Cλ | ; T1 } } c-Code-Sticker(n, ρ, L ; T1 , |Cc |) assume. n ≥ 1, 0 < ρ < 1/2, c | n, a copy of Cc computed offline by Greedy Code(c, ρ; Cc , |Cc |). Power Code(c, Cc , n, L ; T1 ) .
Flex Code-Sticker n, ρ, λ(n), L ; T1 , |Cλ(n) | assume: n ≥ 1, ρ, 0 < ρ < 1/2, λ(n) | n. λ(n), ρ Cλ(n) 1. Greedy Set Cover(n, , |Cλ(n) |) 2. Power Code λ(n), Cλ(n) , n, L ; T1
They are obtained through the classical algorithms above by replacing their step 2 with the following sticker model implementation of the computation of n/λ Cn = Cλ from Cλ . Given a subset L of {0, 1}K and an integer µ, multi-suffixµ (L) (multi-prefixµ (L)) will denote the multiset of strings of length µ, each of which is the length n suffix (prefix) of one of the strings from multiset L. Given an integer n > 1 and a length λ = λ(n) covering code Cλ as input, the following procedure generates as output a set T1 of sticker model memory complexes. These complexes represent a binary language L of length K = (n/λ) lg |Cλ | + L +n with the following properties: (1) multi-suffixn (L) is the multiset of strings representing elements of Cn , each of which appears with multiplicity 2L , and (2) (n/λ) lg |Cλ |+L multi-prefixK−n (L) = {0, 1} . Theorem 1. Given δ > 0 and ρ satisfying 0 < ρ < 1/2, there is a constant c = c(δ, ρ) such that for each multiple n of c the invocation c-CodeSticker(n, ρ, L ; T1 , |Cc |) computes a covering code of length n, radius ρn, and size at most 2[1−h(ρ)]n 2δn . The algorithm has the following requirements. 1. The time required by the classical preprocessing is O(1), and that required by the biomolecular requires is Θ(n) operations from {initialize, set, clear, combine, separate}. 2. The classical phase requires O(1) space. The biomolecular phase requires O(n) tubes of O(n + L ) length strands and O(2[1−h(ρ)+δ]n poly(n)) space. 3. The space-time product required is asymptotically equal to that of the classical algorithm of Dantsin et al. in [6], which the current biomolecular algorithm implements.
106
Pilar de la Torre
Theorem 2. Given a number ρ such that 0 < ρ < 1/2, for each multiple n of (1/3) lg n, the invocation Flex Code-Sticker n, ρ, λ(n), L ; T1 , |Cλ(n) | comlg lg n putes a covering code of length n, radius ρn, and size at most 2[1−h(ρ)+o( lg n )]n .
The algorithm has the following requirements. 1. The time required is O(n) for classical preprocessing and O(n) biomolecular operations from {initialize, set, clear, combine, separate}. 2. The space required by the preprocessing phase is θ(n). The biomolecular phase lg lg n requires 2[1−h(ρ)+o( lg n )]n space, and O(n) tubes of O(n + L ) length strands. 3. The space-time product requirement is asymptotically equal to that of the best known polynomial space classical algorithm for the problem (which is our algorithm in Part 3 of Corollary 1) that the current biomolecular algorithm implements. The algorithm is an exponential number of times more space-time efficient than the best previously known algorithms [6]. 3.5
Minimal Covering Creation Problem
We now describe a beautiful classical probabilistic algorithm from [6] that, with high probability, solves the Minimal Covering Creation problem. We present a rand-initialize based probabilistic sticker model algorithm that implements it, is space-time efficient with respect to it up to constant factors, and is θ(n) times faster. The size of a covering created by these algorithms is, in fact, within a n factor of minimum. Dantsin et al. [6]’s probabilistic algorithm is implied by the following fact, which is the heart of their probabilistic proof for the upperbound on K(n, ρ) stated in Lemma 1. Lemma 4 ([6]). Let S be a set of n2n /V (n, r) elements that have been chosen uniformly at random with replacement from Hn satisfying n > 1. Then S is a covering code, of length n and radius at most r, with probability at least 1−2n /en . As observed in [6], given n ≥ 1 and ρ satisfying 0 < ρ < 1/2, Lemma 4 yields a classical algorithm, which with high probability computes a minimal covering code of length n, radius ρn, and size n2n /V (n, r). By Lemma 1, this size is bounded by, and polynomially equivalent to, ν(n) = nβ(n)2[1−h(ρ)]n . Rand Code(n, ρ; Crand ){ Set C = ∅ and repeat the following step ν(n) times: STEP: For i from 1 to n { Set bi to a random bit}; Add b1 · · · bn to Crand } }
We observe that the covering code Crand created by Rand Code is none other than a multiset Sn,ν(n) of ν(n) strings drawn uniformly and independently at random with replacement from Hn . We therefore conclude that the following randomized algorithm, based on the sticker model augmented with operation rand-initialize, implements Rand Code. Rand Code-Sticker(n, ρ; Trand ){ Invoke rand-initialize(n, n, ν(n); Trand ) }
How Efficiently Can Room at the Bottom Be Traded Away
107
Our conclusions are summarized below. Let us recall that functions h(·) and β(·) were defined in Section 3.1. Theorem 3. For every n ≥ 1 and ρ satisfying 0 < ρ < 1/2, an invocation to the probabilistic sticker model algorithm Rand Code-Sticker(n, ρ; Trand ), based on primitive rand-initialize, creates a minimal covering code Trand of length n, radius ρn, and size at most ν(n) = nβ(n)2[1−h(ρ)]n . 1. The time required is one rand-initialize operation that takes O(1) physical biomolecular steps. 2. The space required is nβ(n)2[1−h(ρ)]n and Θ(1) tubes of length Θ(n) strands. 3. Its space-time product is θ(n) times smaller than that of the best known randomized classical algorithm for the Minimal Covering Creation problem, which the current biomolecular algorithm implements, and its running time is as low as possible. It is θ(n) times more space-time efficient than the best known classical algorithm.
4
The k-SAT Problem
This section summarizes our results on deterministic and randomized sticker model based algorithms for the k-SAT problem. Due to space limitations we attempt to outline the algorithms and summarize the results of the analysis, and leave their elaboration for the journal version of this extended abstract. Definition 5. Problem. k-SAT Input. A k-CNF Boolean formula F = F (X1 , . . . , Xn ) = γ1 ∧ · · · ∧ γm of n variables, where each of the m clauses γi = li,1 ∨ · · · ∨ li,k has exactly k ≥ 3 literals and each literal li,j is either one of the variables Xν or its negation ¬Xν . Decision Output: Either “satisfiable”, if F (x1 , . . . , xn ) = 1 for some truth assignment x = (x1 , . . . , xn ) in Hn = {0, 1}, or “unsatisfiable”.Search Output: Either an x = (x1 , . . . , xn ) in Hn such that F (x1 , . . . , xn ) = 1, if one exists, or “unsatisfiable”. Representing F as an m-tuple γ1 , . . . , γm specifies a fixed order among the clauses. All of the following k-SAT algorithms can be viewed as having the following two phase structure, which offers a remarkable degree of parallelism. k-SAT Multiroot-Local-Search(n, m, F = γ1 , . . . , γm ) 1. Roots-Generation: Generate N initial assignments in set I ⊆ Hn = {0, 1}n . 2. Local-Search:For all x in I, invoke a Local Search(n, m, F = γ1 , . . . , γm , x) of r steps.
In Sch¨ oning’s k-SAT algorithm [14], Phase 1 is performed by probabilistic sampling and Phase 2 by a random-walk based local search involving r = 3n steps where n is the number of variables in the input instance. For each of the two k-SAT algorithms in Dantsin et al. [6] Phase 1 is performed by one of their two deterministic covering code creation algorithms (which correspond to cases
108
Pilar de la Torre
λ(n) = n/c and λ(n) = c in Part 1 and Part 2 of Corollary 1), and Phase 2 by a derandomized version of Sch¨ oning’s local-search algorithm, for the m clauses n k-SAT instance F , consisting of r = k+1 steps. 4.1
Deterministic Sticker Model Based k-SAT Algorithms
This section summarizes our results on two sticker model based k-SAT algorithms each of which, through parameter λ(n), are expressed by the parametrized algorithm k-SAT-SKINNY Sticker(n, λ(n), m, F = γ1 , . . . , γm ). For λ(n) = c, our biomolecular algorithm implements the classical deterministic k-SAT algorithm of Dantsin et al. [6], which uses algorithm c-Covering Code to perform Phase 1. For λ(n) = (1/3) lg n, our biomolecular algorithm implements a new classical k-SAT algorithm that results from the algorithm of Dantsin et al. using Flex Covering Code(n, ρ, λ(n) = (1/3) lg n; Cn ) to perform Phase 1. Algorithm: k-SAT-SKINNY Sticker (n, λ(n), m, F = γ1 , . . . , γm ) n Set L = k+1 1 + lg k.
Phase 1. Roots-Generation:
If λ(n) = c (, k) = c then c - Code-Sticker n, ρ, L ; MCn , |Cλ(n) | . If λ(n) = (1/3) lg n then Flex Code-Sticker n, ρ, λ(n), L ; MCn , |Cλ(n) | . Set I = 1 + (n/λ(n)) lg |Cλ(n) |. Phase 2.
Local-Search:
Local Search SKINNY-Sticker(MCn , I, L , m, γ1 , . . . , γm )f V ← MCn ; For level ← 1 to r do f Split by Unsat Clause(I, L , level, V, m, γ1 , . . . , γm ; U1 , . . . , Um , Sanswer ) Read(Sanswer ): If Sanswer = ∅, then fReport a truth assignment from Sanswer and Halt g elsef Flip Assignments(I, L , level, U1 , . . . , Um , m, γ1 , . . . , γm ; V1 , . . . , Vm ) Parallel-Merge(U1 , . . . , Um ; V ) g g Report “unsatisfiable”. Split by Unsat Clause(I, L , level, V, m, γ1 , . . . , γm ; U1 . . . , Um , R)) f L ← I + L For µ ← 1 to m do fcomment: Separate into Uµ assignments failing to satisfy γµ . For κ ← 1 to k do f Let Xµκ be the variable in γµ ’s κth literal lκ . If lκ = Xµκ then separate(R, L + µκ ; R, Runsat ) else separate(R, L + µκ ; Runsat , R) combine(Runsat , Uµ ; Uµ ) g g g
How Efficiently Can Room at the Bottom Be Traded Away
109
Flip Assignment(I, L , level, U1 , . . . , Um , m, γ1 , . . . , γm ; U1 , . . . , Um )f L ← I + L ; For all µ, 1 ≤ µ ≤ m, in parallel dof , comment: Flip bit values in Uκ Partition by–Flipping–Variable(I, level, Uµ , γµ ; Vµ,1 , . . . , Vµ,k ); For κ ← 1 to k in parallel do f Let Xν be the variable corresponding to γµ ’s κth literal separate(Vµ,κ , L + µκ , Aµκ , Bµ,κ ); clear(Aµ,κ , L + µκ ); set(Bµ,κ , L + µκ ) Parallel–Merge(Vµ,1 , . . . , Vµ,k ; Uµ ) g g g Partition by Flipping–Variable (I, level, Uµ , γµ ; Uµ,1 , . . . , Uµ,k ) For i ← 1 to 1 + lg k do f Set νi = i + (level − 1) 1 + lg k + I; Separate Uµ,1 , . . . , Uµ,2i , ν1 , . . . , ν2i ;
Uµ,1 , . . . , Uµ,2i , . . . , Uµ,1+(k/2i ) , . . . , Uµ,2i +(k/2i ) g
Theorem 4. Given 4 > 0 and k ≥ 3 there is an integer constant c = c (4, k) such that, for each multiple n of c , an k-SAT-SKINNY Sticker(n, λ(n), m, F ) invocation, with λ(n) = c , solves k-SAT instances F of n variables and m clauses. The algorithm has the following requirements. 1. The required time is θ(n) classical preprocessing and a sequence of O(knm) bio operations from {initialize, set, clear, combine, separate}. 2. The space required is θ(n) for the classical preprocessing. The biomolecular n phase requires [2 − 2/(k + 1) + 4] poly(n) space and O(km) tubes of O(n lg k) length strands. 3. The space-time product requirement is within a polynomial factor O(n) of that of the best previously known polynomial space classical algorithm (which is Dantsin et al’s algorithm in [6]) that the current biomolecular algorithm implements. Theorem 5. Let k ≥ 3, λ(n) = (1/3) lg n, and n be a multiple of λ(n). Invoking algorithm k-SAT-SKINNY Sticker(n, λ(n), m, F ) solves k-SAT instances F of n variables and m clauses. The algorithm has the following requirements. 1. The time required is O(n) classical preprocessing and a sequence of O(knm) operations from {initialize, set, clear, combine, separate}. 2. The space required is θ(n) preprocessing workspace. For the biomolecular phase the space requires O(km) tubes, O(n lg k) length strands, and is within n a polynomial factor of [2 − 2/(k + 1) + o((lg lg n)/ lg n)] space. 3. Its space-time product requirement is smaller, by at least the exponential facn tor [1 + 4(k + 1)/(k − 1)] , than that of the best previously known polynomial space deterministic classical algorithm for k-SAT , which is presented in Sec 4 of [6]; this makes k-SAT-SKINNY Sticker exponentially more space-efficient than that algorithm. 4.2
Probabilistic Sticker Model Based k-SAT Algorithm
This section summarizes our results on the probabilistic sticker model based implementation of Sch¨ oning’s k-SAT algorithm [14]. This classical algorithm
110
Pilar de la Torre
has probabilistic elements in both of its phases. The creation of the pool of roots for the multiroot local-search is implemented by a single invocation to rand-initialize. The randomized k-way choice of a literal within an unsatisfied clause required by the local-search update of the assignments is implemented using the rand-partition primitive.
Algorithm: k-SAT-Rand-Sticker (n, m, F = γ1 , . . . , γ , α) Phase 1. Roots-Generation:
Set K = n, L = n, and N = αpSch (n) 2 − Invoke rand-initialize(n, K, L, N ; M ).
2 n . k
Phase 2. All-Sources Local-Search: All-Sources Local-Search Randomized-Sticker(M, n, m, γ1 , . . . , γm ) Repeat 3n times f Separate by First Unsat Clause(M, m, γ1 , . . ., m, γm ; M1 , . . ., Mm , Sanswer ) Read(Sanswer ): if Sanswer = ∅, then report an element from Sanswer , and Halt. else f Flip Unsat Assignments(M1 , . . . , Mm , m, γ1 , . . . , γm ; M1 , . . . , Mm ) Parallel-Merge(M1 , . . . , Mm ; M ) g g Report: “probably unsatisfiable” Separate by First Unsat Clause(V, m, γ1 , . . . , γ ; M1 . . . , Mm , R)) For µ ← 1 to m do f , Comment: Separate from R into Mµ all truth assignments not satisfying γµ . For κ ← 1 to k do f Let Xµκ be the variable in γµ ’s κth literal lκ . If lκ = Xµκ then separate(R, µκ ; R, Runsat )else separate(R, µκ ; Runsat , R) combine(Runsat , Mµ ; Mµ ) gg Flip Unsat Assignment(M1 , . . . , Mm , m, γ1 , . . . , γ ; M1 , . . . , Mm ) For all µ, 1 ≤ µ ≤ m, in parallel do f , Comment: Flip bit values guided by γµ . For κ ← 1 to k do f rand-partition(1 : k − κ , Mµ ; Mµ,κ , Mµ ) g For κ ← 1 to k in parallel do f Let Xµκ be the variable in γµ ’s κth literal lκ . separate(Mµ,κ , µκ ; Aµ,κ , Bµ,κ ) clear(Aµ,κ , µκ ); set(Bµ,κ , µκ ) g Parallel-Merge(Mµ,1 , . . . , Mµ,k ; Mµ ) g
Theorem 6. An invocation of k-SAT-Rand Sticker(n, m, F, α) succeeds in finding a satisfying assignment for the k-SAT instance F of n variables and m clauses, if one exists, with high probability (1 − e−a ). The requirements of this algorithm are as follows. 1. The time required is O(n) rand-partition operation and Θ(knm) operations from {set, clear, combine, separate}. n 2. The space required is N = αpSch (n) 2 − k2 and Θ(kmn) tubes of O(n) length strands. 3. The space-time product requirement is within a polynomial O(km) factor of that of the best currently known classical randomized k-SAT algorithm [14]),
How Efficiently Can Room at the Bottom Be Traded Away
111
which the current algorithm implements. Hence k-SAT-Rand Sticker is spacetime efficient relative to the currently best known classical counterpart up to an O(km) factor. Acknowledgments. I am grateful to Anne Condon for many fruitful discussions. Thanks are due to Mark Bochert and an anonymous referee for suggestions that improved the quality of the presentation.
References 1. L. M. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266:1021–1024, November 11, 1994. 2. E. Bach, A. Condon, E. Glaser, and C. Tanguay. DNA models and algorithms for NP-complete problems, 1996. 3. K. Chen and V. Ramachandran. A space-efficient randomized DNA algorithm for k-SAT. In DNA Computing, 6th International Workshop on DNA-Based Computers, DNA 2000, Leiden, The Netherlands, June 2000, volume 2054 of LNCS. Springer Verlag, Berlin, Heidelberg, New York., 2000. 4. G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein. Covering Codes. NorthHolland, 1997. 5. T. Cormen, C. Leiserson, R. Rivest, and S. Stein. Introduction to Algorithms. McGraw-Hill, second edition, 2001. 6. E. Dantsin, A. Goerdt, E. A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan, , and U. Sch¨ oning. A deterministic (2 − 2/(k + 1))n algorithm for k-SAT based on local search. To appear in Theoretical Computer Science. 7. S. Diaz, J. L. Esteban, and M. Ogihara. A DNA-based random walk method for solving k-SAT. In DNA Computing, 6th International Workshop on DNABased Computers, DNA 2000, Leiden, The Netherlands, June 2000, volume 2054 of LNCS. Springer Verlag, Berlin, Heidelberg, New York., 2000. 8. R. P. Fynman. There’s plenty of room at the bottom. In Miniaturization, D. H. Gilber Editor, Reinhold, New York, pages 282-296, 1961. 9. R. J. Lipton. DNA solution of hard computational problems. Science, 268:542–545, 28, 1995. 10. F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, Amsterdam, Holland, 1977. 11. R. Paturi, P. Pudlak, M. E. Saks, and F. Zane. An improved exponential-time algorithm for k -SAT. In IEEE Symposium on Foundations of Computer Science, pages 628–637, 1998. 12. R. Paturi, P. Pudlak, and F. Zane. Satisfiability coding lemma. Chicago Journal of Theoretical Computer Science, 1999. 13. S. Roweis, E. Winfree, R. Burgoyne, N. V. Chelyapov, M. F. Goodman, P. W. K. Rothemund, and L. M. Adleman. A sticker-based model for DNA computation. Journal of Compuataional Biology, 5(4), pages 615–629, 1998. 14. U. Sch¨ oning. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Prooceedings of 40th Symposium on Foundations of Computer Science, pages 4