Parameterized Algorithmics for Bioinformatics

生物信息学参数化算法

• 批准号: 162571619
• 负责人: Professor Dr. Sebastian Böcker
• 金额: --
• 依托单位: Institut für Informatik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2009
• 资助国家: 德国
• 起止时间: 2008-12-31 至 2015-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/162571619?language=en
• 关键词: Parameterized; Algorithmics; Bioinformatics

This project aims at solving NP-hard bioinformatics problems using fixed-parameter algorithmics. Using a careful analysis of the problem structure, exact solutions to several seemingly intractable problems come into reach. The main idea of fixed-parameter algorithms is to confine the exponential part of the running time to a preferably small parameter individually chosen for the problem. Despite longer running times, computing exact solutions to NP-hard problems in bioinformatics can pay off, as it may enable a better analysis of data from expensive and laborious experiments. Biological problems often feature characteristics that can be exploited towards a fixed-parameter algorithm. In the first two years of the PABI project, we have developed, implemented, engineered, and evaluated fixed-parameter algorithms and data reduction rules for various problems in computational biology. The focus of the following two years, besides developing algorithms for new problems, will be to continuously improve existing methods, and to make them available to researchers in biology. Work on this project is in close collaboration with the group of Prof. Rolf Niedermeier (Theoretical Computer Science, FSU Jena). Towards the end of the project, we plan to hold an international Dagstuhl Research Seminar on the intersection of bioinformatics, parameterized algorithmics, and algorithm engineering.

该项目旨在利用固定参数算法解决NP-Hard生物信息学问题。通过对问题结构的仔细分析，几个看似棘手的问题就有了确切的解决方案。固定参数算法的主要思想是将运行时间的指数部分限制在为问题单独选择的较小参数内。尽管运行时间更长，但计算生物信息学中NP-Hard问题的准确解决方案是有回报的，因为它可能使对昂贵而费力的实验的数据进行更好的分析。生物学问题通常具有可用于固定参数算法的特征。在Pabi项目的头两年，我们为计算生物学中的各种问题开发、实现、工程和评估了固定参数算法和数据约简规则。接下来的两年，除了为新问题开发算法外，重点将是不断改进现有的方法，并将它们提供给生物学研究人员。这个项目的工作是与罗尔夫·尼德迈尔教授(FSU Jena理论计算机科学)密切合作的。在项目结束时，我们计划举办一次国际达格斯图尔研究研讨会，主题是生物信息学、参数算法和算法工程的交叉点。

项目成果

Speedy Colorful Subtrees

快速彩色子树

• DOI: 10.1007/978-3-319-21398-9_25
• 发表时间: 2015
• 作者: W. Timothy J. White;Stephan Beyer;Kai Dührkop;Markus Chimani;Sebastian Böcker
• 通讯作者: Sebastian Böcker

Exact Algorithms for Cluster Editing: Evaluation and Experiments

• DOI: 10.1007/s00453-009-9339-7
• 发表时间: 2011-06-01
• 期刊: ALGORITHMICA
• 影响因子: 1.1
• 作者: Boecker, Sebastian;Briesemeister, Sebastian;Klau, Gunnar W.
• 通讯作者: Klau, Gunnar W.

Comprehensive cluster analysis with Transitivity Clustering

• DOI: 10.1038/nprot.2010.197
• 发表时间: 2011-03-01
• 期刊: NATURE PROTOCOLS
• 影响因子: 14.8
• 作者: Wittkop, Tobias;Emig, Dorothea;Baumbach, Jan
• 通讯作者: Baumbach, Jan

On the parameterized complexity of the repetition free longest common subsequence problem

无重复最长公共子序列问题的参数化复杂度

• DOI: 10.1016/j.ipl.2011.12.009
• 发表时间: 2012
• 期刊: Inf. Process. Lett.
• 作者: Guillaume Blin;Paola Bonizzoni;Riccardo Dondi;Florian Sikora
• 通讯作者: Florian Sikora

Finding and Counting Vertex-Colored Subtrees

查找并计算顶点颜色子树

• DOI: 10.1007/s00453-011-9600-8
• 发表时间: 2013
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Sylvain Guillemot;Florian Sikora
• 通讯作者: Florian Sikora