Analysis of Biological Networks

An introduction to biological networks and methods for their
analysis

Analysis of Biological Networks is the first book of its
kind to provide readers with a comprehensive introduction to the
structural analysis of biological networks at the interface of
biology and computer science. The book begins with a brief overview
of biological networks and graph theory/graph algorithms and goes
on to explore: global network properties, network centralities,
network motifs, network clustering, Petri nets, signal transduction
and gene regulation networks, protein interaction networks,
metabolic networks, phylogenetic networks, ecological networks, and
correlation networks.

Analysis of Biological Networks is a self-contained
introduction to this important research topic, assumes no expert
knowledge in computer science or biology, and is accessible to
professionals and students alike. Each chapter concludes with a
summary of main points and with exercises for readers to test their
understanding of the material presented. Additionally, an FTP site
with links to author-provided data for the book is available for
deeper study.

This book is suitable as a resource for researchers in computer
science, biology, bioinformatics, advanced biochemistry, and the
life sciences, and also serves as an ideal reference text for
graduate-level courses in bioinformatics and biological
research.

Autorentext

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.

Zusammenfassung
An introduction to biological networks and methods for their analysis Analysis of Biological Networks is the first book of its kind to provide readers with a comprehensive introduction to the structural analysis of biological networks at the interface of biology and computer science. The book begins with a brief overview of biological networks and graph theory/graph algorithms and goes on to explore: global network properties, network centralities, network motifs, network clustering, Petri nets, signal transduction and gene regulation networks, protein interaction networks, metabolic networks, phylogenetic networks, ecological networks, and correlation networks.

Analysis of Biological Networks is a self-contained introduction to this important research topic, assumes no expert knowledge in computer science or biology, and is accessible to professionals and students alike. Each chapter concludes with a summary of main points and with exercises for readers to test their understanding of the material presented. Additionally, an FTP site with links to author-provided data for the book is available for deeper study.

This book is suitable as a resource for researchers in computer science, biology, bioinformatics, advanced biochemistry, and the life sciences, and also serves as an ideal reference text for graduate-level courses in bioinformatics and biological research.

Inhalt
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</p&g...