All the connected graphs on up to five nodes. When appearing as an induced subgraph of a larger graph, we call them graphlets. They contain 73 topologically unique node types, called ‘automorphism orbits’. In a particular graphlet, nodes belonging to the same orbit are of the same shade. Graphlet G0 is just an edge, and the degree of a node historically defines how many edges it touches. We generalize the degree to a 73-component ‘graphlet degree’ vector that counts how many times a node is touched by each particular automorphism orbit. This figure is adapted from Pržulj (2007).
An illustration of how the degree of node v in the leftmost panel is generalized into its ‘graphlet degree vector’, or ‘signature’, that counts the number of different graphlets that the node touches, such as triangles (middle panel) or squares (rightmost panel). Values of the 73 coordinates of the graphlet degree vector of node v, GDV (v), are presented in the table.
The alignment of yeast2 and human1 PPI networks. An edge between two nodes means that an interaction exists in both species between the corresponding protein pairs. Thus, the displayed networks appear, in their entirety, in the PPI networks of both species. (a) The largest common connected subgraph (CCS) consisting of 900 interactions amongst 267 proteins. (b) The second largest CCS consisting of 286 interactions amongst 52 proteins; each node contains a label denoting a pair of yeast and human proteins that are aligned.
Comparison of the phylogenetic trees for protists obtained by genetic sequence alignments and by GRAAL's metabolic network alignments. Left: the tree obtained from genetic sequence comparison. Right: the tree obtained from GRAAL. The following abbreviations are used for species: CHO, Cryptosporidium hominis; DDI, Dictyostelium discoideum; CPV, Cryptosporidium parvum; PFA, Plasmodium falciparum; EHI, Entamoeba histolytica; TAN, Theileria annulata; TPV, Theileria parva. The species are grouped into the following classes: ‘Alveolates,’ ‘Entamoeba,’ and ‘cellular slime mould’.