Parameterized Algorithmics for Bioinformatics

本项目旨在使用固定参数算法解决NP-hard生物信息学问题。通过对问题结构的仔细分析，几个看似棘手的问题得到了精确的解决方案。固定参数算法的主要思想是将运行时间的指数部分限制在为问题单独选择的最好的小参数上。尽管运行时间较长，但计算生物信息学中np难题的精确解决方案是值得的，因为它可以更好地分析来自昂贵而费力的实验的数据。生物问题通常具有可用于固定参数算法的特征。在PABI项目的前两年，我们已经为计算生物学中的各种问题开发、实现、设计和评估了固定参数算法和数据约简规则。未来两年的重点，除了为新问题开发算法外，将是不断改进现有的方法，并使其可供生物学研究人员使用。该项目的工作与Rolf Niedermeier教授（耶拿FSU理论计算机科学）小组密切合作。在项目结束时，我们计划举办一个关于生物信息学、参数化算法和算法工程交叉的国际Dagstuhl研究研讨会。

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.