Analysis of Biological Networks

Foreword xiii Preface xv Contributors xix PART I INTRODUCTION 1 1 Networks in Biology 3 Bjorn H. Junker 1.1 Introduction 3 1.2 Biology 101 4 1.3 Systems Biology 8 1.4 Properties of Biological Networks 8 1.5 Summary 12 1.6 Exercises 12 2 Graph Theory 15 Falk Schreiber 2.1 Introduction 15 2.2 Basic Notation 16 2.3 Special Graphs 19 2.4 Graph Representation 23 2.5 Graph Algorithms 24 2.6 Summary 27 2.7 Exercises 27 PART II NETWORK ANALYSIS 29 3 Global Network Properties 31 Ralf Steuer and Gorka Zamora Lopez 3.1 Introduction 31 3.2 Global Properties of Complex Networks 33 3.3 Models of Complex Networks 43 3.4 Additional Properties of Complex Networks 48 3.5 Statistical Testing of Network Properties 52 3.6 Summary 57 3.7 Exercises 58 4 Network Centralities 65 Dirk Koschutzki 4.1 Introduction 65 4.2 Centrality Definition and Fundamental Properties 67 4.3 Degree and Shortest Path-Based Centralities 69 4.4 Feedback-Based Centralities 77 4.5 Tools 80 4.6 Summary 80 4.7 Exercises 81 5 Network Motifs 85 Henning Schwobbermeyer 5.1 Introduction 85 5.2 Definitions and Basic Concepts 86 5.3 Motif Statistics and Motif-Based Network Distance 89 5.4 Complexity of Network Motif Detection 94 5.5 Methods and Tools for Network Motif Analysis 96 5.6 Analyses and Applications of Network Motifs 97 5.7 Summary 106 5.8 Exercises 108 6 Network Clustering 113 Balabhaskar Balasundaram and Sergiy Butenko 6.1 Introduction 113 6.2 Notations and Definitions 115 6.3 Network Clustering Problem 118 6.4 Clique-Based Clustering 119 6.5 Center-Based Clustering 125 6.6 Conclusion 131 6.7 Summary 133 6.8 Exercises 133 7 Petri Nets 139 Ina Koch and Monika Heiner 7.1 Introduction 139 7.2 Qualitative Modeling 141 7.3 Qualitative Analysis 152 7.4 Quantitative Modeling and Analysis 169 7.5 Tool Support 171 7.6 Case Studies 172 7.7 Summary 174 7.8 Exercises 175 PART III BIOLOGICAL NETWORKS 181 8 Signal Transduction and Gene Regulation Networks 183 Anatolij P. Potapov 8.1 Introduction 183 8.2 Decisive Role of Regulatory Networks in the Evolution and Existence of Organisms 184 8.3 Gene Regulatory Network as a System of Many Subnetworks 186 8.4 Databases on Gene Regulation and Software Tools for Network Analysis 187 8.5 Peculiarities of Signal Transduction Networks 188 8.6 Topology of Signal Transduction Networks 190 8.7 Topology of Transcription Networks 191 8.8 Intercellular Molecular Regulatory Networks 198 8.9 Summary 200 8.10 Exercises 201 9 Protein Interaction Networks 207 Frederik Bornke 9.1 Introduction 207 9.2 Detecting Protein Interactions 209 9.3 Establishing Protein Interaction Networks 220 9.4 Analyzing Protein Interaction Networks 223 9.5 Summary 225 9.6 Exercises 226 10 Metabolic Networks 233 Marcio Rosa da Silva, Jibin Sun, Hongwu Ma, Feng He, and An-Ping Zeng 10.1 Introduction 233 10.2 Visualization and Graph Representation 234 10.3 Reconstruction of Genome-Scale Metabolic Networks 234 10.4 Connectivity and Centrality in Metabolic Networks 239 10.5 Modularity and Decomposition of Metabolic Networks 242 10.6 Elementary Flux Modes and Extreme Pathways 246 10.7 Summary 249 10.8 Exercises 249 11 Phylogenetic Networks 255 Birgit Gemeinholzer 11.1 Introduction 255 11.2 Character Selection, Character Coding, and Matrices for Phylogenetic Reconstruction 257 11.3 Tree Reconstruction Methodologies 260 11.4 Phylogenetic Networks 264 11.5 Summary 276 11.6 Exercises 276 12 Ecological Networks 283 Ursula Gaedke 12.1 Introduction 283 12.2 Binary Food Webs 289 12.3 Quantitative Trophic Food Webs 293 12.4 Ecological Information Networks 298 12.5 Summary 300 12.6 Exercises 301 13 Correlation Networks 305 Dirk Steinhauser, Leonard Krall, Carsten Mussig, Dirk Bussis, and Bjorn Usadel 13.1 Introduction 305 13.2 General Remarks 306 13.3 Basic Notation 307 13.4 Construction and Analyses of Correlation Networks 314 13.5 Biological Use of Correlation Networks 321 13.6 Summary 328 13.7 Exercises 329 References 330 Index 335