Statistical and Evolutionary Analysis of Biological Networks

Contents......Page 8
Preface......Page 6
1.1. Introduction......Page 10
1.2. Types of Biological Networks......Page 11
1.3.1. Mathematical descriptions of networks......Page 12
1.3.1.2. Paths, components and trees......Page 13
1.3.1.3. Distance and diameter......Page 14
1.3.2.1. The degree distribution......Page 15
1.3.2.2. Clustering......Page 16
1.3.2.3. Average path length......Page 17
1.3.3.1. The adjacency matrix......Page 18
1.3.3.3. The edge list......Page 19
1.3.3.4. Some remarks on complexity......Page 20
1.4.1. Identity of networks......Page 21
1.4.2. Subnets and patterns......Page 22
1.4.3. The challenges of the data......Page 23
References......Page 24
2.1. Introduction......Page 26
2.1.2. Expansion by gene duplication......Page 27
2.1.3. Redeployment of existing genetic systems......Page 28
2.3. Mathematical Models of Networks and Network Growth......Page 29
2.3.1. Simplistic models of network growth......Page 30
2.3.2. Complex models of network growth by repeated node addition......Page 31
2.3.3. Asymptotics of the node degree DD+RA and DD+PA......Page 33
2.4. Inferring Evolutionary Dynamics in Terms of Mixture Models of Network Growth......Page 36
2.4.1. The likelihood of PIN data under DD+RA or DD+PA......Page 37
2.4.2. Simple methods to account for incomplete datasets......Page 38
2.4.3. Approximating the likelihood with many summaries......Page 39
2.4.4. Approximate Bayesian computation......Page 40
2.4.5. Evolutionary analysis of the PIN topologies of T. pallidum, H. pylori and P. falciparum......Page 41
2.4.6. The size of the interactome......Page 43
Appendix A. Proofs of Theorems.......Page 44
References......Page 49
3.1. Introduction......Page 54
3.2.1. Definitions......Page 55
3.2.2. Modelling of biological data as graphs......Page 56
3.2.3. Complexity of motif search......Page 57
3.2.4. Frequency concepts......Page 58
3.2.6. Randomisation algorithm for generation of null model networks......Page 59
3.3. Methods and Tools for the Analysis of Network Motifs......Page 60
3.3.3. MAVisto......Page 61
3.4.1. Analysis of gene regulatory networks......Page 62
3.4.3. Analysis of other networks......Page 64
3.4.4. Superstructures formed by overlapping motif matches......Page 65
3.4.5. Dynamic properties of network motifs......Page 66
3.4.6. Comparison of networks using motif distributions......Page 68
3.4.7. On the function of network motifs in biological networks......Page 70
References......Page 71
4.1. Introduction......Page 74
4.2. Measuring Biological Networks......Page 75
4.3. Random Networks in Biology......Page 78
4.4. Network Clusters......Page 79
4.5. Network Motifs......Page 82
4.5.1. Network motifs in regulatory networks......Page 83
4.6. Cross-Species Analysis of Networks......Page 85
4.6.1. Alignment of co-expression networks......Page 87
4.7.2. Gene duplications......Page 88
Appendix: Bayesian Analysis of Network Data......Page 89
References......Page 90
5.1. Introduction......Page 94
5.2.1. Introducing R0......Page 97
5.2.2. Density vs. frequency dependent contact......Page 98
5.3. Some De nitions and Their Application to Poisson Random Networks......Page 99
5.4.1. Small worlds......Page 100
5.4.2. Moment closure......Page 101
5.5.1. Models for sexually transmitted diseases......Page 105
5.5.2. Disease transmission on scale-free networks......Page 108
5.5.3. Preferential attachment or the `Matthew e ect\'......Page 110
5.5.4. STI partnership models......Page 111
5.6. Integrating Networks and Epidemiology......Page 112
5.6.1. Component sizes and the  nal epidemic size......Page 113
5.6.2. R0 on epidemiological networks and network percolation thresholds......Page 114
5.6.3. Contact frequency distributions on social and epidemiological networks......Page 115
5.7. Conclusion......Page 118
References......Page 119
6.1. Introduction......Page 122
6.2. Optimal Design of Metabolic Pathways......Page 124
6.3. Game-Theoretical Approaches to Studying Optimal Pathway Design......Page 125
6.4. Genetic Robustness and Epistasis in Metabolic Pathways......Page 126
6.5.1. Hubs and robustness in metabolic networks......Page 129
6.5.3. Robustness and epistasis in the emerging networks......Page 130
6.6. Conclusion......Page 131
References......Page 133
7.1. Introduction......Page 136
7.2.1. Experimental vs. computational methods......Page 138
7.2.3. Gene fusion......Page 139
7.2.4. Similarity of phylogenetic pro les......Page 140
7.2.5. Similarity of phylogenetic trees......Page 143
7.2.6. Correlated mutations......Page 144
7.3. Conclusion......Page 146
Acknowledgements......Page 147
References......Page 148
8.1. Introduction......Page 154
8.1.1. Protein interaction networks......Page 155
8.2. Network Ensembles......Page 156
8.2.1. Ensembles in statistical physics......Page 157
8.2.2. Bender-Can eld (BC) networks......Page 158
8.2.3. Beyond BC networks......Page 159
8.3. Generating Con dence Intervals on Networks......Page 160
8.3.2. Random rewiring of networks......Page 161
8.3.2.2. Conditional rewiring of networks — GOcardShuffle......Page 162
8.4. Analysis of Coevolution of Yeast Proteins......Page 164
8.4.1. Phylogenetic analysis......Page 166
8.4.2. Coevolution in phylogenies: BC con dence intervals......Page 168
8.5. Network Analysis and Confounding Factors......Page 170
References......Page 172
Index......Page 176