Parameterized complexity in computational biology and cognitive psychology

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

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.