Biology Reference
In-Depth Information
Chapter 7
Identifying Critical Nodes in Protein-Protein Interaction Networks
Vladimir Boginski
Research & Engineering Education Facility (REEF)
Department of Industrial & Systems Engineering
University of Florida
Shalimar, FL 32579, USA
Clayton W. Commander
Air Force Research Laboratory
Munitions Directorate
Eglin AFB, FL 32542, USA
In recent years, the study of biological networks has increased dramatically.
These problems have piqued the interest of researchers in many disciplines from
biology to mathematics. In particular, many problems of interest to biological
scientists can be modeled as combinatorial optimization problems and studied by
operations researchers. In this chapter, we consider the problem of identifying the
critical nodes of a network and its potential applications to protein-protein inter-
action networks. More specifically, we are interested in determining the smallest
set of nodes whose removal from the graph maximally disconnects the network.
Recent techniques for identifying critical nodes in telecommunication networks
are applied to the study of protein-protein interaction graphs and the results are
analyzed.
7.1. Introduction
Optimization problems abound in the study of biological networks. This is a
timely research topic and has been the focus of great attention in the recent litera-
ture[1,4,6,19,21-23, 27]. In this chapter, we investigate the detection of
critical
nodes
in
protein-protein interaction networks
.The
CRITICAL NODE DETECTION
PROBLEM
(
CNDP
) is a combinatorial optimization problem recently introduced
by Arulselvan et al. [2]. Given a graph
G
=(
V,E
) andaninteger
k
∈
Z
\|
V
|
,
the objective is to determine a subset
A
⊆
V
, such that
|
A
|
=
k
, whose deletion
153
Search WWH ::
Custom Search