Biological Network Distances

Networks of interactions are increasingly used to model biological systems. The patterns of these networks capture a larger, more complex, representation of the whole than any single attribute can. Networks allow the modelling of far more complicated systems, at the expense of more computationally complex analysis. The networks of biological entities share common aspects. They mutate, and they mutate in a similar fashion. These mutations can be accurately measured, but accurately measuring the effect of a mutation on the overall network is beyond current understanding. Tools to find similarities between biological networks exist, but they focus on mapping the parts of one network to those of another. This is very useful and has found important relationships to inspire research, however, it does not address the problem of estimating distances between networks. In this thesis I develop a model of evolution in terms of network structure. This model represents biologically relevant mutations in terms of their effect on the network. With this an estimate of a distance between the biological entities can be found in terms of the number of mutations needed to mutate a network into another, or mutate an unknown ancestor into two known networks. This contribution responds to the need for tools that can use complex biological networks as a basis for estimating distances between organisms. With this we can develop more accurate models of their evolution and better understand their links. With this we can find shared network patterns that let us transfer our knowledge of one system to another. Using this model, I develop implementations to effectively estimate a distance between biological networks. The validity of the implementations are tested on simulated data with a known, evolutionary history. The evolutionary relationship between the protein interaction networks of the most well studied organisms is also shown, validated by the established phylogeny