用于寻找NP难生物问题精确解的参数化算法

Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.

作者信息

Hüffner Falk, Komusiewicz Christian, Niedermeier Rolf, Wernicke Sebastian

机构信息

Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany.

Seven Bridges Genomics, Cambridge, MA, USA.

出版信息

Methods Mol Biol. 2017;1526:363-402. doi: 10.1007/978-1-4939-6613-4_20.

DOI:10.1007/978-1-4939-6613-4_20

PMID:27896752

Abstract

Fixed-parameter algorithms are designed to efficiently find optimal solutions to some computationally hard (NP-hard) problems by identifying and exploiting "small" problem-specific parameters. We survey practical techniques to develop such algorithms. Each technique is introduced and supported by case studies of applications to biological problems, with additional pointers to experimental results.

摘要

固定参数算法旨在通过识别和利用特定于问题的“小”参数，有效地找到一些计算困难（NP难）问题的最优解。我们综述了开发此类算法的实用技术。每种技术都通过应用于生物学问题的案例研究进行介绍和支持，并给出了指向实验结果的额外参考。