Functionality and metagraph disintegration in boolean networks

We study regulatory networks of N genes giving rise to a vector expression profile v(t) in which each gene is Boolean; either on or off at any time. We require a network to produce a particular time sequence v(t) for t∈1,…,T and parameterize the complexity of such a genetic function by its duration T. We establish a number of new results regarding how functional complexity constrains genetic regulatory networks and their evolution. We find that the number of networks which generate a function decreases approximately exponentially with its complexity T and show there is a corresponding weakening of the robustness of those networks to mutations. These results suggest a limit on the functional complexity T of typical networks that is polynomial in N. However, we are also able to prove the existence of a, presumably small, class of networks in which this scales exponentially with N. We demonstrate that an increase in functional complexity T drives what we describe as a metagraph disintegration effect, breaking up the space of networks previously connected by neutral mutations and contrast this with what is found with less restrictive definitions of functionality. Our findings show how functional complexity could be a factor in shaping the evolutionary landscape and how the evolutionary history of a species constrains its future functionality. Finally we extend our analysis to functions with more exotic topologies in expression space, including "stars" and "trees". We quantify how the properties of networks that give rise to these functions differ from those that produce linear functional paths with the same overall duration T.