Algorithmics and Bioinformatics Group

The research of the working group Algorithmics and Bioinformatics headed by Prof. Dr. Markus Nebel addresses different questions in the area of ​​algorithms. We examine the efficiency of algorithms and data structures with the aim of improving them. To this end we focus on the average-case behaviour of structural and performance parameters. Using reasonable assumptions about the distribution of inputs, the resulting expected values provide better insight into an algorithm’s complexity than extreme cases, especially if the latter are highly unlikely.

With our tool MaLiJAn and the theory behind – the so-called maximum likelihood analysis – a semi-automatic analysis becomes possible and offers a bridge between analytical and experimental analysis of algorithms. With its help, it is possible to examine algorithms (in their Java implementation) in the context of arbitrary input data, and to understand which of their functions contribute significantly to resource consumption (space, time, branch mispredictions, ...). From this knowledge, improvements can be derived.

A second focus of our work comes from bioinformatics. Our expertise in efficient algorithms and data structures as well as the mathematical modelling and analysis are of great benefit to our bioinformatic research and the development of efficient algorithms as well as their implementation in tools for scientists.

We are currently working on improved methods for predicting the structure of RNA molecules and – within the international DFG Graduate School Diversity and Dynamics of Genomes – on space and time efficient algorithms for the clustering of large sequence data sets.