{'fraction_non_alphanumeric': 0.03756439610761305, 'fraction_numerical': 0.011448196908986834, 'mean_word_length': 5.132953049583151, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Topology of Biological Networks from a Complexity Perspective

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.


Introduction
At the intersection between biology and computer science lie two related areas of scientific inquiry. In one direction, in silico models of biological components/processes are used to gain insight into biology through algorithmics/statistics as exemplified in the field of bioinformatics. On the opposite direction, and since Adleman's insightful paper [1], computational problems (algorithms) are modeled (implemented) using biological components (processes) in a line of research that has rapidly evolved into the field of molecular computing. The computability/complexity [2] theory has not, however, been applied for the decipherment of actual biological systems. Given that the field of systems biology still lacks a foundational theory that can enable rigorous treatment of biological systems in a holistic manner, the complexity theory of computer science is proposed here for that purpose. It is a theory about machines, and biological systems are considered as such. Given its epistemological independence of physics and statistics, complexity theory can provide new insights into the evolution and functioning of biological networks, especially that the role that natural selection has in the evolution of network structure remains unknown [3].
In this work, a simple graph representation is used whereby nodes represent molecules and directed weighted edges represent promotional (positive weight) or inhibitory (negative weight) interactions. The addressed question is: given the universality (machine-independence) of the computability/complexity law, how do the effects of computational intractability manifest themselves in the evolution of biological networks? The network evolution problem (NEP) is defined formally and proved to be fundamentally hard (NP-hard) by reduction from the Knapsack Problem (KP).
For empirical demonstration, biological networks of experimentally validated interactions are compared to randomly generated networks with varying degrees of connectivity. Networks serve as KP instances (obtained by reversereduction) fed to a KP solver as input, and the latter's total knapsack value and weight is recorded for each network from multiple rounds of evolutionary pressure simulated by a hypothetical Oracle advice. The results show a clear link between a network's distance from biological networks (in degree distribution) and the maximum knapsack value-to-weight ratio achieved. In other words, biological networks show better adaptability as evolutionary pressure increases, and tolerance for errors decreases.
In Section 2, NEP is defined formally (2.1) and described informally (2.2). In section 3, theoretical and empirical results are presented. First, the NP-hardness of NEP is proven by reduction from the KP (3.1). Second, the data used in the empirical study is described (3.2). Third, the algorithmic workflow (3.3) and empirical results of computer simulations over the data are presented (3.4), comparing biological and synthetic networks. In section 4, conclusion a discussion and reflection on the results are presented.

Method
The evolution of biological networks is represented as a computational optimization problem. The definition is intended to compromise between opposing constraints: generality, to avoid symbolic bloat and artificial complexity, and specificity, to capture the reality of biological systems. It is also crucial that the proposed definition of the problem and the theoretical analysis of its complexity are easily falsifiable through empirical evidence. In this section, the network evolution (NEP) problem is defined formally then described informally, highlighting the correspondence between the model and actual biological systems.

Formal Definition of the Network Evolution Problem (NEP):
Given:    Define : → { , } that: The oracle advice can be imposed by forcibly repressing every gene where = − and forcibly promoting every gene where = + . However:  Repressing can inadvertently contribute to a violation of the oracle advice because is a also a promoter (repressor) of some that should in fact be promoted (repressed); and  Promoting can inadvertently contribute to a violation of the oracle advice because is also a promoter (repressor) of some that should in fact be repressed (promoted). What subset of genes should forcibly be promoted/repressed (define f) such that the oracle's advice is as satisfied as possible (maximize … subject to…)? The idealistic enforcement of an oracle advice is complicated by the reality of network connectivity.

Reduction of KNAPSACK T to NEP:
Given KNAPSACKOPT definition above, define an NEP instance as follows:

Data:
A total of seven networks, three biological and four synthetic, are used in this comparative study. All biological networks are from experimentally-validated interactions, while synthetic networks are computer-generated using various random graph generating algorithms. Table 1 summarizes properties of each network. The first biological network is obtained from IntAct database (actively humanly curated) [5] by submitting a Molecular Interaction Query Language (MIQL) query through PSICQUIC [6] (Proteomics Standard Initiative Common QUery of InteraCtions) implementation 1 . The resulting interactions from the query meet the following constraints: 1. Homo sapiens endogenous molecules only for both interactors. 2. Direct interactions (direct physical contact). 3. Supported by experimental evidence (as opposed to those inferred manually or computationally).
The resulting network is comprised of 1779 nodes and 3272 interactions (see Appendix A.1 for further details). Since the direction and sign of interactions are not provided by IntAct database (or any other molecular interaction database to our knowledge), they are assigned randomly. The second and third biological networks used in this study, obtained from Surantee et. al. (Table S3 in [7]) and Vinayagam et. al. (Table S7 in [8]), respectively, do however assign direction and sign (inhibitory or promotional) to each interaction 2 .
Synthetic network are obtained using various random graph-generating methods. The Scale-free and Barabasi-Albert (BA) networks have an average degree distribution (number of in-and out-edges) that follows a power law, making them similar to biological networks in network connectivity (last column in Table 1). Generally, in these two models, the probability of adding an edge to and/or from a node is proportional to its current degree (the more edges a node already has the more likely it will be further connected to new nodes). In the Erdos-Renyi (ER) model of generating random graphs [9], an edge between each pair of nodes is added with equal probability and independently of the current degree of both nodes. Lastly, Complete graph is one where each node is connected to every other node but itself. In all synthetic networks, both direction and sign of interactions (edges) are assigned randomly. Complete Computergenerated [10] random random 2000 1999 Table 1: Summary of network data sets used in this study. Random edge (interaction) direction and signs are assigned with a fair coin flip. Inferred edge are obtained computationally through a trained machine learning algorithm and its prediction accuracy is verified by cross-validation with known experimentally-validated directed/signed interactions (see text for details).

Algorithmic Workflow of Computer Simulation:
The simulation has two parameters: evolutionary pressure and tolerance . Evolutionary pressure is captured in the NEP definition by the Oracle advice A, and in each simulation we refer to = ∑ | | = as the number of nodes towards which the Oracle is not indifferent. For example, for a network G of n nodes, =5 implies there is a subset of 5 nodes = { , , , , } ⊂ where ∀ , ≠ and ∀ , = . The tolerance T is the optimization threshold in NEP definition (Section 2.1) or, equivalently, the knapsack capacity C in the corresponding KP instance (see reduction, section 3.1). For each network described in Section 3.2, a simulation is carried out for each = 5, , 5 , or 5 against each = 5, , 5 , or 5 .
Given a , pair, a knapsack instance is generated from a given network by reversing the reduction shown Section 3.1.2, that is: = , = , = , and = . The simulation records the total value and weight of objects (=nodes, recall = ) added to the knapsack by the solver (∑ { , }) for each round against a randomly generated Oracle advice on nodes. The simulation is repeated i=10,000 times (sampling threshold). Simulation time runs exponentially (days of execution time on 128 parallel CPUs). Using i=100,000 on IntAct and Suratanee networks over days of simulations produced virtually the same results (Appendix A.2). In the case of the Complete network, one round of simulation is sufficient (because its nodes have the same exact degree and edges have equal probability of direction/sign values). Figure 1 Table 2 and 3 show the average V and W values achieved after 10k rounds of simulation on each , pair for each network (except for the Complete network where 1 round for each , pair is sufficient). The highest V/W ratio achieved is highlighted (orange), and it shows a clear superior adaptability in biological (IntAct, Suratee, and Vingayam) and pseudo-Biological (BA and Scale-free) networks as they achieve highest scores at maximum pressure and lowest tolerance . Networks that are very distant in degree distributions from biological networks (ER and Complete) achieve high scores at low pressure, but display poor results as the pressure increases. Nonetheless, biological and pseudo-biological networks also show lower V/W ratio when tolerance increases but constant pressure (compare constant = 500 to variable =5, 10, 50 and 500). This may seem paradoxical since, conceptually, increased tolerance should imply improved adaptability. However, observing the same data (constant , variable ) shows that increased tolerance affects V/W ration not by lowering V but rather by increasing W, as seen in Figure 2.

Synthetic (computer-generated) Networks
BA Scale-free ER Complete n=2000 n=2000 n=2000 n=2000  Table 3: Results of simulation results on synthetic networks. The V, W are average values of 10k round of simulations on a given , pair. The V/W column shows the ratio of value-to-weight achieved. Maximum ratios for each network are highlighted (orange); n=number of nodes in a network. BA and Scale-free networks, which are of similar degree distributions to biological networks [11], expectedly show similar results to those in Table 2. ER and Complete networks show poor adaptability as increases, even with relaxed tolerance threshold . The graph shows the V/W ratio at the highest simulated evolutionary pressure p = 500 and increasing degrees of tolerance = 5, , 5 , and 5 . Blue columns represent maximum pressure ( = 5 ) at minimal tolerance ( = 5). Biological networks (IntAct, Suratanee and Vingayam) as well as synthetic networks BA and Scale-free (which are similar in degree distributions to biological networks [11]) achieve higher V/W ratio under maximum evolutionary pressure and minimal tolerance.

Discussion
This study is an attempt towards linking systems biology to the complexity theory of computer science. The aim was to employ the theoretical for the sake of the practical, and so the presented definition of the network evolution problem was intended to be general enough to avoid symbolic bloat and artificial complexity (which hinders falsifiability) but also specific enough to capture the intricacies of biological systems, ensuring its relevance and utility in the practical pursuit of understanding actual biological systems holistically. The empirical study juxtaposes biological networks to various synthetic ones, and the presented simulation results show clear indications that computational intractability does shape the evolution of biological networks (in their degree distributions, particularly). Further validation using a more systematic and comprehensive survey of synthetic networks is underway.

A.2 Simulation threshold:
Increasing the sampling threshold in each round of (p,t) pair to i=100,000 (i.e. 100k rounds of selction-without-replacement of k nodes to be presented for an Oracle advice) produce virtually the same results as i=10,000. It is worth noting that each V and W value presented is the average of all 10,000 or 100,000 V's recorded in each round of (p,t) pair.