Network Querying Techniques for PPI Network Comparison

Network Querying Techniques for PPI Network Comparison

Valeria Fionda (Università della Calabria, Italy) and Luigi Palopoli (Università della Calabria, Italy)
Copyright: © 2009 |Pages: 23
DOI: 10.4018/978-1-60566-398-2.ch017
OnDemand PDF Download:


The aim of this chapter is that of analyzing and comparing network querying techniques as applied to protein interaction networks. In the last few years, several automatic tools supporting knowledge discovery from available biological interaction data have been developed. In particular, network querying tools search a whole biological network to identify conserved occurrences of a query network module. The goal of such techniques is that of transferring biological knowledge. Indeed, the query subnetwork generally encodes a well-characterized functional module, and its occurrences in the queried network probably denote that this function is featured by the associated organism. The proposed analysis is intended to be useful to understand problems and research issues, state of the art and opportunities for researchers working in this research area.
Chapter Preview


Biological data about molecular interactions are growing quickly. This fast growth has rendered the design and the development of automatic tools necessary for retrieving interesting information and discovering new knowledge. Interaction data are usually represented through the biological networks model. The comparison of such biological networks across species or different conditions is useful to understand the mechanisms underlying life processes (Zhang, 2008). Generally, biological networks are represented as graphs that can be fed as input to techniques suitable for topological and functional comparison. Such techniques analyze those networks by exploiting specialized algorithms and methodologies in order to infer new information about cellular activity and evolutive processes of the species.

A graph is a set of objects called nodes or vertices and connected by links called edges. More formally, a graph is an ordered pair G = (V, E), in which V is the set of nodes and E is the set of edges, so that the elements from E are pairs of elements from V. In an undirected graph, an edge linking nodes A and B can be traversed in both directions. In a directed graph, each edge is intended to be traversable in just one direction.

Different types of graphs are used to represent different types of biological networks. In fact, several kinds of biological networks have been defined, each of which stores interaction information related to specific entities or molecules. Main types of networks thereof are: transcriptional regulatory networks, signal transduction networks, metabolic networks and protein interaction network (or PIN). In the transcriptional regulatory networks the nodes of the graph represent genes and the edges are directed. An edge connects a source gene to a target gene if the source gene produces an RNA or protein molecule that functions as a transcriptional activator or inhibitor of the target gene. If the gene is an activator, then it is the source of a positive regulatory connection; if it is an inhibitor, then it is the source of a negative regulatory connection. In the signal transduction networks, the graph vertices represent proteins and the edges are directed. This type of network stores information about the processes by which a cell converts one kind of signal or stimulus into another. In particular, the signal transduction corresponds to the relaying of molecular signals or physical ones (for example, sensory stimuli) from a cell's exterior to its intracellular response mechanisms. In the Metabolic networks, the nodes represent metabolites and the edges are directed. These networks store the set of metabolic and physical processes of the cell and comprise the chemical reactions underlying the metabolism as well as the regulatory interactions that guide these reactions. In the Protein Interaction Networks, instead, the nodes represent proteins and the edges are undirected. They store information about the set of interactions between pairs of proteins in a proteome.

In the last few years, due to the large amount of experimentally discovered interaction data, many databases have been devised and made free accessible online. These databases allow storing and retrieving molecular interaction information (Kanehisa, 2000; Salwinski, 2004; Chatr-aryamontri, 2006). Many of them allow the user to search both online for interaction data and to download database files containing all stored interaction information.

