# Natural examples of XOR functions at the cellular level

We can often think of cells as a sort of circuit on macromolecules, and can show that they can accurately and robustly implement functions like $$\text{MAJ}(x_1,...,x_n)$$ (return $$1$$ if more than half of $$x_1,...,x_n$$ is $$1$$ and $$0$$ otherwise) under natural conditions (Cardell & Csikász-Nagy, 2012).

Not all functions are created equal. $$\text{XOR}(x,y)$$ is a boolean function that is $$1$$ if exactly one of $$x$$ or $$y$$ is $$1$$ and $$0$$ otherwise (i.e, if $$x = y$$). It is often generalized to a multi-input function parity (or odd) as $$\text{ODD}(x_1,...,x_n)$$ which returns $$1$$ if an odd number of $$x_1,...,x_n$$ is $$1$$. Notice that this is superficially similar to $$\text{MAJ}$$ but is doing its counting in base 2, which one would expect to be easier for say finite state machines.

However, in some ways, this sensitivity makes the function much more difficult to the point that Valiant (2009) writes:

[Parity] appears to be biologically unnatural. That is exactly the prediction of our theory, which asserts that evolution cannot be based on the evolvability of [the class of functions parity belongs to]

Synthetic biologists used to agree to some extent, with Tamsir et al. (2011) writing that the closely related XNOR (i.e. $$\text{XNOR}(x,y) = 1 - \text{XOR}(x,y)$$) is empirically impossible to implement. However, they were proven wrong when Bonnet et al. (2012) implemented XNOR among many other amplifying gates by exploiting the structure and process of transcription. Unfortunately, this is an example from synthetic biology, and I really want to learn ones (if any) that occur naturally.

Are there any examples of XOR or related gates implemented (without human engineering) at the cellular level? Are there any naturally occurring molecular pathways that compute something similar to parity? (i.e. something similar to the majority result, but for a more 'sensitive' function) I am primarily interested in empirical demonstrations, but I would be satisfied with theoretical examples that are appealing to biologists (i.e. not something purely comp. sci. like P-systems or something).

### References

Bonnet J, Yin P, Ortiz ME, Subsoontorn P, & Endy D (2013). Amplifying Genetic Logic Gates. Science, 340(6132): 599-603. PMID: 23539178

Cardelli L, & Csikász-Nagy A (2012). The cell cycle switch computes approximate majority. Scientific Reports, 2: 656. PMID: 22977731

Tamsir, A., Tabor, J. J., & Voigt, C. A. (2011). Robust multicellular computing using genetically encoded NOR gates and chemical wires. Nature, 469(7329), 212-215.

Valiant, L.G. (2009) Evolvability. Journal of the ACM, 56(1): 3-22.

• Benenson (2012) also offers a synthetic example. nature.com/nrg/journal/v13/n7/fig_tab/nrg3197_F6.html I'll leave the answering of your primary question about natural examples to the actual experts. I am but the greenest of dilettantes in this field. – Jonathan Van Matre Feb 14 '14 at 22:51
• What's interesting to me is that it's not hard to come up with XOR gate implementations that sound biologically plausible: gene X is activated by two separate activators A and B. When present at the same time A and B bind each other strongly in such a way that their DNA binding domains are occluded, decreasing the transcription of X. It would be a leaky XOR gate, but it seems pretty biologically plausible. But my cursory search didn't yield much on competing trans-activators that can heterodimerize... – A. Kennard Feb 16 '14 at 2:47
• Empirical examples can be thought of but whether natural examples exist or not depends on the usefulness of XOR gate in biological systems. Considering a typical application of XOR, I can't see where a cell would want a binary adder. If we find an application we would find the example too. Can anyone think of its application ? – WYSIWYG Feb 17 '14 at 3:58
• @ArtemKaznatcheev.. by empirical i meant engineer-able. However I see a situation where XOR might find a role but am not sure if the gate exists. Morphogen/Chemokine gradient: if A = left to right gradient, B = right to left gradient...and output is defined as cell migration/development pattern then a XOR gate is implemented as A=1,B=1 will not produce a gradient for the cell to respond. – WYSIWYG Feb 18 '14 at 6:06
• @ArtemKaznatcheev.. In fact I also have a hunch that lymphocyte activation is a likely place where XOR logic is used. I found another example: can't call it a perfect XOR Gate.. but the study says that combination of multiple antibiotics is actually not doing the job well compared to single drug treatment. Somewhat close... *PS: please let me know how adders can track period and wrt any prime numnber (it just increases the number of bits right. Pls fwd me texts on this if you can.Thanks) – WYSIWYG Feb 18 '14 at 6:16

When I think about your question of natural examples of XOR, it pushes me to think about what type of natural environments (i.e., evolutionary pressures) would lead to the selection of an XOR equivalent.

When we implemented a synthetic XOR by "double flipping" one transcription terminator as a type of gene expression "check valve" it was the case that I did not know of any natural examples of flipping terminators, whereas I know of several examples of nature flipping promoters.

Why do we have plenty of natural examples of flipping promoters but (unknown to me at least) as yet no charismatic examples of naturally flipping terminators?

Perhaps we haven't been looking in the right environments to find them?

E.g., for a terminator to exist in nature, there needs to be something that must be expressed upstream of the terminator, and also something that should not be expressed downstream of the terminator. Since there are plenty of terminators there must plenty of examples of nature selecting for terminators. My favorite example is the "Tø" terminator in phage T7 that is just downstream of the major capsid gene (highly expressed) but just upstream of a minor particle protein (weakly expressed).

But now reason thru what would need to be true in order to select for terminator flipping. I'd need all the requirements of a static terminator (above), and then another such pairing of selective requirements under different environmental circumstances for additional gene products encoded in the opposite direction on the complementary strand of DNA. Phew!

I'm not saying that it is impossible to imagine such a complicated coupling of selection requirements emerging in nature, but it definitely seems a much more improbable aggregation of selective pressures to co-mingle all within a single genetic loci.

I'm still nevertheless very curious and would be grateful to learn of any natural examples. -DE