Satisfiability, sequence niches, and molecular codes in cellular signaling

Abstract

Biological information processing as implemented by regulatory and signaling networks in living cells requires sufficient specificity of molecular interaction to distinguish signals from one another, but much of regulation and signaling involves somewhat fuzzy and promiscuous recognition of molecular sequences and structures, which can leave systems vulnerable to crosstalk. This paper examines a simple computational model of protein-protein interactions which reveals both a sharp onset of crosstalk and a fragmentation of the neutral network of viable solutions as more proteins compete for regions of sequence space, revealing intrinsic limits to reliable signaling 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.

References in corpus (7)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Coding limits on the number of transcription factors
• A rate-distortion scenario for the emergence and evolution of noisy molecular codes
• Core percolation and onset of complexity in Boolean networks
• Specific protein-protein binding in many-component mixtures of proteins
• The computational complexity of Kauffman nets and the P versus NP problem

Cited by in corpus (4)

• Sloppiness, robustness, and evolvability in systems biology
• Intrinsic limits to gene regulation by global crosstalk
• On the sufficiency of pairwise interactions in maximum entropy models of biological networks
• The Information Capacity of Specific Interactions