Context-free grammar (Part 2 of 2)

Last time on Context-Free Grammar: a context-free grammar (CFG) built arbitrarily complex structures out of syntactic blocks! Trains collided! Pigs flew! When the dust settled, a man was found to be eaten by his hamster! The boy he (the man) raised was bitten bitten by the dog he (the boy) owned! All this, the work of a CFG. But meanwhile, another CFG was stirring things up in... biology?

That last paragraph works best if read dramatically and in a low voice. FYI. Anyway... synthetic biology and context-free grammar. That is what I am now talking about.

No more distractions!

Synthetic biology is all about making complex (biological) structures out of parts assembled in standardized ways, which sounds very similar to a CFG. It shouldn't be all that surprising then that it is possible to re-write those standards as a set of rules forming a grammar. As I mentioned at the end of the last post though, it doesn't necessarily work that well.

So why is the usefulness of context-free grammars limited in biology? The answer is because they lack context.

...you mutter, but it's that simple: context-free grammars have the very particular property that the structure of any component is independent of the contents of other components. To (reluctantly) go back to the train analogy of yesterday, let's say each container has a dedicated inspector checking to make sure the contents of that container match its type. That inspector should be able to conclude whether or not the contents are valid without checking any other containers. So if a container were allowed to contain eggs if and only if there were chickens in nearby containers, the inspector would be stuck if he found an egg.

The missing word in the sentence is 'Bribery'.

This is problematic for synthetic biology because, as Andre brought up, biological parts are generally not self-contained. The 'validity' of different sequences would not be possible to determine with a CFG if components were capable of excisions, inversions, and merges depending on the contents of containers. For the non-biologists still reading, this would be like a container of our model train holding a robot that could bust through the side of the train and rearrange or destroy some or all of the other compartments ...or it might not, because it's a probabilistic robot that nobody really understands.

Robots that cause syntactic recombination through fiery explosions are often misunderstood.

The point is that biology is clearly too strange to ever fit into a grammar. Right? Well, maybe. It is still possible to have a container for crazy unpredictable things, they'll just have crazy unpredictable results. It's also possible to have separate trains/structures for all the different acceptable uses of the crazy thing.

To return way back to the egg and chicken proximity example, it would be possible to have two separate models of trains: one in which chickens are banned in the compartments surrounding the Formerly-UNinspectable Compartment (FUNC) and the FUNC is replaced with a container in which eggs are likewise banned; and one in which the compartments surrounding the FUNC must have chickens and the FUNC is replaced with a container that does allow eggs.

It's possible, then, to break up the unmanageable cases into a larger number of 'allowable' cases, but this could lead to an astronomical number of cases. More than that, it would also destroy the main cool thing about a CFG setup which is that it is constructive. It doesn't take much effort to make something really complicated and neat with a CFG by adding more and more nested parts to a structure, but when you start worrying about things like interacting parts and physical realizability or anything that frustratingly involves realism things start falling apart.

There is, however, still Context-Sensitive Grammars...

Dun dun dun!