We propose a complexity-theoretic approach to studying biological networks . We use a simple graph representation of biological networks capturing objects (molecules : DNA, RNA, proteins and chemicals) as nodes, and relations between them as directed and signed (promotional (+) or inhibitory (-)) edges. Based on this model, we formally define the problem of network evolution (NE) and subsequently prove it to be fundamentally 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 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 as evolutionary pressure increases . The more distant (in degree distribution) a synthetic network is from biological networks the lower its achieved ratio. This reveals how computational intractability has shaped the evolution of biological networks into their current topology . We propose a restatement of the principle of "survival of the fittest" into the more concrete "survival of the computationally efficient" .
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 .
R
We propose a
A
R
. We use a
is proposed. A
R
of biological networks capturing objects (molecules :
is used where molecules (
R
as nodes,
are vertices
R
as
are
D
we formally define
R
and subsequently prove it
is defined formally as an optimization problem and subsequently proven
A
(NP-hard)
R
random
synthetic (random)
R
as evolutionary pressure increases
at maximal evolutionary pressure and minimal error tolerance conditions
R
This reveals
The results shed light on
D
. We propose a restatement of the principle of "survival of the fittest" into the more concrete "survival of the computationally efficient"