INTRODUCTION

Computational approaches such as those described in Chapters 6 through 10 analyze protein-protein interaction (PPI) networks on the basis of network properties only, with little integration of information from outside sources. Current conventional methods can predict only whether two proteins share a specific function but not the universe of functions that they share. Their effectiveness is hampered by their inability to take into consideration the full range of available information about protein functions. The discussion in Chapter 11 has demonstrated the effectiveness of integrating Gene Ontology (GO) annotations into such analysis. It has become increasingly apparent that the fusion of multiple strands of biological data regarding each gene or protein will produce a more comprehensive picture of the relations among the components of a genome [191], including proteins, and a more specific representation of each protein. The sophisticated data set, graph, or tree generated through these means can be subjected to advanced computational analysis by methods such as machine learning algorithms. Such approaches have become increasingly widespread and are expected to improve the accuracy of protein function prediction.

In this chapter, we present some of the more recent approaches that have been developed for incorporating diverse biological information into the explorative analysis of PPI networks.

INTEGRATION OF GENE EXPRESSION WITH PPI NETWORKS

Current research efforts have resulted in the generation of large quantities of data related to the functional properties of genomes; specifically, gene expression and protein interaction data. Gene expression profiles provide a snapshot of the simultaneous activity of all the genes in a genome under a given condition, thus eliminating the need to examine each gene separately.

I am pleased to offer the research community my second book-length contribution to the field of bioinformatics. My first book, Advanced Analysis of Gene Expression Microarray Data, was published in 2006 by World Scientific as part of its Science, Engineering, and Biology Informatics (SEBI) series. I first became involved in the study of bioinformatics in 1998 and, over the ensuing decade, have been struck by the enormous quantity of data being generated and the need for effective approaches to its analysis.

The analysis of protein-protein interactions (PPIs) is fundamental to the understanding of cellular organizations, processes, and functions. It has been observed that proteins seldom act as single isolated species in the performance of their functions; rather, proteins involved in the same cellular processes often interact with each other. Therefore, the functions of uncharacterized proteins can be predicted through comparison with the interactions of similar known proteins. A detailed examination of a PPI network can thus yield significant new insights into protein functions. These interactions have traditionally been examined via intensive small-scale investigations of a small set of proteins of interest, each yielding information about a limited number of PPIs. The existing databases of PPIs have been compiled from such small-scale screens, presented in individual research papers. Because these data were subject to stringent controls and evaluation in the peer-review process, they can be considered to be fairly reliable. However, each experiment observes only a few interactions and yields a data set of very limited size. Recent large-scale investigations of PPIs using such techniques as two-hybrid systems, mass spectrometry, and protein microarrays have enriched the available protein interaction data and facilitated the construction of integrated PPI networks.

INTRODUCTION

The previous three chapters have discussed in detail the analysis of protein-proteinelusive interactions, which often compromise the effectiveness of the approaches presented so far. In this chapter, we will examine flow-based approaches, another avenue for the analysis of PPI networks. These methods permit information from other sources to be integrated with PPI data to enhance the effectiveness of algorithms for protein function prediction and functional module detection. Flow-based approaches offer a novel strategy for assessing the degree of biological and topological influence of each protein over other proteins in a PPI network. Through simulation of biological or functional flows within these complex networks, these methods seek to model and predict network behavior under the influence of various realistic external stimuli.

This chapter will discuss several flow-based methods for the prediction of protein function. The first section will address the concept of functional flow introduced by Nabieva et al. [221] and the FunctionalFlow algorithm based on this model. In this approach, each protein with a known functional annotation is treated as a source of functional flow, which is then propagated to unannotated nodes, using the edges in the interaction graph as a conduit. This process is based on simple local rules. A distance effect is formulated that considers the impact of each annotated protein on any other protein, with the effect diminishing as the distance between the proteins increases.

The generation of protein-protein interaction (PPI) data is proceeding at a rapid and accelerating pace, heightening the demand for advances in the computational methods used to analyze patterns and relationships in these complex data sets. This book has offered a systematic presentation of a variety of advanced computational approaches that are available for the analysis of PPI networks. In particular, we have focused on those approaches that address the modularity analysis and functional prediction of proteins in PPI networks. These computational techniques have been presented as belonging to seven categories:

