Algorithms for computational biology and bioinformatics

This research area focuses on the development and analysis of efficient algorithms for computational biology and bioinformatics.

Parameterised Algorithmics for Bioinformatics (PABI)

This project aims at solving NP-hard bioinformatics problems using fixed-parameter algorithmics. Using a careful analysis of the problem structure, exact solutions to several seemingly intractable problems come into reach. The main idea of fixed-parameter algorithms is to confine the exponential part of the running time to a preferably small parameter individually chosen for the problem. Despite longer running times, computing exact solutions to NP-hard problems in bioinformatics can pay off, as it may enable improved analysis of data from expensive and laborious experiments. Biological problems often feature characteristics that can be exploited towards a fixed-parameter algorithm.

People:

• Sebastian Böcker (FSU, Dept. of Bioinformatics)
• Rolf Niedermeier (FSU, Dept. of Theoretical Computer Science)

Funding: DFG

Identifying the Unknowns: Towards structural elucidation of small molecules using mass spectrometry (IDUN)

Rapid identification of small compounds from small amounts of substance by mass spectrometry (MS) is of interest in many areas of biology and medicine, such as metabolomics, bio-prospecting, biomarker discovery, and diagnostics. Due to immense technological advances in mass spectrometry over the last years, the amount and complexity of MS data has been growing rapidly. Tandem mass spectrometry offers the potential of identifying small molecules solely from MS fingerprints, but computational analysis of such data is in its infancy; this is one of the major technological hurdles in metabolomics today. The key objective of this project is to develop computational methods to “identify the unknowns”, that is, compounds that cannot be found in any database. For this, we will develop new computational techniques, models, and algorithms for the interpretation of MS fragmentation data from small molecules. As a medium term goal, we want to develop a BLAST-like search tool for searching fragmentation patterns. It turns out that many of the arising problems are computationally hard, and require new algorithmic concepts to guarantee that optimal solutions can be found. We will implement, train, and evaluate our methods to allow an automated processing of metabolite MS data.

People:

• Sebastian Böcker (FSU, Dept. of Bioinformatics)
• Georg Pohnert (FSU, Dept. of Analytical Chemistry)
• Aleš Svatoš (MPI for Chemical Ecology, Jena)

Funding: DFG

Algorithms for the Analysis of Approximate Gene Clusters (3AGC)

The order of genes in genomes can be used to determine the function of unknown genes, as well as the phylogenetic history of organisms. As a result of the increasing speed of genome sequencing huge amounts of data for such studies exist. On the algorithmic side, though, methods are often based on overly simplified genome models, use heuristics to solve optimisation problems, or suffer from long running times. Gene clusters are sets of genes that occur as single contiguous blocks in several genomes. Unfortunately, the requirement of exact occurrences of gene clusters turns out to be too strict for the biological application. We develop models and algorithms for the computation of approximate gene clusters that combine formal strictness with applicability to biological data. At the same time, our algorithms must be swift to allow application to the increasing amount of genome data. We combine methods from combinatorial optimisation and algorithmic graph theory with a statistically sound evaluation. We will implement, train, and evaluate our methods to allow an automated processing of gene order data. Finally, we want to apply our method to biological data, to derive new insights about gene function.

People:

• Sebastian Böcker (FSU, Dept. of Bioinformatics)
• Jens Stoye (Bielefeld University, AG Genome Informatics)
• Jürgen Sühnel (Leibniz Institute for Age Research, FLI)
• Kerstin Voigt (FSU, Fungal Reference Center)

Funding: DFG