Analysis of Biological Networks

Björn H. Junker is a biologist with a strong background in bioinformatics. His current research activities include the quantitative analysis and modeling of metabolic networks, as well as pathway databases and visual data mining. Mr. Junker has been at the Leibniz Institute of Plant Genetics and Crop Plant Research in Germany since 2003. He worked at Brookhaven National Laboratory in New York during 2006 and was appointed as project leader at the Leibniz Institute in 2007. Falk Schreiber is a computer scientist who has worked in bioinformatics for more than ten years. His current research areas include modeling, analysis, and visualization of biological networks; graph algorithms; and data exploration and information visualization in the life sciences. Since 2003, he has been head of the Network Analysis Research Group at the Leibniz Institute of Plant Genetics and Crop Plant Research. He was appointed professor of bioinformatics at the Martin Luther University Halle-Wittenberg, Germany, in 2007.

• Foreword xiii Preface xvContributors xixPART I INTRODUCTION 11 Networks in Biology 3Bjorn H. Junker1.1 Introduction 31.2 Biology 101 41.3 Systems Biology 81.4 Properties of Biological Networks 81.5 Summary 121.6 Exercises 122 Graph Theory 15Falk Schreiber2.1 Introduction 152.2 Basic Notation 162.3 Special Graphs 192.4 Graph Representation 232.5 Graph Algorithms 242.6 Summary 272.7 Exercises 27PART II NETWORK ANALYSIS 293 Global Network Properties 31Ralf Steuer and Gorka Zamora Lopez3.1 Introduction 313.2 Global Properties of Complex Networks 333.3 Models of Complex Networks 433.4 Additional Properties of Complex Networks 483.5 Statistical Testing of Network Properties 523.6 Summary 573.7 Exercises 584 Network Centralities 65Dirk Koschutzki4.1 Introduction 654.2 Centrality Definition and Fundamental Properties 674.3 Degree and Shortest Path-Based Centralities 694.4 Feedback-Based Centralities 774.5 Tools 804.6 Summary 804.7 Exercises 815 Network Motifs 85Henning Schwobbermeyer5.1 Introduction 855.2 Definitions and Basic Concepts 865.3 Motif Statistics and Motif-Based Network Distance 895.4 Complexity of Network Motif Detection 945.5 Methods and Tools for Network Motif Analysis 965.6 Analyses and Applications of Network Motifs 975.7 Summary 1065.8 Exercises 1086 Network Clustering 113Balabhaskar Balasundaram and Sergiy Butenko6.1 Introduction 1136.2 Notations and Definitions 1156.3 Network Clustering Problem 1186.4 Clique-Based Clustering 1196.5 Center-Based Clustering 1256.6 Conclusion 1316.7 Summary 1336.8 Exercises 1337 Petri Nets 139Ina Koch and Monika Heiner7.1 Introduction 1397.2 Qualitative Modeling 1417.3 Qualitative Analysis 1527.4 Quantitative Modeling and Analysis 1697.5 Tool Support 1717.6 Case Studies 1727.7 Summary 1747.8 Exercises 175PART III BIOLOGICAL NETWORKS 1818 Signal Transduction and Gene Regulation Networks 183Anatolij P. Potapov8.1 Introduction 1838.2 Decisive Role of Regulatory Networks in the Evolution and Existence of Organisms 1848.3 Gene Regulatory Network as a System of Many Subnetworks 1868.4 Databases on Gene Regulation and Software Tools for Network Analysis 1878.5 Peculiarities of Signal Transduction Networks 1888.6 Topology of Signal Transduction Networks 1908.7 Topology of Transcription Networks 1918.8 Intercellular Molecular Regulatory Networks 1988.9 Summary 2008.10 Exercises 2019 Protein Interaction Networks 207Frederik Bornke9.1 Introduction 2079.2 Detecting Protein Interactions 2099.3 Establishing Protein Interaction Networks 2209.4 Analyzing Protein Interaction Networks 2239.5 Summary 2259.6 Exercises 22610 Metabolic Networks 233Marcio Rosa da Silva, Jibin Sun, Hongwu Ma, Feng He, and An-Ping Zeng10.1 Introduction 23310.2 Visualization and Graph Representation 23410.3 Reconstruction of Genome-Scale Metabolic Networks 23410.4 Connectivity and Centrality in Metabolic Networks 23910.5 Modularity and Decomposition of Metabolic Networks 24210.6 Elementary Flux Modes and Extreme Pathways 24610.7 Summary 24910.8 Exercises 24911 Phylogenetic Networks 255Birgit Gemeinholzer11.1 Introduction 25511.2 Character Selection, Character Coding, and Matrices for Phylogenetic Reconstruction 25711.3 Tree Reconstruction Methodologies 26011.4 Phylogenetic Networks 26411.5 Summary 27611.6 Exercises 27612 Ecological Networks 283Ursula Gaedke12.1 Introduction 28312.2 Binary Food Webs 28912.3 Quantitative Trophic Food Webs 29312.4 Ecological Information Networks 29812.5 Summary 30012.6 Exercises 30113 Correlation Networks 305Dirk Steinhauser, Leonard Krall, Carsten Mussig, Dirk Bussis, and Bjorn Usadel13.1 Introduction 30513.2 General Remarks 30613.3 Basic Notation 30713.4 Construction and Analyses of Correlation Networks 31413.5 Biological Use of Correlation Networks 32113.6 Summary 32813.7 Exercises 329References 330Index 335

"This book is a wonderful text for biological network analysis. It comprehensively presents a numbers of analysis tools and their applications for understanding real biological problems. This book is a must-read for entry-level students and researchers, and a complete reference source for experts." (Computing Reviews, March 6, 2009) "This book is an excellent introduction to the analysis of biological networks.  The exercise provided after each chapter make the book suitable for self-study, and the extensive references provide the interested reader with good sources for further reading." (Computing Reviews, August 21, 2008)