Research group: Algorithmic computational biology
Coordinator: Gunnar Klau

With the exponential growth of expression and protein-protein interaction (PPI) data, the frontier of research in system biology shifts more and more to the integrated analysis of these large datasets. Of particular interest is the identification of functional modules in PPI networks, sharing common cellular function beyond the scope of classical pathways, by means of detecting differentially expressed regions in PPI networks. 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 the maximally scoring network regions. Various heuristic approaches have been proposed in the literature.

Illustration: Protein-protein interaction network and smaller extracted subnetwork module

In a cooperation with the Biocenter of the University of Würzburg we have presented the first exact solution for this problem, which is based on integer linear programming and its connection to the well-known prize-collecting Steiner tree problem from Operations

Research. Despite the NP-hardness of the underlying combinatorial problem, our method typically computes provably optimal subnetworks in large PPI networks in a few minutes. An essential ingredient of our approach is a scoring function defined on network nodes. We have proposed a new additive score with two desirable properties: (i) it is scalable by a statistically interpretable parameter and (ii) it allows a smooth integration of data from various sources. We have applied our method to a well-established lymphoma microarray dataset in combination with associated survival data and the large publicly available interaction network of to identify functional modules by computing optimal-scoring subnetworks. In particular, we find a functional interaction module associated with proliferation over-expressed in the aggressive ABC subtype as well as modules derived from non malignant by-stander cells.

In this project we extend the prototypical algorithm in several ways. We intend to integrate additional types of data like co-expression of genes, to analyze the dynamics of the subnetwork signals, and to apply it to different diseases.  Furthermore, we plan to apply the subnetwork module approach to analyse cytokine responses in murine and human primary hepatocytes on the level of the entire cellular system.

Key publications

• M.T. Dittrich, G.W. Klau, A. Rosenwald, T. Dandekar, T. Müller. Identifying Functional Modules in Protein-Protein Interaction Networks: An Integrated Exact Approach, Bioinformatics, Vol. 24, pp. i223-i231, Oxford University Press, 2008.

Cooperation partners

• Biocenter of the University of Würzburg, Germany.