DESCRIPTION: Current Protein-Protein Interaction (PPI) databases do not offer sophisticated querying interfaces and especially do not integrate existing information about proteins. Current algorithms for Protein-Interaction Networks (PIN) analysis use only topological information, while emerging approaches attempt to exploit the biological knowledge related to proteins and kinds of interaction, e.g. protein function, localization, structure, described in Gene Ontology or PDB. The book discusses technologies, standards and databases for, respectively, generating, representing and storing PPI data. It also describes main algorithms and tools for the analysis, comparison and knowledge extraction from PINs. Moreover, some case studies and applications of PINs are also discussed. TABLE OF CONTENTS List if Figures xiii List of Tables xix Foreword xxi Preface xxiii Acknowledgments xxix Introduction xxxi Acronyms xxxiii 1 Interactomics 1 1.1 Interactomics and Omics Sciences 1 1.2 Genomics and Proteomics 4 1.3 Representation and Management of Protein Interaction Data 5 1.4 Analysis of Protein Interaction Networks 5 1.5 Visualization of Protein Interaction Networks 6 1.6 Models for Biological Networks 7 1.7 Flow of Information in Interactomics 8 1.8 Applications of Interactomics in Biology and Medicine 10 1.9 Summary 11 2. Technologies for Discovering Protein Interactions 13 2.1 Introduction 13 2.2 Techniques Investigating Physical Interactions 14 2.3 Technologies Investigating Kinetic Dynamics 17 2.4 Summary 18 3. Graph Theory and Applications 21 3.1 Introduction 21 3.2 Graph Data Structures 22 3.3 Graph-Based Problems and Algorithms 28 3.4 Summary 31 4. Protein-to-Protein Interaction Data 33 4.1 Introduction 33 4.2 HUPO PSI-MI 34 4.3 Summary 41 5. Protein-to-Protein Interaction Databases 43 5.1 Introduction 43 5.2 Databases of Experimentally Determined Interactions 45 5.3 Databases of Predicted Interactions 55 5.4 Metadatabases: Integration of PPI Databases 62 5.5 Summary 70 6. Models for Protein Interaction Networks 71 6.1 Introduction 71 6.2 Random Graph Model 72 6.3 Scale-Free Model 73 6.4 Geometric Random Graph Model 73 6.5 Stickiness Index (STICKY) Model 74 6.6 Degree-Weighted Model 74 6.7 Network Scoring Models 75 6.8 Summary 76 7. Algorithms Analyzing Features of Protein Interaction Networks 79 7.1 Introduction 79 7.2 Analysis of Protein Interaction Networks through Centrality Measures 80 7.3 Extraction of Network Motifs 81 7.4 Individuation of Protein Complexes 88 7.5 Summary 99 8. Algorithms Comparing Protein Interaction Networks 101 8.1 Introduction 101 8.2 Local Alignment Algorithms 104 8.3 Global Alignment Algorithms 109 9. Ontology-Based Analysis of Protein Interaction Networks 113 9.1 Definition of Ontology 113 9.2 Languages for Modeling Ontologies 115 9.3 Biomedical Ontologies 116 9.4 Ontology-Based Analysis of Protein Interaction Data 117 9.5 Semantic Similarity Measures of Proteins 120 9.6 The Gene Ontology Annotation Database (GOA) 122 9.7 FussiMeg and ProteinOn 123 9.8 Summary 123 10. Visualization of Protein Interaction Networks 125 10.1 Introduction 125 10.2 Cytoscape 126 10.3 CytoMCL 127 10.4 NaViGaTOR 128 10.5 Biolayout Express3D 130 10.6 Medusa 130 10.7 ProViz 131 10.8 Ondex 132 10.9 PIVOT 132 10.10 Pajek 133 10.11 Graphviz 134 10.12 GraphCrunch 134 10.13 VisANT 135 10.14 PIANA 136 10.15 Osprey 136 10.16 cPATH 137 10.17 PATIKA 138 10.18 Summary 139 11. Case Studies in Biology and Bioinformatics 141 11.1 Analysis of an Interaction Network from Proteomic Data 141 11.2 Experimental Comparison of Two Interaction Networks 143 11.3 Ontology-Based Management of PIN (OntoPIN) 145 11.4 Ontology-Based Prediction of Protein Complexes 149 12. Future Trends 151 References 157 Index 177