br The linear threshold model considers
The linear threshold model considers a threshold for each node and a weight for the incoming edge from
node . The values of and should be normalized so that they are in interval. Moreover, the sum of weights of incoming edges of any node should not exceed 1:
In each iteration of the algorithm, the active nodes will activate an inactive node if the sum of weights of incoming edges is at least equal to :
In Fig. 1, the linear threshold method is applied to a small toy model, which can be considered as a fictitious TRN.
In this model, the regulatory interactions are weighted and an activation threshold value is specified for each node.
Figure 1. At the beginning of the algorithm, node 1 is considered as an active node (gray) and other nodes are assumed to be inactive (white) (a). In the next step, the potential influence of the only active node on other nodes should be assessed. In (b) and (c), node 1 tries to activate node 3 and node 2 respectively which successfully activates node 2 but cannot activate node 3 because of insufficient weight of the edge connecting node 1 to node 3. There is no inactive node remained in this iteration (t=1) with incoming edge from an active node. Note that newly activated nodes cannot activate others in this iteration. Now, since no other node can be activated furthermore, this iteration will be ended. In the next iteration (t=2) (d), the node 3 cannot be activated, because it only has one incoming edge with insufficient edge weight as assessed in the (b). In (e) node 2 activates node 4 whereas cannot activate node 5 due to insufficient edge weight rather than value of node 5 (f). the node 3 cannot be activated
as mentioned above (g). In the next iteration (t=3), the node 4 is active and when the incoming edges of node 5 assessed (h), the sum of weights of incoming edges from node 2 and node 4, exceeds value of node 5 and it will be activated in this iteration. In the next iteration (t=4) (i), the node 3 cannot be activated. Finally, in (j), no node can be activated furthermore and the algorithm will be terminated.
We have used a combination of TRN with gene 112648-68-7 (GE) data as input of linear threshold approach of IM for finding CDGs. Each of the TFs exists in TRN, has been considered as initial active node to find out coverage (number of genes that it activates) of all nodes. Since only TFs in the network have outcome edges, for simplicity we have considered all of nodes as initial active node. In this model an active node can affect inactive nodes, indeed, the activation notion implies affecting downstream genes and showing the flow of GE change due to transcriptional regulation in the network which occurs in the cascading manner.
In this section we firstly describe the iMaxDriver pipeline, which comprises two different steps, namely, network construction and IM algorithm for finding CDGs. Finally, we describe the assessment of this pipeline, together with fifteen other cancer driver-predicting computational tools, based on three of available dataset benchmarks. The overall procedure of iMaxDriver method is shown in Fig 2.
Figure 2 The overall procedure of iMaxDriver method. At first, the network is constructed using raw TRN with associating threshold values for each node based on their gene expression values and weighting edges randomly or based on TRN edge weights. Finally, by using the modified IM algorithm with the constructed network as input, genes are ranked based on their coverage.
2.1 Network construction
2.1.1. Transcription regulatory network data
We considered RegNetwork database  (http://www.regnetworkweb.org/) as an example of a weighted TRNs to
be used as data source of iMaxDriver for weighted networks (iMaxDriverW). In RegNetwork, the list of gene regulatory interactions from different methods and multiple databases is collected. More specifically, we retrieved the human TRN data of RegNetwork obtained from all databases and all methods. It should be noted that RegNetwork, in addition to the TRNs, also contains microRNA regulatory interactions, which are omitted in the present study. The retrieved dataset contains 150,202 TF-gene and TF-TF regulatory interactions. In addition, we exploited the confidence values for assigning weights to interactions which is available in website of RegNetwork as ‘CONFIDENCE’ column in search page. The edge weight ing procedure was done based on the provided confidence of relationships, namely, ‘low’, ‘medium’ and ‘high ’. The ‘high’ confidence is used for experimentally validated regulations, ‘medium’ for predicted regulations in more than one method and the rest as ‘low’ confiden ce. We assumed 0.2, 0.5 and 0.8 respectively for low, medium and high confidence values as edge weights. According to structure of constructed network in influence maximization model, changing these values only could affect results slightly.