Hotel Estoril Eden, Monte Estoril,
5-8 October 2005



NextText Box: Participants
Text Box: Programme

andom Networks in Genetics

Chris Cannings
University of Sheffield, UK

Networks occur in many guises in genetics; as genealogies, as gene-gene interaction networks, as metabolic networks. These networks, and our observation of them, have arisen as the result of the random processes of mutation, natural selection and evolution, gene duplication, mate selection, experimental protocol and sampling design. Thus a proper understanding of these networks requires an understanding of the theory of random graphs, and the development of new random graph models, see [1] for example. Here I shall present some problems which have arisen recently in these areas; specifically the questions of building genealogies from families, modelling gene-gene interaction networks and generating random marriage-node graphs.

      Problem 1. Within the context of protein-protein interaction networks we, [3], have developed a model of pairwise interactions in the form of our “protein-domain" model. We can explore the consequences of this model by generating a random graph, allocating domains to n proteins at random with some appropriate distribution. We have shown, [3], that the resulting graph has features in common with PRONET (the human Y2H net), and further that sampling from it, in a manner similar to that used in the large yeast screens [2, 5] produces approximately a power-law for the degree distribution, though the underlying structure is very different. Results will be presented on the statistical properties of this class of random graph, and variants of it, including cycle-length distribution, diameter, component size, aspects of sampling from such nets and parameter estimation.

      Problem 2. Suppose one wishes to assemble a complete genealogy of, for example, the UK or Portugal. One possible way of doing this is to randomly sample individuals sequentially, recording for each some suitable set of relatives. Each observation will provide a piece of the whole genealogy. We investigate the behaviour of the growing graph as more pieces are added and how large a sample is needed to capture some given percentage of the whole. What would be the optimal set of relatives to obtain information on from each individual? This problem is related to the existence and position of thresholds in growing graphs, which arises in many application including epidemic theory and models of the WWW.

      Problem 3. In many situations we would like to have a random sample of pedigrees of some appropriate structure, perhaps to test the power of some statistical test. [4] address the question of how one can generate random marriage-node graphs, using a variant of the Prufer code.

[1] Cannings C and Penman C.(2002) Random Graphs. In Stochastic processes:modelling and simulation. Handbook of Statistics 21, 51-91, Ed. C R Rao and D N Shanbhag, Elsevier.
[2] Ito T, Chiba T, Ozawa R, Yoshida M, Hattori M, Sakaki Y (2001) XXX PNAS, 98, 4569-4574.
[3] Thomas AW, Canninngs R, Monk NA & Cannings C. (2003) Biochem Soc Trans. 31 1491-1496.
[4] Thomas AW and Cannings C (2003) I IMA Mathematical Medicine & Biology, 20,261-275.
[5] Uetz P et al (2000) Nature, 403, 623-627.