Natural examples of XOR functions at the cellular level

Question

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.

Answer 1

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