DFG Project PABI: Parameterized Algorithmics for Bioinformatics

Project Description

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.

People