Multivariate algorithmics in biological data analysis

Viac o knihe

The thesis focuses on developing fixed-parameter algorithms for NP-hard problems in computational biology, including data clustering, phylogenetic tree construction, protein structure prediction, and haplotype inference. Many combinatorial challenges in this field are NP-hard, and it is widely accepted that efficient polynomial-time algorithms for these problems do not exist. Parameterized algorithmics offers a promising approach, where, alongside input size, a secondary measurement, or parameter, is considered. The goal is to create algorithms where the nonpolynomial part of the running time depends solely on this parameter. For small parameter values, such algorithms can be efficient. Multivariate algorithmics further explores how multiple parameters affect computational complexity. This thesis contributes to existing algorithmic results by developing parameterized algorithms with improved running times for certain problems and extending parameterized complexity investigations through new parameterizations, leading to innovative solving strategies. A key technique employed is kernelization, which transforms an instance into a smaller, equivalent one in polynomial time, with size bounded by a function of the parameter. This approach serves as polynomial-time preprocessing with guaranteed performance, making the kernelizations developed here significant not only in parameterized algorithmics but also as a broader contribution