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

These networks play an important role in computational biology. In many cases,
they can be easily visualized and are convenient for understanding the complex
nature of different types of interactions between proteins. As a result of extensive
research efforts in studying protein-protein interactions for different biological
organisms (e.g., certain types of bacteria), massive amounts of data have been
obtained. In particular, detailed and comprehensive data on protein-protein in-
teractions is available for the yeast Saccharomyces cerevisiae , which has been
considered in a number of works. [16, 17, 25]
Moreover, protein-protein interactions are studied from the perspective of
drug design applications. [11, 24] In particular, drugs that target specific types
of proteins can be developed. This research direction has significantly grown re-
cently in the context of identifying target proteins responsible for certain diseases
based on the available protein-protein interaction data. Nowadays, experimental
studies in this area are extensively conducted by scientists in the pharmaceutical
industry and research communities. [20]
On the other hand, protein-protein interaction networks can be investigated
from the network optimization perspective. In this chapter, we make the first at-
tempt to put the aforementioned problem of identifying target proteins in protein-
protein interaction networks in the framework of combinatorial optimization.
Specifically, we propose to apply the recently introduced CRITICAL NODE DE -
TECTION PROBLEM ( CNDP ) to analyze protein-protein interactions and detect the
nodes (proteins) that are the most important for the connectivity of these networks.
We believe that identifying these critical nodes can provide information that can
be used in drug design and other applications.
Next, we discuss mathematical programming formulations of the considered
problems and present computational results obtained for some available protein-
protein interaction datasets.

7.3. Optimization Approaches for Critical Node Detection

Denote a graph G =( V,E ) as a pair consisting of a set of vertices V , and a set of
edges E . All graphs in this chapter are assumed to be undirected and unweighted.
For a subset W

V ,let G ( W ) denote the subgraph induced by W on G .A
set of vertices I ⊆ V is called an independent or stable set if for every i,j ∈
I, ( i,j )

⊆

E . That is, the graph G ( I ) induced by I is edgeless. An independent
set is maximal if it is not a subset of any larger independent set (i.e., it is maximal
by inclusion), and maximum if there are no larger independent sets in the graph.

∈