Research group: Algorithmic computational biology
Coordinator: Gunnar Klau

Funding period:

• March 2007 - August 2008 (FU Berlin)
• September 2008 - October 2011 (CWI Amsterdam)

Funding: Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)

Illustration: Superposition of two proteins

During the last years, the number of genes known for producing non-coding functional RNA has increased significantly, and it is assumed that many more of these ncRNA genes are still undiscovered. Yet, many functional classes of RNA show little sequence conservation, but rather a conserved secondary structure. A promising avenue to detecting new functional RNAs is thus to look for common structural features shared by a set of related sequences. Within this project we develop algorithmic theory to compute reliable multiple structural alignments of potentially long RNA molecules under a reasonable consumption of computational resources. We employ methods from mathematical programming such as Lagrangian relaxation and solve the problem as an integer linear program resulting from a graph-theoretical reformulation. Our results for the case of pairwise structural alignment show that our current software prototype is among the top programs in terms of speed and alignment quality.

Due to the similiarities of RNA secondary structures and contact map representations of proteins and based on the successful application of the above techniques in the field of RNA structural biology, we are currently extending the project to the area of protein structure research.

Researchers

• Gunnar W. Klau
• Markus Bauer, Mar 2007- Aug 2008 (now with Illumina Cambridge Ltd.)
• Inken Wohlers (PhD student)

Key publications

• I. Wohlers. Multiple Alignment of Protein Distance Matrices with Mathematical Programming, MSc thesis, Freie Universität Berlin, 2008.
• M. Bauer. A Combinatorial Approach to RNA Sequence-Structure Alignments. PhD thesis, Freie Universität Berlin, Germany, 2008.
• M. Bauer, G.W. Klau, and K. Reinert. An exact mathematical programming approach to multiple RNA sequence-structure alignment. Algorithmic Operations Research, Vol. 3, No. 2, 2008. Special Issue on Biology, Medicine, and Health Care.
• M. Bauer, G.W. Klau, and K. Reinert. Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics, 8(271), 2007.
• K. Reinert, M. Bauer, A. Döring, G.W. Klau, and A.L. Halpern. A general paradigm for fast, adaptive clustering of biological sequences. In C. Falter, A. Schliep, J. Selbig, M. Vingron, and D. Walther, editors, Proc. of the German Conference on Bioinformatics (GCB 2007), Potsdam, Germany, volume 115 of GI-Edition, Lecture Notes in Informatics, pages 15-29. Gesellschaft für Informatik, 2007.

Cooperation partners

• Algorithmic Bioinformatics group, Freie Universität Berlin.