In silico network topology-based prediction of gene essentiality

The identification of genes essential for survival is important for the understanding of the minimal requirements for cellular life and for drug design. As experimental studies with the purpose of building a catalog of essential genes for a given organism are time-consuming and laborious, a computational approach which could predict gene essentiality with high accuracy would be of great value. We present here a novel computational approach, called NTPGE (Network Topology-based Prediction of Gene Essentiality), that relies on network topology features of a gene to estimate its essentiality. The first step of NTPGE is to construct the integrated molecular network for a given organism comprising protein physical, metabolic and transcriptional regulation interactions. The second step consists in training a decision tree-based machine learning algorithm on known essential and non-essential genes of the organism of interest, considering as learning attributes the network topology information for each of these genes. Finally, the decision tree classifier generated is applied to the set of genes of this organism to estimate essentiality for each gene. We applied the NTPGE approach for discovering essential genes in Escherichia coli and then assessed its performance.

Escherichia coli, a model organism whose most of genes have already been characterized experimentally as essential or non-essential.

II. CONSTRUCTION OF THE IMN OF E. COLI
As NTPGE relies on topological features of molecular network, the first step was to construct the Escherichia coli integrated molecular network (IMN) comprising protein physical, metabolic and transcriptional regulation interactions. For this purpose, we used MONET (MOlecular NETwork) ontology, a tool developed by our group that facilitates the construction of IMNs of organisms via integration of information from metabolic pathways, protein-protein interaction networks and transcriptional regulation interactions through a model able to minimize data redundancy and inconsistency [12]. As previously described, two genes of a given organism, g 1 and g 2 , coding for proteins p 1 and p 2 are linked if: • p 1 and p 2 interact physically, • g 1 regulates the transcription of gene g 2 , • or one metabolite generated by a reaction catalyzed by p 1 is consumed in a reaction catalyzed by p 2 (we may exclude from this analysis the most used compounds such as ATP, NAD, H2O, etc.).
The data sources present in MONET ontology used for the construction of the E. coli IMN were KEGG (Kyoto Encyclopedia of Genes and Genomes [13] for metabolic interactions, RegulonDB [14] for transcriptional regulation interactions, and Butland et al [15] for protein physical interactions.
Using MONET, we constructed two directed IMNs of E. coli, G a and G p . G a contained all possible interactions among genes with 1,998 genes and 51,642 interactions. G p was similar to G a , except that the connections through the ten most frequently used compounds on the metabolism were deleted producing a network with 1,987 genes and 21,338 interactions, since connections via these common compounds is not likely to be important for the determination of gene essentiality due to their promiscuity.

III. BRIEF ANALYSIS OF THE ESCHERICHIA COLI IMNS
Prior to use the Escherichia coli IMNs for the validation of the NTPGE approach, we present here a brief analysis of the most common network measures, i.e. degree distribution and clustering coefficient, of these IMNs. The degree distribution, P (k), gives the probability that a selected node has exactly k links. P (k) is obtained by counting the number of nodes N (k) with k = 1, 2,... links and dividing by the total number of nodes N . The clustering coefficient, C i , gives the density of triangles we can construct in the network having the node i as a vertex. The clusterization coefficient is defined as: where n i is the number of links connecting the k i neighbors of the node i. The average clustering coefficient C is the clustering coefficient for the whole network and characterizes the overall tendency of nodes to form clusters or groups. In Figure 1 we show the histogram of degree distribution for G a and G p . The curves are well approximated by a power law function, P (k) = Ak −γ for both IMNs, suggesting that G a and G p are scale-free networks. We also analyzed the dependence of the average clusterization coefficient, C, on the connectivity k, defined as C(k). For a traditional scale-free network, we expect C(k) not to depend on k, while for hierarchical networks we expect C(k) ∼ k −α . Figure 2 shows the C(k) for G a and G p . These results point to a C(k) not dependent on k for G a and a C(k) dependent on k for G p , thus indicating that G a is a non-hierarchical IMN and G p is an hierarchical IMN. This shift from a non-hierarchical topology for G a to an hierarchical topology for G p seems to be caused by the deletion of the connections through the ten most frequently used compounds in the metabolism on the construction of G p . Such compounds induce a strongly connected IMN due to their promiscuity.

IV. DESCRIPTION OF THE NTPGE APPROACH
The NTPGE approach was performed using WEKA (Waikato Environment for Knowledge Analysis) system [16]. WEKA is a collection of machine learning algorithms for data mining tasks. It also provides means for data preprocessing, classification, regression, clustering, association rules, and visualization [16]. Among these algorithms, we used the J48 [16], which is the Weka's implementation of the well known C4.5 [17] that uses the greedy technique to induce decision trees for classification. A decision-tree model is built by analyzing training data, which is then used to classify unseen data.
We trained the J48 algorithm on four different training configurations (t 1 , t 2 , t 3 and t 4 ). In all configurations, the training data was a set of known essential and non-essential genes of Escherichia coli taken from the PEC database (Profiling of Escherichia coli chromosome, http://www.shigen.nig.ac.jp/ecoli/pec/). The PEC database has been compiled experimental information on Escherichia coli strains from research reports and deletion mutation studies prior to 1998, including gene essentiality for cell growth. Based on these reports about gene essentiality for cell growth, the E, coli genes are classified in essential, non-essential and unknown. http://www.shigen.nig.ac.jp/ecoli/pec In all training configurations, for a given gene, the learning attributes used were as follows: • number of physical interactions for the corresponding encoded protein; • number of target genes transcriptionally regulated by the corresponding encoded transcription factor (regulation out); • number of transcription factors that regulate it; (regulation in); • number of enzymes that use metabolites produced by the corresponding encoded enzyme as reactants (metabolism out); • number of enzymes that produce metabolites used as reactants by the corresponding encoded enzyme (metabolism in); In t 1 and t 2 , the above mentioned attributes were extracted from G a , whereas these same attributes were extracted from G p in t 3 and t 4 . Moreover, the attribute damage, which was not originally present in G a and G p , was included in t 2 and t 4 , The damage d is defined as the number of metabolites whose production was prevented by the deletion of the enzyme. For a given enzyme, its damage d has been shown to be strongly correlated to its essentiality. [18].
The J48 algorithm was trained with the parameters presented in Table I. As it has been known that data imbalance is one of the causes that degrade the performance of machine learning algorithms [19], we replicated the data related to the essential genes in order to correct data imbalance as the number of non-essential genes is much larger than the number of essential genes.

V. PERFORMANCE OF THE NTPGE APPROACH AND RELATED DISCUSSION
The performance of the NTPGE approach was evaluated by testing the classifiers created by the J48 algorithm, as described above, on the training data itself. The selection of the best training configuration to be considered as default by the NTPGE approach was performed based on the F-measure of the corresponding generated classifier. The F-measure provides an harmonic mean of precision and recall and is defined as: Precision (the percentage of correctly classified instances) and recall (the percentage of positive labeled instances that were classified as such) were calculated from the confusion matrices of the classifiers obtained from the training configurations t 1 , t 2 , t 3 and t 4 (Tables II) and are shown on Table III. Table III also shows the F-measure as well as the features of the training configurations, as the number of instances (genes plus metabolites) and presence or absence of the learning attribute damage d on training.
According to Table III, the best training configuration was t 1 (all genes and metabolites with the attribute damage). Its corresponding generated classifier had a F-measure of 83.4% for essential genes and 79.7% for non-essential genes. In fact, all generated classifiers yielded similar results, suggesting that the presence or absence of the ten most used compounds in metabolism or the presence or absence of the attribute damage d did not affect the classification of genes as essential or non-essential by the NTPGE approach. Therefore, any training configuration could be selected as default by NTPGE.   a The number of essential genes were replicated to avoid data imbalance; number of non-essential genes remained unchanged. Actually, the number of essential genes is 209 and non-essential genes is 1,789 for Ga and the number of essential genes is 209 and non-essential genes is 1,778 for Gp   FIG. 3: Decision tree generated from t1 with a F-measure of 83.4% for essential genes (E) and 79.7% for non-essential genes (N). The (x/y) inside rectangles denotes the number of correctly classified genes (x) and the number of incorrectly classified genes (y). Figure 3 shows the set of rules of the decision tree generated from t 1 . The top node of the tree corresponds to the attribute protein physical interaction. This means that the classification tree algorithm concluded that the main factor to define essentiality in E. coli was the protein physical interaction. In fact, the degree of a protein has been documented in the literature as being indicative of essentiality in various organisms [9,20,21]. In our approach, a combination of intermediate number of protein physical interactions with at least one interaction of the type metabolism in, i.e. number of enzymes that produce metabolites used as reactants by the corresponding encoded enzyme, was also indicative of essentiality. Transcriptional regulation interactions seems not to be a good predictor for gene essentiality, since genes with at least one interaction of the type regulation out, i.e. number of target genes transcriptionally regulated by the corresponding encoded transcription factor, were classified as non-essential. Moreover, the attribute (regulation in, i.e. the number of transcription factors that regulate a given gene, was not even included in the decision tree. These results regarding gene essentiality and transcriptionall regulation are not surprising, since transcription factors are usually not essential under the conditions in which the knockout experiments for determining gene essentiality are performed (PEC database, http://www.shigen.nig.ac.jp/ecoli/pec/)

VI. CONCLUDING REMARKS
We proposed here a novel machine learning-based computational approach, called NTPGE (Network Topologybased Prediction of Gene Essentiality), that relies on network topology features of a gene to estimate its essentiality. Distinct from previous network topology-based gene essentiality predictors, NTPGE employs multiple topological network features of a given gene to estimate its essentiality, namely physical interactions for the corresponding encoded protein, number of target genes transcriptionally regulated by the corresponding encoded transcription factor, number of transcription factors that regulate it, number of enzymes that use metabolites produced by the corresponding encoded enzyme as reactants and number of enzymes that produce metabolites used as reactants by the corresponding encoded enzyme.
We verified the performance of NTPGE by applying it for the discovery of essential genes in the bacterium Escherichia coli, a model organism whose most of genes have already been characterized experimentally as essential or non-essential. Among the interactions considered as learning attributes, NTPGE relied mostly in protein physical and metabolic interactions for gene essentiality prediction. In addition, the presence or absence of the ten most used compounds in metabolism or the presence or absence of the attribute damage d did not likely influence the classification of genes as essential or non-essential by NTPGE. This can be concluded because the F-measure values of all generated decision trees were similar. Anyway, the best classifier was generated from t 1 (all genes and metabolites with the attribute damage) with a F-measure of 83.4% for essential genes and 79.7% for non-essential genes.
In conclusion, the NTPGE seems to be a reliable method of gene essentiality discovery that may be applied to the gene set of other organisms. However, NTPGE is limited to organisms whose corresponding IMN has already been constructed. The construction of the IMN of a given organism involves the gathering of experimentally determined data that are not always available, particularly for a newly sequenced organism. To overcome this limitation, future developments would be the integration of NTPGE with sequence-based methods of IMN construction, thus creating a purely in silico network topology information-based methodology of gene essentiality discovery.