Parameterized complexity in computational biology and cognitive psychology

计算生物学和认知心理学中的参数化复杂性

• 批准号: 249898-2006
• 负责人: Stege, Ulrike
• 金额: $ 1.38万
• 依托单位: University of Victoria
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=362495
• 关键词: Parameterized; complexity; computational; biology; cognitive

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.

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