CCF: AF: EAGER: Systematic Construction of Heuristic Algorithms for Combinatorial Optimization Problems in Biology

在许多实际情况下，启发式算法可靠地为现实生活中的优化问题实例提供满意的解决方案，尽管计算复杂性理论表明这些问题是难以解决的。这个项目的中心目标是帮助理解这个表面上的矛盾，并把启发式算法的构建和评估放在一个更坚实的基础上。该项目将开发一种通用的经验方法，用于在定义良好的启发式算法策略中选择参数和子程序的最佳选择。该方法是经验性的，并假设有一个典型问题实例的供应，可用于训练算法策略和评估其性能。对最优参数和子程序的搜索将被视为一个优化问题。该项目将引入隐式命中集问题的概念，证明一类广泛的NP-hard组合优化问题可以被框架为隐式命中集问题，并系统地推导和评估本课程中三个问题的启发式算法：多基因组对齐，反馈顶点集问题和反馈弧集问题。启发式算法设计的进一步例子将来自计算分子生物学，其长期目标是从大量数据集中提取有关蛋白质如何协同工作以在细胞水平上执行生命过程的信息。这项研究将集中于蛋白质-蛋白质相互作用（PPI）网络，其中顶点是物种内的蛋白质，边缘表示蛋白质之间的直接相互作用。目标将是发现保守的蛋白质模块：相互作用丰富的蛋白质组，其相互作用模式在两个或更多物种中是保守的。这些模块对应于PPI网络的子图，这些子图具有许多内部边缘，相对较少的外部边缘，以及从一个物种到另一个物种持续存在的结构。目前已有几个用于寻找保守蛋白模块的软件包，本项目开发的算法将与这些软件包进行系统比较。这项研究自然会导致计算图论中的基本抽象问题，例如将图划分为具有高密度边的顶点不相交子图的问题，或彩色子图问题，其中图的每个顶点被分配一种颜色，目标是找到一个包含每种颜色至少一个顶点的小连接子图。该项目将系统地推导和评估这些问题的启发式算法。由于启发式算法是实际解决NP-hard优化问题的重要工具，并且由于实践中出现的大多数优化问题都是NP-hard，因此将启发式算法的创建，比较和验证系统化的尝试可能会对本提案所追求的许多应用领域产生影响。

In many practical situations heuristic algorithms reliably give satisfactory solutions to real-life instances of optimization problems, despite evidence from computational complexity theory that the problems are intractable. The central goal of this project is to contribute to an understanding of this seeming contradiction, and to put the construction and evaluation of heuristic algorithms on a firmer footing.The project will develop a general empirical method for selecting an optimal choice of parameters and subroutines within a well-defined heuristic algorithmic strategy. The method is empirical, and assumes the availability of a supply of typical problem instances which can be used to train the algorithmic strategy and evaluate its performance. The search for optimal parameters and subroutines will be treated as an optimization problem in its own right.The project will introduce the concept of an implicit hitting set problem, demonstrate that a broad class of NP-hard combinatorial optimization problems can be framed as implicit hitting set problems, and systematically derive and evaluate heuristic algorithms for three problems in this class: multi-genome alignment, the feedback vertex set problem, and the feedback arc set problem.Further examples of heuristic algorithm design will be drawn from computational molecular biology, where a long-term goal is to extract, from large data sets, information about how proteins work together to carry out life processes at a cellular level. This investigation will focus on protein-protein interaction (PPI) networks, in which the vertices are the proteins within a species and the edges indicate direct interactions between proteins. The goal will be to discover conserved protein modules: richly interacting sets of proteins whose patterns of interaction are conserved across two or more species. Such modules correspond to subgraphs of a PPI network that have many internal edges, relatively few external edges, and a structure that persists from one species to another.There are several existing software packages for finding conserved protein modules, and the algorithms developed in this project will be compared systematically with these packages.This research leads naturally to fundamental abstract problems in computational graph theory, such as the problem of partitioning a graph into vertex-disjoint subgraphs with a high density of edges, or the colorful subgraph problem, in which each vertex of a graph is assigned a color, and the goal is to find a small connected subgraph containing at least one vertex of each color. The project will systematically derive and evaluate heuristic algorithms for these problems.Since heuristic algorithms are an essential tool for the practical solution of NP-hard optimization problems, and since most optimization problems arising in practice are NP-hard, the attempts to systematize the creation, comparison and validation of heuristic algorithms may have repercussions for many application areas beyond those pursued in this proposal.