Parameterized Algorithmics for Bioinformatics

该项目旨在利用固定参数算法解决NP-Hard生物信息学问题。通过对问题结构的仔细分析，几个看似棘手的问题就有了确切的解决方案。固定参数算法的主要思想是将运行时间的指数部分限制在为问题单独选择的较小参数内。尽管运行时间更长，但计算生物信息学中NP-Hard问题的准确解决方案是有回报的，因为它可能使对昂贵而费力的实验的数据进行更好的分析。生物学问题通常具有可用于固定参数算法的特征。在Pabi项目的头两年，我们为计算生物学中的各种问题开发、实现、工程和评估了固定参数算法和数据约简规则。接下来的两年，除了为新问题开发算法外，重点将是不断改进现有的方法，并将它们提供给生物学研究人员。这个项目的工作是与罗尔夫·尼德迈尔教授(FSU Jena理论计算机科学)密切合作的。在项目结束时，我们计划举办一次国际达格斯图尔研究研讨会，主题是生物信息学、参数算法和算法工程的交叉点。

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.