  A complexity-theoretic approach to studying biological networks is proposed.
A simple graph representation is used where molecules (DNA, RNA, proteins and
chemicals) are vertices and relations between them are directed and signed
(promotional (+) or inhibitory (-)) edges. Based on this model, the problem of
network evolution (NE) is defined formally as an optimization problem and
subsequently proven to be fundamentally hard (NP-hard) by means of reduction
from the Knapsack problem (KP). Second, for empirical validation, various
biological networks of experimentally-validated interactions are compared
against randomly generated networks with varying degree distributions. An NE
instance is created using a given real or synthetic (random) network. After
being reverse-reduced to a KP instance, each NE instance is fed to a KP solver
and the average achieved knapsack value-to-weight ratio is recorded from
multiple rounds of simulated evolutionary pressure. The results show that
biological networks (and synthetic networks of similar degree distribution)
achieve the highest ratios at maximal evolutionary pressure and minimal error
tolerance conditions. The more distant (in degree distribution) a synthetic
network is from biological networks the lower its achieved ratio. The results
shed light on how computational intractability has shaped the evolution of
biological networks into their current topology.
