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

7.6. Conclusions

In this chapter, we have identified an important practical application of the re-
cently introduced problem of detecting critical nodes to protein-protein interaction
networks. As indicated above, in many cases, potentially harmful biological or-
ganisms, such as bacteria and viruses that cause diseases, can be studied in terms
of their protein-protein interaction patterns. Therefore, finding the critical nodes
corresponding to the proteins that are the most important for the integrity of the
network would be very helpful in terms of identifying the proteins that need to
be targeted in the efficient process of destroying this network and neutralizing
the corresponding organisms. This approach can potentially be used in drug de-
sign applications, e.g., in developing drugs that target specific proteins that are
the most “important” in the considered networks. It would be interesting to con-
sider protein-protein interaction networks corresponding to different dangerous
viruses, such as HIV (although obtaining detailed information on these interac-
tions certainly represents another challenge) and identify key proteins that need to
be targeted to ensure that these networks are sufficiently disconnected.
In addition to their potential important practical applications, the considered
problems need to be studied from the computational perspective as well. As in-
dicated above, these problems are -hard, and the available exact and heuris-

tic methods do not always perform sufficiently well, especially on large problem
instances. Clearly, large-scale protein-protein interaction networks can provide
valuable information about the structure of complex molecules and organisms;
therefore, efficient techniques for solving the considered problems on massive
networks need to be developed.
Overall, we believe that the area of research proposed in this chapter is promis-
ing and challenging due to multiple reasons; therefore, this research clearly needs
to be conducted further, including both biological and mathematical aspects.

NP

References

[1] C. Alves, P. M. Pardalos, and L. N. Vicente, editors. Optimization in Medicine .

Springer, 2008.

[2] A. Arulselvan, C. W. Commander, L. Elefteriadou, and P. M. Pardalos. Detecting

critical nodes in sparse graphs. Computers and Operations Research , under revision,
2008.

[3] A. Arulselvan, C. W. Commander, P. M. Pardalos, and O. Shylo. Managing network

risk via critical node identification. In N. Gulpinar and B. Rustem, editors, Risk Man-
agement in Telecommunication Networks . Springer, 2008.