Parameterized Algorithmics for Bioinformatics

点击翻译按钮获取中文摘要

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 a better analysis of data from expensive and laborious experiments. Biological problems often feature characteristics that can be exploited towards a fixed-parameter algorithm. In the first two years of the PABI project, we have developed, implemented, engineered, and evaluated fixed-parameter algorithms and data reduction rules for various problems in computational biology. The focus of the following two years, besides developing algorithms for new problems, will be to continuously improve existing methods, and to make them available to researchers in biology. Work on this project is in close collaboration with the group of Prof. Rolf Niedermeier (Theoretical Computer Science, FSU Jena). Towards the end of the project, we plan to hold an international Dagstuhl Research Seminar on the intersection of bioinformatics, parameterized algorithmics, and algorithm engineering.