1. Basic representation and modularity analysis. Throughout this book, PPI networks have been represented through mathematical graphs, and we have provided a detailed discussion of the basic properties of such graphs. PPI networks have been identified as modular and hierarchical in nature, and modularity analysis is therefore of particular utility in understanding their structure. A range of approaches has been proposed for the detection of modules within these networks and to guide the prediction of protein function. We have broadly classified these methods as distance-based, graph-theoretic, topology-based, flow-based, statistical, and domain knowledge-based. Clustering a PPI network permits a better understanding of its structure and the interrelationship of its constituent components. The potential functions of unannotated proteins may be predicted by comparison with other members of the same functional module.

2. Distance-based analysis. Chapter 7 surveyed five categories of approaches to distance-based clustering. All these methods use classic clustering techniques and focus on the definition of the topological or biological distance or similarity between two proteins in a network.

3. […]

INTRODUCTION

The ability of the various approaches discussed throughout this book to accurately analyze protein-protein interactions (PPIs) is often compromised by the errors and gaps that characterize the data. Their accuracy would be enhanced by the integration of data from all available sources. Modern experimental and computational techniques have resulted in the accumulation of massive amounts of information about the functional behavior of biological components and systems. These diverse data sources have provided useful insights into the functional association between components. The following types of data have frequently been drawn upon for functional analysis and could be integrated with PPI data [276, 297, 304, 305]:

• Amino acid sequences

• Protein structures

• Genomic sequences

• Phylogenetic profiles

• Microarray expressions

• Gene Ontology (GO) annotations

The development of sequence similarity search algorithms such as FASTA [244], BLAST [13], and PSI-BLAST [14] has been a major breakthrough in the field of bioinformatics. The algorithms rest on the understanding that proteins with similar sequences are functionally consistent. Searching for sequential homologies among proteins can facilitate their classification and the accurate prediction of their functions.

The availability of complete genomes for various organisms has shifted such sequence comparisons from the level of the single gene to the genome level [48, 97]. As discussed in Chapter 3, several genome-scale approaches have been introduced on the basis of the correlated evolutionary mechanisms of genes. For example, the conservation of gene neighborhoods across different, distantly-related genomes reveals potential functional linkages [80, 235, 296]. Gene fusion analysis infers pairs of interacting proteins and their functional relatedness [98, 208].

INTRODUCTION

Essential questions regarding the structure, underlying principles, and semantics of protein-protein interaction (PPI) networks can be addressed by an examination of their topological features and components. Network performance, scalability, robustness, and dynamics are often dependent on these topological properties. Much research has been devoted to the development of methods to quantitatively characterize a network or its components. Empirical and theoretical studies of networks of all types - technological, social, and biological - have been among the most popular subjects of recent research in many fields. Graph theories have been successfully applied to these real-world systems, and many graph and component measurements have been introduced.

In Chapters 4 and 5, we provided an introduction to the typical topological properties of real complex networks, including degree distribution, attachment tendency, and reachability indices. We also introduced the scale-free model, which is among the most popular network models. This model exemplifies several important topological properties, which will be briefly summarized here:

1. ■ The small-world property: Despite the large size of most real-world networks, arelatively short path can be found between any two constituent nodes. The smallworld property states that any node in a real-world network can be reached from any other node within a small number of steps. As Erdős and Rényi [100, 101] have demonstrated, the typical distance between any two nodes in a random network is the logarithm of the number of nodes, indicating that random graphs are also characterized by this property.

2. […]

INTRODUCTION

The classic approaches to clustering follow a protocol termed “pattern proximity after feature selection” [158]. Pattern proximity is usually measured by a distance function defined for pairs of patterns. A simple distance measurement can capture the dissimilarity between two patterns, while similarity measures can be used to characterize the conceptual similarity between patterns. In protein-protein interaction (PPI) networks, proteins are represented as nodes and interactions are represented as edges. The relationship between two proteins is therefore a simple binary value: 1 if they interact, 0 if they do not. This lack of nuance makes it difficult to define the distance between the two proteins. The reliable clustering of PPI networks is further complicated by a high rate of false positives and the sheer volume of data, as discussed in Chapter 2.

Distance-based clustering employs these classic techniques and focuses on the definition of the topological or biological distance between proteins. These clustering approaches begin by defining the distance or similarity between two proteins in the network. This distance/similarity matrix can then be incorporated into traditional clustering algorithms. In this chapter, we will discuss a variety of approaches to distance-based clustering, all of which are grounded upon the use of these classic techniques.

