Progress since Aug, 1998:

Most significantly, we have successfully refined the RNA ‘mark and destroy’ algorithm which we introduced last year, to solve a 9-bit instance of a Satisfiability (SAT) problem derived from Chess (a 3 x 3 version of the Knight problem). The paper (see below) is currently under review, but the method is general for any type of SAT problem. Using the enzyme Ribonuclease (RNase) H to specifically cleave targeted RNA strands, we demonstrated that this effectively allows creation of a universal RNA restriction endonuclease, which means that the method is inherently scalable. We have also carried out the design of a 25-bit RNA library with the specific aim of extending our experimental protocol to address larger, more challenging NP-complete problems.

The paper which describes RNA solutions to the Knight problem (placement of knights on a 3 x 3 board) can be found at:

ftp://rnaworld.princeton.edu/pub/export/Knights.ps

 

Several others (see list below) are also available at

ftp://rnaworld.princeton.edu/pub/export/

 

Plans for the rest of FY99:

Now that we have successfully demonstrated that we can use RNA based computing to find solutions to a representative 9-bit problem, our immediate goals are 1) to enhance the technology to the point at which we can choose specific solutions. For example, can we modify the protocol to select the board with the most knights. 2) We will try our approach with a slightly more challenging 9-bit problem, the related Queens problem. 3) We will then synthesize the designed 25-bit library and begin experiments to test our approach and this library on larger versions of the current SAT problems (placement of knights or queens on a 4 x 4 or 5 x 5 board, for example) to test the scalability of the RNA approach.

 

Graphics:

 

RNA solutions to general SAT problems:

http://rnaworld.princeton.edu/~fadirk/slides_html (includes Powerpoint Slideshow)

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

 

DNA2DNA computations:

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

 

General illustrations (DHPP) and ciliate computations:

http://www.princeton.edu/~lfl/CiliateComputer/

 

 

Recent DNA Computing Publications:

 

• Landweber, L. F. and R. J. Lipton. (1997) DNA2DNA Computations: A potential ‘killer app’? In 24th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, pages 672-683, Springer-Verlag.

• Landweber, L. F. (1997) RNA Based Computing. DIMACS Technical Report 97-83.

• Landweber, L. F. (1998) The Evolution of DNA Computing: Nature's Solution to a Path Problem. IEEE Proceedings of Symposia on Intelligence and Systems '98, May 21-23, 1998. IEEE Computer Society Press, 133-139.

• Landweber, L. F. and L. Kari. (1998) The Evolution of DNA Computing: Nature's Solution to a Computational Problem. 1998 Genetic Programming Conference Proceedings, John Koza et al., eds., Morgan Kaufmann Publishers, Inc., 700-708.

• Landweber, L. F. (1999) RNA Based Computing. In DNA Based Computers II, L. F. Landweber and E. B. Baum, eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 181-189.

• Kari, L. and L. F. Landweber. (in press) Computing with DNA. Methods in Molecular Biology.

• Landweber, L. F., Lipton, R. J. and M. O. Rabin. (in press) DNA2DNA Computations: A Potential "Killer App"? In DNA Based Computers III, D.H. Wood, ed. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society.

• Forbes, N. A. and L. F. Landweber. (1999, in press) Computer Science and Meta-Evolution. Trends in Genetics.

• Landweber, L. F., Horton, T. L. and L. Kari. (in press) Evolution of Gene Scrambling and RNA Editing: Protists Perform Computations!

• Landweber, L. F. (in press) The Evolution of Cellular Computing. The Biological Bulletin.

• Landweber, L. F. and L. Kari. (in press) The Evolution of Cellular Computing: Nature's Solution to a Computational Problem, In DNA Based Computers IV, L. Kari, ed.

• Cukras, A. R., Faulhammer, D., Lipton, R. J. and L. F. Landweber (in press) Chess Games: A Model for RNA Based Computation. In DNA Based Computers IV, L. Kari, ed.

• Faulhammer, D., Lipton, R. J. and L. F. Landweber (in press) Counting DNA: Estimating the complexity of a test tube of DNA. In DNA Based Computers IV, L. Kari, ed.

• Landweber, L. F. and L. Kari (1999, to appear) Universal Molecular Computation in Ciliates. In Landweber, L. F. and Winfree, E., eds. Evolution as Computation. Springer-Verlag.

• Faulhammer, D., Cukras, A. R., Lipton, R. J. and L. F. Landweber (submitted) Molecular Computation: RNA Solutions to Chess Problems.

• Faulhammer, D., Lipton, R. J. and L. F. Landweber (in preparation for J. Comp. Bio.) Fidelity of enzymatic ligation in DNA computing.

Books

• Landweber, L. F. and Baum, E. B., eds. (1999) DNA Based Computers II. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.44, American Mathematical Society.

• Landweber, L. F. and Winfree, E., eds. (1999, to appear) Evolution as Computation. Springer-Verlag.

• Landweber, L. F., ed. (in preparation) Directed Evolution: The RNA Solution.

 

Invited Lectures, Seminars, and Colloquia on DNA Computing (Landweber)

 

• Sigma Xi Annual Meeting, Minneapolis, November 1999.

