Identifying Critical Nodes in Protein-Protein Interaction Networks - Clustering Challenges in Biological Network - page 161

Fig. 7.5(b) and 7.5(c) respectively. The corresponding numerical results are pro-
vided in Table 7.1. The table contains the objective function values and the corre-
sponding computation times required by the algorithms. We provide the optimal
solutions as computed by CPLEX and the solutions provided by the heuristics
mentioned above. For this small, and relatively unconnected example, we see that
all the methods were able to obtain optimal solutions in a negligible amount of
time.

Table 7.1. Results of the IP model and the genetic algorithm for the 46
interactions of S. cerevisiae .
Instance IP Model Genetic Alg Comb. Alg

Max Conn. Obj Comp Obj Comp Obj Comp

Index ( L ) Va l Ti m e ( s ) Va l Ti m e ( s ) Va l Ti m e ( s )

2 8 0 . 18 8 0 . 05 8 0 . 04

3 6 1 . 19 6 0 . 01 6 0 . 00

4 5 2 . 57 5 0 . 05 5 0 . 00

1 . 05 0 . 01 0 . 00 5 4 4 4

6 4 2 . 63 4 0 . 04 4 0 . 00

The next network considered is from the 78 protein-protein interactions from
the development of D. melanogaster [29]. The graph of the network can be seen in
Fig. 7.6(a). Similar to the previous example, we provide the graphs corresponding
to the optimal solution for the cases of L =5and L =4.Table7.2reflects the
computational results for this instance. As above, we see that the heuristics were
able to provide the optimal solutions for each value of L tested. However, we
see that even for this relatively small instance, the required computation time to
compute the optimal solution has increased by two orders of magnitude from the
previous example.
As a final test case we examine the network comprising 186 yeast two-hybrid
system interactions of S. cerevisiae proteins [17]. The original network is shown
in Fig. 7.7. For this case, CPLEX was unable to compute optimal solutions for
any values of L . Therefore, we only provide solutions for the two heuristics in
Table 7.3. Notice that both heuristics computed the same objective function value
in each case. However, the combinatorial algorithm required over 30 seconds for
the case where L =2.
Though promising, these preliminary results indicate the need for advanced
heuristics and exact solution methods for computing critical nodes in protein-
protein interaction networks. The primary challenge to computing optimal solu-
tions in real-world networks is that the sizes of the networks prohibit optimal solu-
tions from being calculated using standard branch-and-bound techniques. The test
cases presented represent relatively small instances of protein-protein interaction