Biomolecular Computing at Binghamton

Our group at Binghamton is part of a consortium of research universities funded by DARPA and the NSF, working on issues in biomolecular computing. The main web page for the project is at Duke University . The group at Binghamton consists of

     Tom Head , Professor, Department of Mathematical Sciences
     Dennis Pixton , Associate Professor, Department of Mathematical Sciences
     K.J. Reddy , Assistant Professor, Department of Biological Sciences
     Elizabeth Laun , Graduate Student, Department of Mathematical Sciences
     Peggy Sullivan, Graduate Student, Department of Mathematical Sciences
     Masayuki Yamamura , Visiting Associate Professor from Tokyo Institute of Technology.

We have concentrated on the analysis and exploitation of splicing. There is a solid theoretical foundation for splicing as an operation on formal languages. In biochemical terms, procedures based on splicing may have some advantages, since the DNA is used mostly in its double stranded form, and thus many problems of unintentional annealing may be avoided.

The basic model is a single tube, containing an initial population of dsDNA, several restriction enzymes, and a ligase. Mathematically this is represented as a set of strings (the initial language), a set of cutting operations, and a set of pasting operations. Mathematically, the output of such a system is

The splicing language, consisting of all strings produced during the

The adult language, consisting of the strings that are produced by the

The limit language, consisting of those strings which remain in the system

The most studied of these is the splicing language, but the most relevant for analysis of an actual test tube is probably the limit language. This is a new concept, and it is not yet clear how to define it or what its basic properties are. For example, it is well known that the splicing language (given a finite splicing system) is always a regular language, but this is an open question for the limit language. The notion of adult language is intermediate between these.

Recently our two graduate students have made new contributions to basic splicing theory. Sullivan has extended the cutting and pasting formulation to a multiple test tube setting; the major new result is that the operations of pasting and filtering, without cutting, generate essentially the context-free languages. Laun has found an algorithm for detecting whether a regular language is a certain type of reflexive splicing language as studied recently by Head, and has produced the first example of a splicing language which is not a reflexive splicing language.

Experimental work

Our laboratory emphasis has been on demonstrating our splicing model and the basic properties of the splicing, adult and limit languages.

The first experiment serves to verify that the splicing model is viable in the laboratory. The splicing system involved initial strands of dsDNA, restriction enzymes and a ligase designed to produce new stings of dsDNA over time in one test tube. The observed results were those predicted by the splicing model. See the report by Laun & Reddy, below.

The second experiment involved a splicing system which generates a splicing language containing an adult language. The expected adult strands were observed, as were the other intermediate strands predicted by the model. (Results to be published.)

The most recent experimental design should serve to demonstrate the existence of a limit language associated with a splicing system. (Work in progress.)

Recent lab work has concentrated on constructing a prototype of DEL, the "Delphic Plasmid". This is a circular DNA molecule which provides a universal starting place for a uniform approach to a large variety of combinatorial problems.

Group Publications

Tom Head, Splicing Representations of Strictly Locally Testable Languages, Discrete Applied Math., 87 (1998), 139-147. (abstract, dvi or postscript)

Tom Head, Splicing Languages Generated with One Sided Context, in Computing With Bio-molecules: Theory and Experiments (Gh. Paun, ed.), Springer-Verlag, Singapore, 1998. (abstract, dvi or postscript)

Tom Head, Hamiltonian Paths and Double Stranded DNA, in Computing With Bio-molecules: Theory and Experiments (Gh. Paun, ed.), Springer-Verlag, Singapore, 1998. (abstract, dvi or postscript)

Tom Head, Circular Suggestions for DNA Computing, submitted. (abstract, dvi or postscript)

Tom Head, Relativised Code Concepts and Multi-Tube DNA Dictionaries, submitted. (abstract, dvi or postscript)

Tom Head, Masayuki Yamamura and Susannah Gal, AQUEOUS COMPUTING: Writing on Molecules, submitted. (abstract, dvi or postscript)

Elizabeth Laun and Kalluru J. Reddy, Wet Splicing Systems, in DNA Based Computers III (H. Rubin and D. H. Wood, eds.), DIMACS: Series in Discrete Mathematics and Theoretical Computer Science, v. 48, American Mathematical Society, Providence, RI, 1999. (abstract, dvi , html or postscript)

Elizabeth Goode and Dennis Pixton, Semi-simple Splicing Systems, in Where Mathematics, Computer Science, Linguistics and Biology Meet (C. Martin-Vide & V. Mitrana, eds.), Kluwer Academic Publishers, Dordrecht, 2001, pp. 343-352. (abstract, dvi, pdf, or postscript)

Dennis Pixton, Regularity of splicing languages, Discrete Applied Math., 69 (1996), no. 1-2, 99-122. (abstract, dvi or postscript)

Dennis Pixton, Linear and circular splicing systems, Proceedings of the 1st International Symposium on Intelligence in Neural and Biological Systems (May, 1996), 181-188. (abstract, dvi or postscript)

Dennis Pixton, Splicing in abstract families of languages, Theoretical Computer Science, 234 (2000), 135-166. (abstract, dvi or postscript)

Peggy Sullivan, Cut, Paste and Filter, submitted. (abstract, dvi, pdf, or postscript)