• The 11th Conversation in Biomolecular Stereodynamics, Albany, June 1999.

• Rockefeller University, "Computing with RNA: From Ribozyme and Genetic Code Origins to Chess" March 23, 1999.

• Universite de Montreal, March 16, 1999.

• University of Western Ontario, "Exploring information embedded in RNA: the origin of life, chess, and the genetic code" March 12, 1999.

• Harvard University, "Gene Scrambling and DNA Computing: The Origin of Biological information Processing" March 11, 1999.

• Stanford University, "Experimental RNA Evolution: From the origins of RNA catalysts to the genetic code and chess" March 9, 1999

• Princeton University Alumni Day, "Computing with DNA:" February 20, 1999.

• The Institute for Advanced Study, Princeton, NJ, "Computing with DNA and RNA: The Origin of Biological Information Processing" Feb. 17, 1999.

• Princeton Plasma Physics Laboratory, Science on Saturday Series, "DNA Computers" Feb. 13, 1999.

• NASA Goddard Space Flight Center, "DNA, Cells, and Computation" Jan. 8, 1999.

• Bellcore General Colloquium, "Biological Computation" Dec. 16, 1998.

• Santa Fe Institute, "Evolutionary and Computational Analysis of Complex Molecular Systems" Dec. 12, 1998.

• NSF RNA Workshop, "Three Problems with Information Encoded in RNA: RNA Editing without Guides, Chess, and the Genetic Code" Dec. 10, 1998.

• NIH/NIAID, "Evolution of Gene Scrambling and RNA Editing: Nature’s solutions to complex problems" Dec 8, 1998.

• New England Complex Systems Institute, "Universal Molecular Computation in Ciliates" Oct. 27, 1998.

• Stanford Department of Biological Sciences, "Gene Scrambling and DNA Computing: The Origin of Biological Information Processing" Oct. 12, 1998.

• NYU Graduate Sponsored Colloquium, "Gene Scrambling and Editing: The Origin of Biological Information Processing" Sept. 28, 1998.

• David Axelrod Institute, Albany, NY "Evolution of Gene Scrambling and Editing: Protists Perform Computations!" Sept. 22, 1998.

• Woods Hole, Molecular Evolution short course faculty "Gene Scrambling and Editing: The Origin of Biological Information Processing", Marine Biological Laboratory, Aug. 13, 1998

• Intl. Society Evolutionary Protistology (ISEP), Flagstaff, session chair, "Evolution of Gene Scrambling and Editing: Protists Perform Computations!" Aug. 2, 1998.

• Simon Fraser University, "Gene Scrambling and Editing: The Origin of Biological Information Processing" July 13, 1998.

• Genetic Programming '98 (with Lila Kari) The Evolution of DNA Computing: Nature's Solution to a Computational Problem.

• SIAM, SMB "DNA Computing and Molecular Evolution." Toronto, Ontario. July 13, 1998.

• Witten/Herdecke University, Germany. "Gene Scrambling and Editing: The Origin of Biological Information Processing" July 7, 1998.

• University of Leiden, Netherlands, "The Biology of DNA Computing" July 3, 1998.

• University of Leiden, "Chess Games: A Model of RNA Based Computing" July 2, 1998.

• Soc. for Study of Evolution Symposium on Simulated Evolution, "Knight Moves: Molecular Evolution and a DNA Computer" Vancouver, June 23, 1998.

• "The Evolution of Cellular Computing: Nature's Solution to a Computational Problem" 4th Annual Meeting on DNA Based Computers, U. Penn., June 16, 1998.

• "Chess Games: A Model for RNA Based Computation" 4th Annual Meeting on DNA Based Computers, U. Penn., June 16, 1998, Session Chair on Biochemistry, June 17, 1998.

• IEEE Intl. Symposium on Intelligence in Neural and Biological Systems, "The Evolution of DNA Computing: Nature's Solution to a Path Problem", May 22, 1998.

• University of Western Ontario, "Molecular Evolution of DNA Computing" London, Ontario, Canada, April 6, 1998.

• Rutgers University, Dept. of Computer Science, "Molecular Evolution of DNA Computing: Nature’s Solution to a Path Problem" March 11, 1998.

• NASA Ames, "Molecular Evolution of DNA Computing" Moffet Field, CA, March 5, 1998.

• "The Evolution of Cellular Computing" Yale University. Nov. 1997 Meeting of the New England Molecular Evolutionary Biologists.

• NASA Workshop on Evolution: A Molecular Point of View, "The Evolution of Cellular Computing," Woods Hole, MA, Oct., 1997. (reported in The Washington Post Dec. 15, 1997).

• "DNA2DNA Computations" Third Annual Meeting on DNA Based Computers, DIMACS Workshop, (with Richard Lipton) University of Pennsylvania, June, 1997.

• Houghten Pharmaceuticals (HPI). "DNA Computers" San Diego, CA, November 21, 1996.

• ICOS and Darwin Molecular, Inc. "DNA Computers". Seattle, WA, July 11, 1996.

• "RNA Based Computing: Some examples from in vitro selection of catalytic RNA" 2nd Annual Meeting on DNA Based Computers, DIMACS Workshop, Princeton University Dept. of Computer Science, June 10-12, 1996.