III: Small: Combinatorial Optimization Methods for Problems in Molecular Biology and Genetics

在科学、工程和商业的几乎每一个领域，都会出现优化问题，对于这些优化问题，没有已知的求解方法可以保证在合理的计算时间内得到大型实例的满意解。计算复杂性理论证实了这些问题中的大多数都是棘手的。然而，这些问题需要在实践中解决，启发式算法在大多数情况下都能很好地工作，尽管不是在最坏的情况下。启发式算法的不合理成功是计算机科学中的一大谜团。这个项目将对启发式算法的设计进行四个案例研究。1.隐碰集问题是一类约束满足问题，其约束条件太多而无法显式列出。许多经典的优化问题都符合这个模型。将研究一种通用方法，其目的是列举一小部分足以确定最佳解决方案的约束条件。这种方法已经被证明成功地解决了一组重要的基因组比对问题。2.整数规划可用于根据实验数据重建相互作用的基因和蛋白质网络。将网络建模为互连的门的接线图，并使用整数规划来重构门的逻辑功能。该方法已经成功地定位了控制酵母端粒长度的TLM基因的子网络，并将应用于其他模型。3.研究的另一个重点是发现相互作用的蛋白质聚集体，形成在进化中保守的调节模块。给定一个物种中的这样一个模块，在另一个物种中找到对应的模块的问题被抽象为一个图论问题，称为多彩子图问题。我们的计划是开发快速而准确的启发式算法来解决这个问题。4.最后一个问题是将一个图划分成大量的小而密集的簇。给出了遗传学的一个应用，涉及到一组遗传相关个体之间的家庭关系的自动推断，该项目所研究的问题可以作为测试用例来理解约束松弛、整数规划和局部搜索等基本算法策略的适用性。

In virtually every area of science, engineering and commerce, optimization problems arise for which no known solution method is guaranteed to yield satisfactory solutions to large instances using a reasonable amount of computation time. Computational complexity theory confirms the intractability of most of these problems. Nevertheless, these problems demand to be solved in practice, and very often heuristic algorithms work quite well in most cases, although not in the worst case. The unreasonable success of heuristic algorithms is one of the great mysteries in computer science.This project will undertake four case studies in the design of heuristic algorithms. 1. Implicit hitting set problems are a class of constraint satisfaction problems in which the constraints are too numerous to list explicitly. Many classic optimization problems fit this model. A generic approach will be investigated which aims to enumerate a small set of constraints sufficient to determine the optimal solution. This approach has proved successful in solving a significant group of genome alignment problems. 2. Integer programming can be used to reconstruct a network of interacting genes and proteins from experimental data. A network is modeled as a wiring diagram of interconnected gates, and integer programming is used to reconstruct the logical functions of the gates. The method has successfully mapped the subnetwork of TLM genes that control telomere length in yeast, and will be applied to other models. 3. Another focus of the research is the discovery of aggregates of interacting proteins that form regulatory modules conserved in evolution. Given such a module in one species, the problem of finding a corresponding module in a second species is abstracted as a graph-theoretic problem called the colorful subgraph problem. The plan is to develop fast and accurate heuristic algorithms for the solution of this problem. 4. The final problem is partitioning a graph into a large number of small dense clusters. An application is given from genetics, involving the automatic inference of the familial relationships among a group of genetically related individuals.The problems studied in this project can serve as test cases for understanding the applicability of fundamental algorithmic strategies such as constraint relaxation, integer programming and local search.