Analysis of Biological Networks

Foreword     xiiiPreface     xvContributors     xixIntroduction     1Networks in Biology   Bjorn H. Junker     3Introduction     3Biology 101     4Biochemistry and Molecular Biology     4Cell Biology     6Ecology and Evolution     7Systems Biology     8Properties of Biological Networks     8Networks on a Microscopic Scale     9Networks on a Macroscopic Scale     11Other Biological Networks     11Summary     12Exercises     12References     12Graph Theory   Falk Schreiber     15Introduction     15Basic Notation     16Sets     16Graphs     16Graph Attributes     19Special Graphs     19Undirected, Directed, Mixed, and Multigraphs     19Hypergraphs and Bipartite Graphs     20Trees     21Graph Representation     23Adjacency Matrix     23Adjacency List     23Graph Algorithms     24Running Times of Algorithms     24Traversal     25Summary     27Exercises     27References     28Network Analysis     29Global Network Properties   Ralf Steuer   Gorka Zamora Lopez     31Introduction     31Global Properties of Complex Networks     33Distance, Average Path Length, and Diameter     33Six Degrees of Separation: Concepts of a Small World     35The Degree Distribution     35Assortative Mixing and Degree Correlations     38The Clustering Coefficient     39The Matching Index     41Network Centralities     42Eigenvalues and Spectral Properties of Networks     43Models of Complex Networks     43The Erdos-Renyi Model     44The Watts-Strogatz Model     45The Barabasi-Albert Model     46Extensions of the BA Model     48Additional Properties of Complex Networks     48Structural Robustness and Attack Tolerance     49Modularity, Community Structures and Hierarchies     50Subgraphs and Motifs in Networks      51Statistical Testing of Network Properties     52Generating Networks and Null Models     53The Conceptualization of Cellular Networks     54Bipartite Graphs     55Correlation Networks     57Summary     57Exercises     58References     59Network Centralities   Dirk Koschutzki     65Introduction     65Centrality Definition and Fundamental Properties     67Comparison of Centrality Values     68Disconnected Networks     68Degree and Shortest Path-Based Centralities     69Degree Centrality     69Eccentricity Centrality     71Closeness Centrality     72Shortest Path Betweenness Centrality     73Algorithms     74Example     76Feedback-Based Centralities     77Katz's Status Index     77Bonacich's Eigenvector Centrality     78PageRank     79Tools     80Summary     80Exercises     81References     81Network Motifs   Henning Schwobbermeyer      85Introduction     85Definitions and Basic Concepts     86Definitions     86Modeling of Biological Networks     88Concepts of Motif Frequency     88Motif Statistics and Motif-Based Network Distance     89Determination of Statistical Significance of Network Motifs     89Randomization Algorithm for Generation of Null Model Networks     90Influence of the Null Model on Motif Significance     91Limitations of the Null Model on Motif Detection     91Measures of Motif Significance and for Network Comparison     91Complexity of Network Motif Detection     94Aspects Affecting the Complexity of Network Motif Detection     94Frequency Estimation by Motif Sampling     96Methods and Tools for Network Motif Analysis     96Pajek     96Mfinder     96MAVisto     97FANMOD     97Analyses and Applications of Network Motifs     97Network Motifs in Complex Networks     97Dynamic Properties of Network Motifs     98Higher Order Structures Formed by Network Motifs     102Network Comparison Based on Network Motifs     104Evolutionary Origin of Network Motifs     106Summary     106Exercises     108References     108Network Clustering   Balabhaskar Balasundaram   Sergiy Butenko     113Introduction     113Notations and Definitions     115Network Clustering Problem     118Clique-Based Clustering     119Minimum Clique Partitioning     120Min-Max k-Clustering     122Center-Based Clustering     125Clustering with Dominating Sets     126k-Center Clustering     129Conclusion     131Summary     133Exercises     133References     134Petri Nets   Ina Koch   Monika Heiner     139Introduction     139Qualitative Modeling     141The Model     141The Behavioral Properties     148Qualitative Analysis     152Structural Analysis     152Invariant Analysis     155MCT-Sets     162Dynamic Analysis of General Properties     164Dynamic Analysis of Special Properties      166Model Validation Criteria     168Quantitative Modeling and Analysis     169Tool Support     171Case Studies     172Summary     174Exercises     175References     177Biological Networks     181Signal Transduction and Gene Regulation Networks   Anatolij P. Potapov     183Introduction     183Decisive Role of Regulatory Networks in the Evolution and Existence of Organisms     184Gene Regulatory Network as a System of Many Subnetworks     186Databases on Gene Regulation and Software Tools for Network Analysis     187Peculiarities of Signal Transduction Networks     188Topology of Signal Transduction Networks     190Topology of Transcription Networks     191Intercellular Molecular Regulatory Networks     198Summary     200Exercises     201References     202Protein Interaction Networks   Frederik Bornke     207Introduction     207Detecting Protein Interactions     209The Yeast Two-Hybrid System     211Affinity Capture of Protein Complexes      216Computational Methods to Predict Protein Interactions     218Other Ways to Identify Protein Interactions     219Establishing Protein Interaction Networks     220Data Storage and Network Generation     220Benchmarking High-Throughput Interaction Data     222Analyzing Protein Interaction Networks     223Network Topology and Functional Implications     223Functional Modules in Protein Interaction Networks     223Evolution of Protein Interaction Networks     224Comparative Interactomics     225Summary     225Exercises     226References     227Metabolic Networks   Marcio Rosa da Silva   Jibin Sun   Hongwu Ma   Feng He   An-Ping Zeng     233Introduction     233Visualization and Graph Representation     234Reconstruction of Genome-Scale Metabolic Networks     234Connectivity and Centrality in Metabolic Networks     239Modularity and Decomposition of Metabolic Networks     242Modularity Coefficient     244Modularity-Based Decomposition     245Elementary Flux Modes and Extreme Pathways      246Summary     249Exercises     249References     251Phylogenetic Networks   Birgit Gemeinholzer     255Introduction     255Character Selection, Character Coding, and Matrices for Phylogenetic Reconstruction     257Tree Reconstruction Methodologies     260Phylogenetic Networks     264Galled Trees     266Statistical Parsimony     267Median Network     269Median-Joining Networks     270Pyramids     271Example of a Pyramidal Clustering Model     271Split Decomposition     274Summary     276Exercises     276References     277Ecological Networks   Ursula Gaedke     283Introduction     283Binary Food Webs     289Introduction and Definitions     289Descriptors of the Network     289Operational Problems     291Aims and Results     291Conclusion     293Quantitative Trophic Food Webs     293Introduction, Definitions, and Database     293Multiple Commodities      295Descriptors of the Network and Information to be Gained     295Conclusion     298Ecological Information Networks     298Summary     300Exercises     301References     301Correlation Networks   Dirk Steinhauser   Leonard Krall   Carsten Mussig   Dirk Bussis   Bjorn Usadel     305Introduction     305General Remarks     306Basic Notation     307Data, Unit, Variable, and Observation     307Sample, Profiles, and Replica Set     308Measures of Association     309Simple Correlation Measures     310Complex Correlation and Association Measures     311Probability, Confidence, and Power     313Matrices     314Construction and Analyses of Correlation Networks     314Data and Profiles     315Data Set and Matrix     316Correlation Matrix     318Network Matrix     318Correlation Network Analysis     319Interpretation and Validation     321Biological Use of Correlation Networks     321The Global Analysis Approach     321The Guide Gene Approach     322A Simple Coregulation Test: Photosynthesis     324A Complex Coregulation Test: Brassinosteroids     327Summary     328Exercises     329References     330Index     335