TOPOLOGICAL DISTANCE MEASUREMENT BASED ON COEFFICIENTS

The simplest of these approaches use classic distance measurement methods and their various coefficient formulas to compute the distance between proteins in PPI networks. As discussed in [123], the distance between two nodes (proteins) in a PPI network can be defined as follows.

INTRODUCTION

In recent years, the genomic sequencing of several model organisms has been completed. As of June 2006, complete genome sequences were available for 27 archaeal, 326 bacterial, and 21 eukaryotic organisms, and the sequencing of 316 bacterial, 24 archaeal, and 126 eukaryotic genomes was in progress [281]. In addition, the development of a variety of high-throughput methods, including the two-hybrid system, DNA microarrays, genomic SNP arrays, and protein chips, has generated large amounts of data suitable for the analysis of protein function. Although it is possible to determine the interactions between proteins and their functions accurately using biochemical/molecular experiments, such efforts are often very slow, costly and require extensive experimental validation. Therefore, the analysis of protein function in available databases offers an attractive prospect for less resource-intensive investigation.

Work with these sequenced genomes is hampered, however, by the fact that only 50–60% of their component genes have been annotated [281]. Several approaches have been developed to predict the functions of these unannotated proteins. The accurate prediction of protein function is of particular importance to an understanding of the critical cellular and biochemical processes in which they play a vital role. Methods that allow researchers to infer the functions of unannotated proteins using known functional annotations of proteins and the interaction patterns between them are needed.

Machine learning has been widely applied in the field of protein-protein interaction (PPI) networks and is particularly well suited to the prediction of protein functions. Methods have been developed to predict protein functions using a variety of information sources, including protein structure and sequence, protein domain, PPIs, genetic interactions, and the analysis of gene expression.

INTRODUCTION

The component proteins within protein-protein interaction (PPI) networks are associated in two types of groupings: protein complexes and functional modules. Protein complexes are assemblages of proteins that interact with each other at a given time and place, forming a single multimolecular machine. Functional modules consist of proteins that participate in a particular cellular process while binding to each other at various times and places. The detection of these groupings, known as modularity analysis, is an area of active research. In particular, the graphic representation of PPI networks has facilitated the discrimination of protein clusters through data-mining techniques.

The methods of data mining can be applied to identify various aspects of network organization. For example:

• Proteins located at neighboring positions in a graph are generally considered to share functions (“guilt by association”). On this basis, the functions of a protein may be predicted by examining the proteins with which it interacts and the protein complexes to which it belongs.

• Densely connected subgraphs in the network are likely to form protein complexes that function as single units in a particular biological process.

• Investigation of network topological features can shed light on the biological system [29]. For example, networks may be scale-free, governed by the power law, or of various sizes.

A cluster is a set of objects that share some common characteristics. Clustering is the process of grouping data objects into sets (clusters); objects within a cluster demonstrate greater similarity than do objects in different clusters. In a PPI network, these sets will be either protein complexes or functional modules.

INTRODUCTION

Modules (or clusters) in protein-protein interaction (PPI) networks can be identified by applying various clustering algorithms that use graph theory. Each of these methods converts the process of clustering a PPI dataset into a graph-theoretic analysis of the corresponding PPI network. Such clustering approaches take into consideration either the local topology or the global structure of the networks.

The graph-theoretic approaches to modularity analysis can be divided into two classes. One type of approaches [24, 238, 272, 286] seeks to identify dense subgraphs by maximizing the density of each subgraph on the basis of local network topology. The goal of the second group of methods [94,99,138,180,250] is to find the best partition in a graph. Based on the global structure of a network, the methods in this class minimize the cost of partitioning or separating the graph. The approaches in these classes will be discussed in the first two sections of this chapter.

PPI networks are typically large, often having more than 6,000 nodes. In a graph of such large size, classical graph-theoretic algorithms become inefficient. A graph reduction-based approach [65], which enhances the efficiency of module detection in such large and complex interaction networks, will be explored in the third section of this chapter.

FINDING DENSE SUBGRAPHS

In this section, we will discuss those graph-theoretic approaches that seek to identify the densest subgraphs within a graph; specific methods vary in the means used to assess the density of the subgraphs. Six variations on this theme will be discussed in the following subsections.

