Research group: Algorithmic computational biology
Coordinator: Gunnar Klau

Funding period: Feb 2009 - Feb 2012

In systems biology, biological process are often modelled as networks. Examples include protein-protein interaction, metabolic, signal transduction, and regulatory networks. The increasing quality and quantity of available data creates the need for automated analysis methods to better understand cellular processes, network organization, evolutionary changes, and disease mechanisms. Based on the assumption that evolutionary conservation implies functional significance, comparative approaches may help improve the accuracy of data, elucidate protein pathways and complexes, generate, investigate, and validate hypotheses about the underlying networks, and transfer functional annotations. In addition to component-based comparative approaches, network alignments provide the means to study conserved network topology such as common pathways and more complex network motifs. Yet, unlike in classical sequence alignment, the comparison of networks becomes computationally more challenging, as most meaningful assumptions instantly lead to NP-hard problems.

Illustration: Network alignment and corresponding bipartite alignment graph

In this project we develop novel algorithms as well as statistical theory for network alignment, comparison, and query problems. Currently, we cooperate with the following partners:

• We evaluate the usefulness of our algorithms in a functional annotation pipeline for proteins with the Knowledge Management in Bioinformatics group of the Humboldt-Universität Berlin, Germany.
• We investigate randomization models for a given metabolic network by partitioning reaction environemnts into equivalence classes based on their topology with the Computational Systems Biochemistry group at Charité, Berlin, Germany.
• We apply our methods to compare bacterial metabolic networks with the Institute for Food Research (NIZO).

Researchers

• Gunnar W. Klau
• Stefan Canzar

Key publications

• G.W. Klau. A new graph-based method for pairwise global network alignment. BMC Bioinformatics, Vol. 10, Suppl. 1, 2009.

Cooperation partners

• Knowledge Management in Bioinformatics group, Humboldt-Universität Berlin.
• Computational Systems Biochemistry group at Charité University Medicine, Berlin
• NIZO Food Research, The Netherlands.