Multivariate algorithmics in biological data analysis

The focus of the thesis is on the development of fixed-parameter algorithms for NP-hard problems arising in computational biology. The considered problems model tasks in data clustering, construction of phylogenetic trees, predicting information on the three-dimensional structure of proteins, and haplotype inference. Many combinatorial problems in the field of computational biology have turned out to be NP-hard. It is commonly believed that there exist no efficient, that is, polynomial-time algorithms for NP-hard problems. Parameterized algorithmics provides an approach to tackle NP-hard problems that has already proven to be successful in bioinformatics. The basic idea is to consider besides the input size a secondary measurement capturing an additional aspect of the input instance, the parameter. Then, the goal is to find algorithms such that the nonpolynomial part of the running time depends only on the parameter. For small parameter values such a parameterized algorithm might constitute an efficient solving strategy. Multivariate algorithmics extends a parameterized algorithm analysis in the sense that it investigates the influence of several parameters on the computational complexity of a problem. The main contributions of the thesis to the known algorithmic results are twofold. First, parameterized algorithms with better running times as known parameterized algorithms are developed for some of the considered problems. Second, the parameterized complexity investigations are extended by considering new parameterizations leading to new solving strategies for some of the considered problems. In particular, this thesis initiates a multivariate complexity study for some of the considered problems. An important algorithmic technique employed in the thesis is kernelization. Here the goal is to transform a given instance in polynomial time into an equivalent instance whose size is bounded by a function only depending on the parameter value. In this sense, kernelization can be seen as polynomial-time preprocessing with provable performance guarantee. Hence, the kernelizations developed in this thesis are not only relevant in the field of parameterized algorithmics but constitute a general contribution to solving the considered problems.