Protein-protein Interactions and Networks (eBook)

Preface 6
Contents 8
Contributors 10
1 Experimental Methods for Protein Interaction Identification and Characterization 13
1.1 Introduction 13
1.1.1 Complex Versus Binary Interactions 15
1.1.2 The Biological Relevance of Detected Protein-protein Interactions 16
1.1.3 Protein-protein Interactions are Incompletely Studied 16
1.2 Protein Complementation Techniques 16
1.2.1 The Yeast-Two-Hybrid System 17
1.2.2 Other Fragment Complementation Techniques 19
1.3 Affinity Purification Methods 21
1.3.1 GST-Pulldown 22
1.3.2 Co-Immunoprecipitation 22
1.4 Protein Complex Purification and Mass Spectrometry 25
1.4.1 Purification of Proteins Using Affinity Tags 25
1.4.2 Tandem Affinity Tagging 27
1.4.3 Genetics and Cloning of Affinity Tagged Proteins 28
1.4.4 Isolation of Protein Complexes 29
1.4.5 Proteomics by Mass Spectrometry 29
1.4.6 Identifying Interacting Proteins Using Mass Spectrometry 30
1.4.7 Quantitative Proteomics 31
1.5 Far-Western Blotting 33
1.6 Protein and Peptide Chips 34
1.7 Quality of Large-Scale Interaction Data 34
1.8 Comparison of Methods 36
1.8.1 Y2H vs. co-AP/MS 36
1.8.2 coAP/MS vs Protein Chips 38
1.9 Conclusions 39
2 Handling Diverse Protein Interaction Data: Integration, Storage and Retrieval 45
2.1 Introduction 45
2.2 Data Integration Methods 46
2.2.1 Statistical Meta-Analysis 46
2.2.2 Supervised Learning Methods 48
2.3 Protein and Domain Interaction Databases 50
2.3.1 Comprehensive Protein Interaction Databases 53
2.3.1.1 Database of Interacting Proteins (DIP) 53
2.3.1.2 Biomolecular Object Network Databank (BOND) 53
2.3.1.3 Search Tool for the Retrieval of Interacting Proteins (STRING) 53
2.3.2 Specialized Interaction Databases 54
2.3.2.1 Human Protein Reference Database (HPRD) 54
2.3.2.2 Munich MPact/MIPS Database 54
2.3.2.3 Binding Interface Databases (WikiBID and HotSprint) 54
2.3.2.4 Molecule Pages Database/UCSD-Nature Signaling Gateway 54
2.3.2.5 InterDom Database 56
2.3.2.6 Domain Interaction Map (DIMA) Database 56
2.3.3 Interaction Databases Using Protein Structures 56
2.3.3.1 PIBASE Database 56
2.3.3.2 3did Database 57
2.3.3.3 Conserved Binding Mode (CBM) Database 57
2.3.3.4 iPfam Database 58
2.3.4 Interaction Network Analysis and Visualization 58
2.3.4.1 PathBLAST 58
2.3.5 Conclusion: A Case Study 59
3 Principles of Protein Recognition and Properties of Protein-protein Interfaces 64
3.1 Introduction 64
3.2 Protein Folding and Protein Binding are Similar Events 65
3.3 Types of Protein Interactions and Complexes in the Interactome 66
3.4 Classification into Three Types of Interfaces in the Interactome 68
3.5 Protein-protein Interfaces and Protein Cores are Similar 71
3.6 How are Signals Transmitted Through the Network? 72
3.7 Conclusions 74
4 Computational Methods to Predict Protein Interaction Partners 77
4.1 Introduction 77
4.2 Computational Methods vs. Experimental Techniques 78
4.2.1 Interplay Between Experimental and Computational Methods 78
4.2.2 Performance Comparison 79
4.3 Computational Methods Based on Sequence and Genomic Information 79
4.3.1 Phylogenetic Profiling 80
4.3.2 Similarity of Phylogenetic Trees 82
4.3.3 Conservation of Gene Neighboring 84
4.3.4 Gene Fusion 84
4.3.5 Other Methods 85
4.3.5.1 Co-evolving Positions 85
4.3.5.2 Training-Based Methods 85
4.3.5.3 Structure-Based Methods 86
4.4 Other Computational Methods Not Based on Sequence or Structural Information 86
4.5 Discussion and Future Trends 87
5 Protein Interaction Network Based Prediction of Domain-Domain and Domain-Peptide Interactions 92
5.1 Introduction 92
5.2 Predicting Domain Interactions from Protein Interaction Networks 93
5.2.1 Association Method 94
5.2.2 Maximum Likelihood Estimation (MLE) 95
5.2.3 Domain Pair Exclusion Analysis (DPEA) 96
5.2.4 Parsimonious Explanation (PE) 97
5.2.5 Integrative Approaches 99
5.2.6 Evaluation of Domain-Domain Interaction Prediction Methods 100
5.3 Predicting Domain-Peptide Interactions from Protein Interaction Networks 101
5.3.1 Discovering Domain-Peptide Interactions from Protein Interaction Networks 102
5.3.2 Utilizing Protein Interaction Network in Discovering Phosphorylation Networks 103
5.4 Conclusions and Future Directions 104
6 Integrative Structure Determination of Protein Assemblies by Satisfaction of Spatial Restraints 108
6.1 Introduction 108
6.2 Sources of Spatial Information 111
6.3 Comprehensive Data Integration by Satisfaction of Spatial Restraints 111
6.4 Structural Characterization of the Nuclear Pore Complex 117
6.5 Conclusions 121
7 Topological and Dynamical Properties of Protein Interaction Networks 124
7.1 Introduction 124
7.2 Detecting Non-Random Topological Patterns in PPI Networks 126
7.2.1 Single-Node Topological Properties: Degree Distribution 126
7.2.2 Edge Swapping Algorithm: Constructing a Randomized Network 128
7.2.3 Detecting Non-Random Topological Patterns in a Network 129
7.2.4 An Example: Correlations Between Degrees of Neighboring Nodes 131
7.3 Equilibrium and Dynamical Properties of PPI Networks 134
7.3.1 The Assignment of Dissociation Constants Kij 135
7.3.2 Concentration-Coupled Proteins 136
7.3.3 Cascading Concentration Changes in PPI Networks 137
7.3.4 Conditions Favoring the Multi-Step Propagation of Perturbations 139
7.3.5 Robustness with Respect to Assignment of Dissociation Constants 142
7.3.6 Effects of Intracellular Noise 143
8 From Protein Interaction Networks to Protein Function 147
8.1 Introduction 147
8.2 Preliminaries 148
8.2.1 Protein Function 148
8.2.2 Notation 149
8.3 Assessing Interaction Reliability 149
8.4 Algorithms 150
8.4.1 Local Approaches 150
8.4.2 Graph Cuts 152
8.4.3 Markov Random Field 154
8.4.4 Network Flow-Based Methods 155
8.4.5 Discriminative Learning Methods 157
8.4.6 Clustering 158
8.4.6.1 Distance-Based Clustering 159
8.4.6.2 Network-Based Hierarchical Clustering 160
8.4.6.3 Local Clustering 161
8.4.6.4 Other Clustering Approaches 162
8.5 Evaluation of Methods 163
8.5.1 Testing Frameworks 163
8.5.2 Performance of Methods 165
8.6 Conclusions 166
9 Cross-Species Analysis of Protein-protein Interaction Networks 171
9.1 Introduction 171
9.2 Preliminaries 172
9.3 Methods for Pairwise Network Alignment 172
9.3.1 Alignment-Graph Based Methods 172
9.3.1.1 The Network Alignment Graph 173
9.3.1.2 Search Heuristic 174
9.3.1.3 NetworkBLAST 174
9.3.1.4 NetworkBLAST-E 176
9.3.1.5 MaWish 178
9.3.2 Match-and-Split 179
9.3.3 Global Network Alignment 180
9.3.3.1 Orthology Detection Using Markov Random Fields 180
9.3.3.2 ISORank 181
9.4 Multiple Network Alignment 181
9.4.1 Græmlin 182
9.5 Network Querying 183
9.5.1 MetaPathwayHunter 184
9.5.2 QPath and QNet 185
9.5.3 PathMatch 186
9.6 Evaluation Measures 187
9.6.1 Significance Evaluation 187
9.6.2 Quality Assessment 188
9.7 A Case Study 189
9.8 Discussion 190
Index 194

