Comparative Analysis of Protein Networks: Hard Problems, Practical Solutions

The field of comparative network analysis with an emphasis on the arising computational problems and the different methods that have been used to tackle them is surveyed. Protein function and interaction are predicted, the organization of protein-protein interaction networks into their underlying functional modules are inferred, and biological processes within and across species are linked. NetworkBLAST can be used to align multiple networks, and the size of the alignment graph grows exponentially with the number k of networks. Color coding is based on the idea that by randomly assigning k distinct colors to the vertices of the graph, the task of finding a simple subgraph translates to that of finding a colorful subgraph, namely, one spanning k distinct colors. It is demonstrated that the power of comparative network analysis approaches by comparing their performance with that of methods that are either sequence-based or single-species-based.