Moreover, several automatic tools supporting knowledge discovery from available interaction data have been developed. Among them, the most related to the topic of this chapter are those tools designed to compare biological networks (see also, in this volume, the chapter Discovering Interaction Motifs from Protein Interaction Networks).

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Xiao-Li Li, See-Kiong Ng
Chapter 1
Christian Schönbach
Advances in protein-protein interaction (PPI) detection technology and computational analysis methods have produced numerous PPI networks, whose... Sample PDF
Molecular Biology of Protein-Protein Interactions for Computer Scientists
Chapter 2
Koji Tsuda
In this tutorial chapter, the author reviews basics about frequent pattern mining algorithms, including itemset mining, association rule mining, and... Sample PDF
Data Mining for Biologists
Chapter 3
Tatsuya Akutsu, Morihiro Hayashida
Many methods have been proposed for inference of protein-protein interactions from protein sequence data. This chapter focuses on methods based on... Sample PDF
Domain-Based Prediction and Analysis of Protein-Protein Interactions
Chapter 4
Martin S.R. Paradesi, Doina Caragea, William H. Hsu
This chapter presents applications of machine learning to predicting protein-protein interactions (PPI) in Saccharomyces cerevisiae. Several... Sample PDF
Incorporating Graph Features for Predicting Protein-Protein Interactions
Chapter 5
David La, Daisuke Kihara
This chapter gives a comprehensive introduction of the sequence/structural features that are characteristic of protein- protein interaction sites... Sample PDF
Discovering Protein-Protein Interaction Sites from Sequence and Structure
Chapter 6
Paolo Marcatili, Anna Tramontano
This chapter provides an overview of the current computational methods for PPI network cleansing. The authors first present the issue of identifying... Sample PDF
Network Cleansing: Reliable Interaction Networks
Chapter 7
Hugo Willy
Recent breakthroughs in high throughput experiments to determine protein-protein interaction have generated a vast amount of protein interaction... Sample PDF
Discovering Interaction Motifs from Protein Interaction Networks
Chapter 8
Raymond Wan, Hiroshi Mamitsuka
This chapter examines some of the available techniques for analyzing a protein interaction network (PIN) when depicted as an undirected graph.... Sample PDF
Discovering Network Motifs in Protein Interaction Networks
Chapter 9
Clara Pizzuti, Simona Ester Rombo
In this chapter a survey on the main graph-based clustering techniques proposed in the literature to mine proteinprotein interaction networks (PINs)... Sample PDF
Discovering Protein Complexes in Protein Interaction Networks
Chapter 10
Takashi Makino, Aoife McLysaght
This chapter introduces evolutionary analyses of protein interaction networks and of proteins as components of the networks. The authors show... Sample PDF
Evolutionary Analyses of Protein Interaction Networks
Chapter 11
Kar Leong Tew, Xiao-Li Li
This chapter introduces state-of-the-art computational methods which discover lethal proteins from Protein Interaction Networks (PINs). Lethal... Sample PDF
Discovering Lethal Proteins in Protein Interaction Networks
Chapter 12
Hon Nian Chua, Limsoon Wong
Functional characterization of genes and their protein products is essential to biological and clinical research. Yet, there is still no reliable... Sample PDF
Predicting Protein Functions from Protein Interaction Networks
Chapter 13
Pablo Minguez, Joaquin Dopazo
Here the authors review the state of the art in the use of protein-protein interactions (ppis) within the context of the interpretation of genomic... Sample PDF
Protein Interactions for Functional Genomics
Chapter 14
Xiaoyue Zhao, Lilia M. Iakoucheva, Michael Q. Zhang
Genetic factors play a major role in the etiology of many human diseases. Genome-wide experimental methods produce an increasing number of genes... Sample PDF
Prioritizing Disease Genes and Understanding Disease Pathways
Chapter 15
Smita Mohanty, Shashi Bhushan Pandit, Narayanaswamy Srinivasan
Integration of organism-wide protein interactome data with information on expression of genes, cellular localization of proteins and their functions... Sample PDF
Dynamics of Protein-Protein Interaction Network in Plasmodium Falciparum
Chapter 16
Sirisha Gollapudi, Alex Marshall, Daniel Zadik, Charlie Hodgman
Software for the visualization and analysis of protein-protein interaction (PPI) networks can enable general exploration, as well as providing... Sample PDF
Graphical Analysis and Visualization Tools for Protein Interaction Networks
Chapter 17
Valeria Fionda, Luigi Palopoli
The aim of this chapter is that of analyzing and comparing network querying techniques as applied to protein interaction networks. In the last few... Sample PDF
Network Querying Techniques for PPI Network Comparison
Chapter 18
Tero Aittokallio
This chapter provides an overview of the computational approaches developed for exploring the modular organization of protein interaction networks.... Sample PDF
Module Finding Approaches for Protein Interaction Networks
About the Contributors