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

from the graph results in a minimum cohesion and ensures a minimum differ-
ence in the sizes of the components. A related problem, the CARDINALITY CON -
STRAINED CNDP ( CC - CNDP ) seeks to determine a minimum cardinality subset of
nodes whose deletion ensures that the number of nodes reachable from any other
node in the network does not exceed some threshold value.
The CNDP has applications in many fields including social network analysis,
quality assurance and risk management in telecommunication networks, trans-
portation science, and control of social contagion [2, 3, 7]. Our proposition is
that identifying the critical nodes in protein-protein interaction networks can have
applications in computational biology, in particular in drug design. The interpre-
tation of the critical nodes in the context of protein-protein interaction networks
is that these nodes represent a minimum cardinality set of proteins whose removal
would destroy the primary interactions and thus help neutralize potentially harm-
ful organisms (e.g., bacteria or viruses).
The organization of this chapter is as follows. In the next section, protein-
protein interaction networks are discussed. In Section 7.3, we provide mathemat-
ical programming formulations for both variants of the CRITICAL NODE DETEC -
TION PROBLEM described above. In Section 7.4, we discuss the implementation
of several heuristics for both problems, and provide some preliminary computa-
tional results of critical node detection on real-world protein-protein interaction
networks in Section 7.5. Conclusions and future directions of research are identi-
fied in Section 7.6.

7.2. Protein-Protein Interaction Networks

In recent years, the biological research community's interest in studying proteins
from different aspects has steadily increased. As a result, the field of proteomics ,
which investigates proteins' structures and functions, has been developed. In par-
ticular, protein-protein interactions have been extensively studied using various
advanced techniques. [5, 14, 15, 26, 28] Many biological functions involve inter-
actions between proteins at different levels, including signal transduction in cells
(i.e., conversion of one kind of a signal to another inside a cell, which may play an
important role in biological processes, including disease development), formation
of protein complexes (i.e., stable over time structures involving multiple proteins),
brief interactions between proteins involving the processes of modification of one
protein by another, etc.
Protein-protein interactions can be represented in terms of graph theory as a
set of vertices (proteins) and edges (certain types of interactions between pro-
teins). These structures are referred to as protein-protein interaction networks .