Application of graph colouring to biological networks

The author explores the application of graph colouring to biological networks, specifically protein-protein interaction (PPI) networks. First, the author finds that given similar conditions (i.e. graph size, degree distribution and clustering), fewer colours are needed to colour disassortative than assortative networks. Fewer colours create fewer independent sets which in turn imply higher concurrency potential for a network. Since PPI networks tend to be disassortative, the author suggests that in addition to functional specificity and stability proposed previously by Maslov and Sneppen (Science, 296, 2002), the disassortative nature of PPI networks may promote the ability of cells to perform multiple, crucial and functionally diverse tasks concurrently. Second, because graph colouring is closely related to the presence of cliques in a graph, the significance of node colouring information to the problem of identifying protein complexes (dense subgraphs in PPI networks), is investigated. The author finds that for PPI networks where 1-11% of nodes participate in at least one identified protein complex, such as H. sapien, DSATUR (a well-known complete graph colouring algorithm) node colouring information can improve the quality (homogeneity and separation) of initial candidate complexes. This finding may help improve existing protein complex detection methods, and/or suggest new methods. [Includes supplementary material].