This Article Full Text Full Text (PDF) Supplemental Data Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a colleague Related Commentary in PNAS Similar articles in this journal Similar articles in ISI Web of Science Similar articles in PubMed Alert me to new issues of the journal Add to My File Cabinet Download to citation manager Request Copyright Permission Citing Articles Citing Articles via HighWire Citing Articles via CrossRef Citing Articles via ISI Web of Science (95) Citing Articles via Google Scholar Google Scholar Articles by Faulhammer, D. Articles by Landweber, L. F. Search for Related Content PubMed PubMed Citation Articles by Faulhammer, D. Articles by Landweber, L. F. Social Bookmarking                What's this?

 Previous Article  | Table of Contents |  Next Article 

Vol. 97, Issue 4, 1385-1389, February 15, 2000

Computer Sciences / Biochemistry
Molecular computation: RNA solutions to chess problems

(DNA computing / satisfiability / RNA evolution / in vitro selection / SELEX)

Dirk Faulhammer^*, Anthony R. Cukras^*, Richard J. Lipton, and Laura F. Landweber^*,

Departments of ^* Ecology and Evolutionary Biology and  Computer Science, Princeton University, Princeton, NJ 08544

Communicated by Andrew Chi-Chih Yao, Princeton University, Princeton, NJ, December 3, 1999 (received for review April 25, 1999)

We have expanded the field of "DNA computers" to RNA and present a general approach for the solution of satisfiability problems. As an example, we consider a variant of the "Knight problem," which asks generally what configurations of knights can one place on an n × n chess board such that no knight is attacking any other knight on the board. Using specific ribonuclease digestion to manipulate strands of a 10-bit binary RNA library, we developed a molecular algorithm and applied it to a 3 × 3 chessboard as a 9-bit instance of this problem. Here, the nine spaces on the board correspond to nine "bits" or placeholders in a combinatorial RNA library. We recovered a set of "winning" molecules that describe solutions to this problem.

CiteULike    Complore    Connotea    Del.icio.us    Digg    What's this?

Related Commentary in PNAS:

Computation with biomolecules

Junghuei Chen and David Harlan Wood
PNAS 2000 97: 1328-1330. [Extract] [Full Text]  

This article has been cited by other articles in HighWire Press-hosted journals:

				S. Beyer and F. C. Simmel A modular DNA signal translator for the controlled release of a protein by an aptamer Nucleic Acids Res., March 17, 2006; 34(5): 1581 - 1587. [Abstract] [Full Text] [PDF]

				J. J. Tabor, M. Levy, and A. D. Ellington Deoxyribozymes that recode sequence information. Nucleic Acids Res., January 1, 2006; 34(8): 2166 - 2172. [Abstract] [Full Text] [PDF]

				D. Tulpan, M. Andronescu, S. B. Chang, M. R. Shortreed, A. Condon, H. H. Hoos, and L. M. Smith Thermodynamically based DNA strand design Nucleic Acids Res., September 6, 2005; 33(15): 4951 - 4964. [Abstract] [Full Text] [PDF]

				M. R. Shortreed, S. B. Chang, D. Hong, M. Phillips, B. Campion, D. C. Tulpan, M. Andronescu, A. Condon, H. H. Hoos, and L. M. Smith A thermodynamic approach to designing structure-free combinatorial DNA word sets Nucleic Acids Res., September 2, 2005; 33(15): 4965 - 4977. [Abstract] [Full Text] [PDF]

				F. Tanaka, A. Kameda, M. Yamamoto, and A. Ohuchi Design of nucleic acid sequences for DNA computing based on a thermodynamic approach Nucleic Acids Res., February 8, 2005; 33(3): 903 - 911. [Abstract] [Full Text] [PDF]

				K. A. Schmidt, C. V. Henkel, G. Rozenberg, and H. P. Spaink DNA computing using single-molecule hybridization detection Nucleic Acids Res., September 23, 2004; 32(17): 4962 - 4968. [Abstract] [Full Text] [PDF]

				R. Adar, Y. Benenson, G. Linshiz, A. Rosner, N. Tishby, and E. Shapiro Stochastic computing with biomolecular automata PNAS, July 6, 2004; 101(27): 9960 - 9965. [Abstract] [Full Text] [PDF]

				X. Su and L. M. Smith Demonstration of a universal surface DNA computer Nucleic Acids Res., June 4, 2004; 32(10): 3115 - 3123. [Abstract] [Full Text] [PDF]

				M. Andronescu, R. Aguirre-Hernandez, A. Condon, and H. H. Hoos RNAsoft: a suite of RNA secondary structure prediction and design software tools Nucleic Acids Res., July 1, 2003; 31(13): 3416 - 3422. [Abstract] [Full Text] [PDF]

				Y. Benenson, R. Adar, T. Paz-Elizur, Z. Livneh, and E. Shapiro DNA molecule provides a computing machine with both data and fuel PNAS, March 4, 2003; 100(5): 2191 - 2196. [Abstract] [Full Text] [PDF]

				K. Sakamoto, H. Gouzu, K. Komiya, D. Kiga, S. Yokoyama, T. Yokomori, and M. Hagiya Molecular Computation by DNA Hairpin Formation Science, May 19, 2000; 288(5469): 1223 - 1226. [Abstract] [Full Text]

				J. Chen and D. H. Wood Computation with biomolecules PNAS, February 15, 2000; 97(4): 1328 - 1330. [Full Text] [PDF]

				R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, and L. Adleman Solution of a 20-Variable 3-SAT Problem on a DNA Computer Science, April 19, 2002; 296(5567): 499 - 502. [Abstract] [Full Text] [PDF]

Current Issue | Archives | Online Submission | Info for Authors | Editorial Board | About Subscribe | Advertise | Contact | Site Map Copyright © 2000 by the National Academy of Sciences