Satisfiability, sequence niches and molecular codes in cellular signalling

Biological information processing as implemented by regulatory and signalling networks in living cells requires sufficient specificity of molecular interaction to distinguish signals from one another, but much of regulation and signalling involves somewhat fuzzy and promiscuous recognition of molecular sequences and structures, which can leave systems vulnerable to crosstalk. A simple model of biomolecular interactions that reveals both a sharp onset of crosstalk and a fragmentation of the neutral network of viable solutions is examined as more proteins compete for regions of sequence space, revealing intrinsic limits to reliable signalling in the face of promiscuity. These results suggest connections to both phase transitions in constraint satisfaction problems and coding theory bounds on the size of communication codes.