DFG Project PABI: Parameterized Algorithmics for Bioinformatics
Project PABI (DFG Project NI 369/7-1) started in October 2007.
The project "Parameterized algorithmics for bioinformatics (PABI)" heads at exploring and understanding
the reasons for computational intractability (NP-hardness) of a large number of problems
in algorithmic bioinformatics. As turned out in recent years, the hardness of these problems can
often be attributed to problem-specific parameters. In particular, if these problem parameters are
small - and if the seemingly unavoidable combinatorial explosion inherent to the NP-hard problems
can be confined to these parameters - then the concept of fixed-parameter tractability may offer an
opportunity for efficient (and exact) algorithms despite NP-hardness.
This is a joint project with the Chair of Bioinformatics
of the Friedrich Schiller University of Jena.
Head: Rolf Niedermeier