An exact algorithm to detect functional modules in protein-protein interaction networks

Gunnar Klau

In modern biomedicine, gene expression profiling has become a well-established tool for disease classification and subtyping. However, the cellular function of an individual protein can often not be understood on an isolated level, but needs to be studied in the context of its interplay with other gene products, for instance, within a protein interaction network. Of particular interest is the identification of novel functional modules in these networks, sharing common cellular function beyond the scope of classical pathways, by means of detecting differentially expressed network regions under different conditions. This requires on the one hand an adequate scoring of the nodes in the network to be identified and on the other hand the availability of an effective algorithm to find maximally scoring network regions.

We present the first exact solution for this problem, which is based on a sound statistical score definition and an unusual connection to the well-known prize-collecting Steiner tree problem, which also appears in network design, eg, for city heating. Despite the complexity of the underlying combinatorial problem, our method typically computes provably optimal subnetworks in large networks in a few minutes. We have applied our algorithm to data from a well-established lymph cancer study involving 194 patients suffering from two different lymphoma subtypes. Our algorithm discovers biologically meaningful dysregulated modules, which include and extend modules that are well-known for the pathogenesis of the two tumor subtypes.