This morning I read Scott Aaronson’s post musing on the computational expressiveness of his son’s toy train set. This immediately triggered for me a flood of memories about my undergraduate days at Cal, where Scott and I overlapped for a few years (while he was younger than me, he was already in grad school). While there, I had the great fortune of being a researcher in Adam Arkin’s computational biology lab, where I could soak up mind-expanding ideas from the grad students, post-docs, and staff researchers about biological computing1, and computing about biology.

One area of interest was in determining what kinds of computation could be performed by cells or biochemical reaction networks2,3. While it has been shown that some cells have NAND-logic-like behavior4, it seemed that this was limiting, because there are only so many genes in a cell with that kind of behavior, and there are many other tricks up the sleeve of cells and DNA. It struck me that all of the string manipulation tricks that a genome can perform might provide a more expressive form of computation. While I did find one paper5 that tackled that directly, I thought that an analogous problem must have gathered much more attention, and thus there might be a richer vein of material to mine there.

I thought that the various proteins like RNA polymerase that process along the strands of DNA in a cell might be viewed as a train moving along a train track, where “stops” would be analogous to transcribing a gene6. I thought that all sorts of interesting modifications can happen to the “track”, like inversions. I dug for references online, and I came across this gem, which uses the common elements of train track switching to explore the universal computation capabilities of sufficiently designed train tracks: “Train Sets” by Adam Chalcraft and Michael Greene.

Alas, I lacked the training (no pun intended) to soak up all of this information and do anything significant with it. Till today I am fascinated with understanding how the cell meshes “analog” computation in the form of biochemical signal processing7, with the “digital” computation as expressed in the nucleotide sequence of the genome.

To find the above link, I had a dusty print-out that I had miraculously saved from my undergraduate days, but no further bibliographic information. Searching for the title and authors, I came across some related pages/articles:

Hopefully someone will find this assemblage of links amusing, or useful.

  1. Recent Developments in DNA-Computing ↩

  2. Chemical Kinetics is Turing Universal ↩

  3. Chemical Implementation of Finite-State Machines ↩

  4. Cellular Gate Technology ↩

  5. On the Power of Circular Splicing Systems and DNA Computability ↩

  6. Programmable and autonomous computing machine made of biomolecules ↩

  7. Motifs and Modules in Cellular Signal Processing ↩