Hi Everyone!<br>
<br>
I was talking to Daniel and Hugo yesterday about an interesting problem with applications in DNA computing. I thought I'd share a description and maybe give you guys some ideas for your next just-for-fun toy program! So here's how it goes:<br>
<br>
-----<br>
<br>
A strand of DNA is a string over the alphabet {A,T,G,C}, where (A,T) and (G,C) are matching base pairs. An important operation that certain enzymes can perform on DNA is called inversion (denoted x*), which reverses the string and replaces every symbol by it's base pair match. For example:<br>
<br>
GATTACA* =TGTAATC<br>
AATT* = AATT<br>
<br>
Note that (x*)* == x, for all x<br>
And that (x y)* == y* x*<br>
<br>
There are certain strings which have semantic meaning for special [DNA processing enzymes][1], called *recognition sites*. A recognition site, x, is always matched by it's inverse, x*. One tells a recombinase enzyme to start, and the other tells it to stop. Since we're computer scientists, we can think of these restriction sites as pairs of matching parentheses. For example:<br>
<br>
If<br>
    [ == AGTATC<br>
Then<br>
    ] == [* == GATACT<br>
<br>
It doesn't matter what the actual strings are, they're just short arbitrary markers. When the enzyme finds a substring enclosed in two opposing parentheses, it replaces the string with its inverse then deletes the parentheses. On the other hand, if it sees something between two of the *same* parentheses, then the whole thing will be deleted. For example:<br>
<br>
x [ y ] z  ->  x y* z<br>
x [ y [ z  ->  x z<br>
<br>
Importantly, the recombinase enzyme doesn't care whether the recognition site is "facing in" or "facing out" – it can only detect whether they match or mismatch. So the previous example would be equivalent to this:<br>
<br>
x ] y [ z  ->  x y* z<br>
x ] y ] z  ->  x z<br>
<br>
A completely unmatched paren in the string has no effect whatsoever, the enzyme just leaves it:<br>
<br>
x [ y  ->  x [ y<br>
<br>
Also, parens don't need to be properly nested:<br>
<br>
x [ y [ z ] w  ->  x z ] w<br>
x [ y ( z ] w  ->  x z* ) y* w<br>
<br>
Notice that the []-enzyme ignored the "(", because every recombinase only searches for it's own specific marker. The process is also un-lazy, it starts as soon as it can, and stops as soon as it can. One last thing to notice about this system: *order matters!* Say we have this string:<br>
<br>
x { y ] z { w [ v<br>
<br>
If we give it to the {}-enzyme then the []-enzyme, we get this:<br>
<br>
{}:  x w [ v<br>
[]:  x w [ v<br>
<br>
But if we do this the other way around, we get this:<br>
<br>
[]:  x { y w* } z* v<br>
{}:  x w y* z* v<br>
<br>
And those are all the rules. It turns out your cells process DNA using this crazy programming language that looks like the hybrid baby of lisp and brainfuck! Who knew?<br>
<br>
-----<br>
<br>
So now that you're an expert in this string rewriting system, I have a problem for you:<br>
<br>
Write a program that takes as input a  "DNA" sequence, encoded as an alternating series of letters and parentheses, and outputs the number of different results you could get back by running the recombinase enzymes in different orders.<br>
<br>
You can assume that no two symbols are repeated twice in the sequence (except for mismatched brackets!), and that it's impossible to accidentally create a new recognition site by gluing two unrelated subsequences together, like this:<br>
<br>
If<br>
    [ = ATCA<br>
    ] = TGAT<br>
Then<br>
    A(GA)A GCA (CAA)AT  -><br>
    ATCA GCAT TGAT  =<br>
    [ GCAT ]  ->  ATGC<br>
<br>
I have a strong hunch this happens in real life, which would make mother nature seem *waaay* more hacker than I ever gave her credit for. Anyways, this problem doesn't require you to think at all about the underlying base-pair encoding!<br>
<br>
This originally came to me via [Scott Aaronson's blog][2], which you can read of you're interested in learning more. In that post he actually proves an upper bound of 2^n for the number of distinct outputs, where `n` is the number of different types of parentheses in the input sequence. This is surprising, because you'd expect to find a case where *every* permutation of enzymes gives a different result, which would raise that upper bound to n!.<br>
<br>
Anyways, have fun!<br>
- Jesse<br>
<br>
[1]: <a href="https://en.m.wikipedia.org/wiki/Recombinase">https://en.m.wikipedia.org/wiki/Recombinase</a><br>
[2]: <a href="http://www.scottaaronson.com/blog/?p=2862">http://www.scottaaronson.com/blog/?p=2862</a>