INTRODUCTION

Proteins and their interactions lie at the heart of most fundamental biological processes. Typically, proteins seldom act in isolation but rather execute their functions through interaction with other biomolecular units. Consequently, an examination of these protein-protein interactions (PPIs) is essential to understanding the molecular mechanisms of underlying biological processes. This chapter is intended to provide an overview of the more common experimental methods currently used to generate PPI data.

In the past, PPIs were typically examined via intensive small-scale investigations of restricted sets of proteins of interest, each yielding information regarding a limited number of PPIs. The existing databases of PPIs have been compiled from the results of such small-scale screens presented in individual research papers. Since these data are subject to stringent controls and evaluation in the peer-review process, they can be considered to be fairly reliable. However, each experiment observes only a few interactions and provides a data set of limited size.

Recent high-throughput approaches involve genome-wide detection of protein interactions. Studies using the yeast two-hybrid (Y2H) system, mass spectrometry (MS), and protein microarrays have generated large amounts of interaction data. The Y2H system takes a bottomup genomic approach to detecting possible binary interactions between any two proteins encoded in the genome of interest. In contrast, mass spectrometric analysis adopts a top-down proteomic approach by analyzing the composition of protein complexes. The protein microarray technology simultaneously captures the expression of thousands of proteins.

RAPID GROWTH OF PROTEIN-PROTEIN INTERACTION DATA

Since the sequencing of the human genome was brought to fruition, the field of genetics now stands on the threshold of significant theoretical and practical advances. Crucial to furthering these investigations is a comprehensive understanding of the expression, function, and regulation of the proteins encoded by an organism. This understanding is the subject of the discipline of proteomics. Proteomics encompasses a wide range of approaches and applications intended to explicate how complex biological processes occur at a molecular level, how they differ in various cell types, and how they are altered in disease states.

Defined succinctly, proteomics is the systematic study of the many and diverse properties of proteins with the aim of providing detailed descriptions of the structure, function, and control of biological systems in health and disease. The field has burst onto the scientific scene with stunning rapidity over the past several years. Figure 1–1 shows the trend of the number of occurrences of the term “proteome” found in PubMed bioinformatics citations over the past decade. This figure strikingly illustrates the rapidly increasing role played by proteomics in bioinformatics research in recent years.

A particular focus of the field of proteomics is the nature and role of interactions between proteins. Protein-protein interactions (PPIs) regulate a wide array of biological processes, including transcriptional activation/repression; immune, endocrine, and pharmacological signaling; cell-to-cell interactions; and metabolic and developmental control. PPIs play diverse roles in biology and differ based on the composition, affinity, and lifetime of the association.

INTRODUCTION

The yeast two-hybrid (Y2H) system and other experimental approaches described in Chapter 2 provide useful tools for the detection of protein-protein interactions (PPIs) between specified proteins that may occur in many possible combinations. The widespread application of these methods has generated a substantial bank of information about such interactions. However, as pointed out in Chapter 2, the data generated through these approaches may be unreliable and may not be completely inclusive of all possible PPIs. In order to form an understanding of the total universe of potential interactions, including those not detected by these methods, it is useful to develop approaches to predict the full range of possible interactions between proteins. The accurate prediction of PPIs is therefore an important goal in the field of molecular recognition.

A variety of computational methods have been applied to supplement the interactions that have been detected experimentally. In addition, these methods can assess the reliability of experimentally derived interaction data, which are prone to error. The computational methods for in-silico prediction include genomicscale approaches [80, 98, 208, 209, 235, 248], sequence-based approaches [212, 287, 322, 338], structure-based approaches [10, 11, 22, 95, 282], learning-based approaches [42, 43, 127, 160, 236], and network-topology-based approaches [19, 62, 125, 245, 269, 270]. The individual PPI data can be taken from publicly available databases, such as MIPS [130, 214], DIP [271, 327], MINT [59, 340], IntAct [141, 178], BioGRID [289], and HPRD [219, 251, 252], as described in Chapter 2.

GENOME-SCALE APPROACHES

The availability of complete genomes for various organisms has enabled the prediction of PPIs at a genomic scale. Genomic-scale approaches typically perform a comparison of gene sequences across genomes and are often justified on the basis of the correlated evolutionary mechanisms of genes.