O'Reilly logo

Complex Networks by Kayhan Erciyes

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 10
Protein Interaction
Networks
10.1 Introduction
Proteins have important functions in cell biology such as transferring signals, con-
trolling the functions of enzymes and regulating activities in the cell. Proteins interact
with other proteins in the cell to form protein-protein interaction (PPI) networks to
perform important tasks in the cell such as cell cycle control, protein folding, transla-
tion and transcription. A protein may also modify another protein by interacting with
it in a PPI network. Understanding the role of interactions of proteins is believed
to provide molecular indications of health and disease states which can be used to
provide new drugs and therapies.
PPI networks can be modeled by graphs where nodes represent proteins and
edges show the interactions between them. These networks act as an interface be-
tween the genome and the metabolism as shown in Figure 10.1. They perform the
functions under the control of the genes which results in biochemical reactions gov-
erning metabolism. Using technologies such as mass spectrometry provided large
volumes of data of PPI networks; however, the size of data and the fact that it con-
tains significant noise make the analysis difficult.
There are many public PPI databases such as Munich Information center for Pro-
tein Sequences (MIPS) [26], Yeast Proteomics Database (YPD) [6], Database of In-
teracting Proteins (DIP) [39] and Human Reference Protein Database (HRPD) [12]
which contain data about PPI networks of various organisms. Recent studies have
shown that disease genes share common topological properties [28, 14]. Assessment
of the relationship between PPI network topology and biological function of PPI
networks and disease is a challenging and active research area.
203
204
Complex Networks: An Algorithmic Perspective
PPI Network
P4
P5
P3
P2
P1
GENOME
PROTEOME
protein−gen
e
interactions
METABOLISM
reactions
bio−chemical
Figure 10.1: Networks in the cell
A part of a protein that has a specific functionality such as signal transduction
and transcription is called a domain [30]. Functions performed by domains within a
protein include signal transduction, transcription and metabolism. The same domain
may be found in various proteins. A molecular pathway is a sequence of directed
molecular reactions to perform a process in the cell. A protein in a cell may regulate
the abundance of another, forming a pair with it. A genetic regulatory network in a
cell is formed by all such pairs of proteins.
In this chapter, we will first review the properties of PPI networks from the graph
theory point of view. We will then describe algorithms that are used to find clus-
ters in PPI networks. We will also describe network motifs and network alignment
algorithms in these and other biological networks.
10.2 Topological Properties of PPI Networks
Topology of the PPI networks is important to discover functions of unknown pro-
teins, to understand the evolution of protein interaction better and to understand the
high level functional organization in the cell. A fundamental aim in studying the
topology of the PPI networks therefore is to discover and predict the network struc-
ture that is related to the biological functions and processes in the cell. There are other
types of interactions in the cell such as the metabolic, signalling and transcription-
regulatory networks and all of these networks cooperate to result in the overall
Protein Interaction Networks
205
Figure 10.2: The PPI network of T. pallidum taken from [38]
function of the cell. An example protein interaction network of Treponema pallidum
including 576 proteins and 991 interactions is shown in Figure 10.2 [38]. Proteins
involved in DNA metabolism are shown as enlarged circles.
The structures of the PPI networks have been observed to have a scale-free topol-
ogy where P(k) k
2.2
[30], with a few high degree nodes called hubs and many
small degree nodes. These hubs are believed to have important roles in the overall
functioning of the network. Proteins in a PPI network interact with other proteins in
the same functional class but also with other proteins in different functional classes.
This property can be best described by the hierarchical clustering we have described
in Chapter 7. The clustering coefficient of a vertex u showed how well connected the
neighbors of u are and the average clustering coefficient was the average value of the
clustering coefficients of all vertices. Studies have shown that the average clustering
coefficient in PPI networks is almost constant, that is, it does not change significantly

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required