"Chapter 8 From Protein Interaction Networks to Protein Function (p. 139-140)

Mona Singh

Abstract The recent availability of large-scale protein-protein interaction data provides new opportunities for characterizing a protein’s function within the context of its cellular interactions, pathways and networks. In this paper, we review computational approaches that have been developed for analyzing protein interaction networks in order to predict protein function.

8.1 Introduction

A major challenge in the post-genomic era is to determine protein function at the proteomic scale. Most organisms contain a large number of proteins whose functions are currently unknown. For example, about one-third of the proteins in the baker’s yeast Saccharomyces cerevisiae—arguably one of the most wellcharacterized model organisms—remain uncharacterized. Traditionally, computational methods to assign protein function have relied largely on sequence homology. However, the recent emergence of high-throughput techniques for determining protein interactions has enabled a new line of research where protein function is predicted by utilizing interaction data.

Proteome-scale physical interaction networks, or interactomes, have been determined for several organisms, including yeast and human. These networks are comprised of direct physical interactions between proteins (typically obtained via two hybrid analysis [FS89]) as well as of interactions indicating that two proteins are part of the same multi-protein complex (review, [BK03]).

High-throughput experiments have also linked together proteins in several other ways, and it is possible to build large-scale networks consisting of links between proteins that are synthetic lethals or are coexpressed, or between proteins where one regulates or phosphorylates the other (review, [ZGS07]). In addition to interaction networks that have been determined experimentally, there are a number of computational methods for building functional interaction networks, where two proteins are linked if they are predicted to perform a shared biological task (review, [GK00])).

In this chapter, we review some of the basic computational methods developed for analyzing protein interaction networks in order to predict protein function. The majority of these methods use some version of guilt-by-association, where proteins are annotated by transferring the functions of the proteins with which they interact.

The methods differ in the extent to which they use global properties of the interactome in annotating proteins, what topological features of the interactome they exploit, and whether they rely on first identifying tight clusters of proteins within the interactome before transferring annotations. Additionally, the underlying formulations are quite diverse, typically exploiting and further developing well understood concepts from graph theory, graphical models, discriminative learning and/or clustering."