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

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

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.