Discrete Biomathematics
Peter F. Stadler
External Scientific Member
Email MPI MIS
Homepage University Leipzig
Phone:
+49 (0) 341 - 9959 - 558
Fax:
+49 (0) 341 - 9959 - 658
Address:
Inselstr. 22
04103 Leipzig
Relationships between Graphs and Networks
In biological applications one if often concerned with graphs that capture different aspects of the same information and thus share structural features. We ask here, in a more general setting, under which conditions a graph H is determined by another graph G and a relation R between the vertex sets of G and H. It turns out that the relation R plays the role of a generalized graph homomorphism with a number of interesting and unexpected properties.
It is rather easy to quantify the differences between two networks when a correspondence between nodes is given. In the context of protein interaction networks, however, this information is partially available and the map between the vertex sets is not necessarily 1-1. It is of interest, therefore, to explore measures of graph distance that are invariant under isomorphism such as spectral distances. We ask, for instance, whether spectral distance measures of biological networks contain meaningful phylogenetic information and hence provide an alternative means of tracing network evolution.