Parameterized complexity in computational biology and cognitive psychology

点击翻译按钮获取中文摘要

In many application areas, such as Computational Biology or Bioinformatics, there is a tremendous need for practical algorithms for NP-hard problems (i.e., problems where no polynomial time algorithm is known and most likely no such algorithm exists). Several approaches to tackle NP-hard problems exist including approximation algorithms and fixed-parameter-tractable algorithms. My expertise is in the latter one, which belongs to the area of Parameterized Complexity. We distinguish between parameterized problems which are fixed-parameter tractable and fixed-parameter intractable (i.e., hard for the class W[1]). For parameterized problems that are fixed-parameter tractable, there exist algorithms that have a polynomial-time behaviour for small parameters, that is such an algorithm may be of exponential time in the parameter, but of polynomial time in the non-parameterized input size. In Bioinformatics, I am especially interested in (1) analyzing the relationship between biological sequence data and (2) modeling the evolution of a genome. Other important applications I am investigating are in Cognitive Psychology, that is, the modeling of cognitive theories in general and understanding of human problem solving and decision making strategies in particular. Finally, my principle objectives are to design tractable algorithms for NP-hard problems and to extend the parameterized tractable algorithms design toolkit with new techniques (e.g., kernelization); the modeling of and algorithm design for genome rearrangement problems for given biological sequence data; the modeling of cognitive theories and their validation; and the investigation of human problem solving strategies when confronted with NP-hard problems.