Computational Intractability Law Molds the Topology of Biological Networks

Abstract

Virtually all molecular interaction networks (MINs), irrespective of organism or physiological context, have a majority of loosely-connected leaf genes interacting with at most 1-3 genes, and a minority of highly-connected hub genes interacting with at least 10 or more other genes. Previous reports proposed adaptive and non-adaptive hypotheses describing sufficient but not necessary conditions for the origin of this majority-leaves minority-hubs (mLmH) topology. We modeled the evolution of MINs as a computational optimization problem which describes the cost of conserving, deleting or mutating existing genes so as to maximize (minimize) the overall number of beneficial (damaging) interactions network-wide. The model 1) provides sufficient and, assuming [Formula], necessary conditions for the emergence of mLmH as a software adaptation to circumvent computational intractability, 2) predicts the percentage number of genes having d interacting partners, and 3) when employed as a fitness function in an evolutionary algorithm, produces mLmH-possessing synthetic networks whose degree distributions match those of equal-size MINs.\n\nSummaryOur results indicate that the topology of molecular interaction networks is a selected-for software adaptation that minimizes the evolutionary cost of re-wiring the network in response to an evolutionary pressure to conserve, delete or mutate existing genes and interactions.