Hotel Estoril Eden, Monte Estoril, 



Chris Cannings Networks occur in many guises in genetics; as genealogies, as genegene 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 genegene interaction networks and generating random marriagenode graphs. Problem 1. Within the context of proteinprotein interaction networks we, [3], have developed a model of pairwise interactions in the form of our “proteindomain" 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 powerlaw 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 cyclelength 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 marriagenode graphs, using a
variant of the Prufer code.
References:
