Parameterized complexity in computational biology and cognitive psychology

在许多应用领域，如计算生物学或生物信息学，对于NP-Hard问题(即，不知道多项式时间算法，并且很可能不存在这样的算法的问题)，非常需要实用的算法。存在几种解决NP-Hard问题的方法，包括近似算法和固定参数易处理算法。我的专长是后者，它属于参数化复杂性领域。我们区分了固定参数易处理的参数化问题和固定参数难处理的参数化问题(即对于W[1]类是困难的)。对于固定参数可处理的参数化问题，存在对小参数具有多项式时间性态的算法，即这样的算法在参数中可能是指数时间，但在非参数输入大小中是多项式时间。在生物信息学中，我特别感兴趣的是(1)分析生物序列数据之间的关系和(2)对基因组进化进行建模。我正在研究的其他重要应用是认知心理学，也就是一般认知理论的建模，特别是对人类问题解决和决策策略的理解。最后，我的主要目标是为NP-Hard问题设计易于处理的算法，并使用新技术(例如，核化)扩展参数化易处理算法设计工具包；针对给定生物序列数据的基因组重排问题的建模和算法设计；认知理论的建模及其验证；以及当遇到NP-Hard问题时人类问题解决策略的研究。

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.