Constructing an RNA Computer with examples from chess

Laura Landweber, Dirk Faulhammer, Richard Lipton

Princeton University

We have expanded the field of "DNA Computers" to RNA and present a general approach for the solution of satisfiability (SAT) 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 x 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 x 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. I will discuss the scalability and limitations of this approach to molecular computing.

Figures and slide presentations describing our experiment:

http://www.princeton.edu/~lfl/DNA2DNA/RNAcomputer.pdf

http://rnaworld.princeton.edu/~fadirk/Knight.html