SGER: A Distributed Hybrid Optimization Technique for Protein Structure Prediction

优化问题在科学、工程和商业的许多领域自然出现。其中一些问题是离散的，其解决方案涉及在有限数量的可能构象中找到最佳配置（例如，运筹学中的生产调度问题或计算机工程中的电路最小化问题）。其他优化问题本质上是连续的，其解决方案涉及在某个无限空间中找到最佳解决方案（例如，物理学中的熵最小化，金融中的投资组合分配问题，或土木工程中的弹性研究）。通常，存在一些有用的抽象，可以将一种类型的问题转换为另一种类型的更简单的问题。生物科学中一些最引人注目的优化问题也表现出这种对偶性。一个明显的例子是预测蛋白质（连续的）三维形状的问题，从而预测它的生物功能，从它的（离散的）初级结构，表示为组成氨基酸的序列。目前，蛋白质结构最准确的测定方法是实验手段，如x射线晶体学或核磁共振波谱学。计算生物学家的一个主要目标是不借助实验观察就能预测三级结构。该项目为蛋白质结构预测问题提供了一种新的方法。特别是，将一种用于离散（组合）优化的新型分布式搜索技术与一种用于解决连续优化问题的高效多项式时间内点算法相结合。每种方法都将使用独立的、尽管相关的能量模型，而离散系统将“提出”供连续模型评估的构象。目标是通过在两种方法之间交换信息来提高计算效率，同时利用并行性来求解实际大小的蛋白质。具体来说，该项目将构建一个原型混合计算工具，将原型应用于蛋白质构象问题，并通过与现有计算方法和物理现实进行比较来评估解决方案。

Abstract Optimization problems arise naturally in many areas of science, engineering, and busi-ness. Some of these problems are discrete, where the solution involves finding the best configuration over a finite number of possible conformations (for example, production scheduling problems in operations research or circuit minimization problems in computer engineering). Other optimization problems are inherently continuous, where the solution involves finding the best solution in some infinite space (for example, entropy minimiza-tion in physics, portfolio allocation problems in finance, or elasticity studies in civil engi-neering). Often, useful abstractions exist which convert one type of problem into a simpler problem of the other type. Some of the most compelling optimization problems in the biological sciences also dis-play this same kind of duality. An obvious example is the problem of predicting a protein's (continuous) three-dimensional shape- and, consequently, its biological function-from its (discrete) primary structure, expressed as the sequence of constituent amino acids { Friesne~6 . Curren~y, protein structure is most accurately determined by experimental means, such as X-Ray crystallography or NMR spectroscopy. A primary goal for compu- tational biologists is to be able to predict the tertiary structure without resorting to experi-mental observation. This project takes a new approach to the problem of predicting protein structure. In partic-ular, the merger of a novel distributed search technique for discrete (combinatorial) opti-mization, and an efficient, polynomial time, interior-point algorithm for solving continuous optimization problems. Each approach will operate using separate, albeit related, energy models, with the discrete system "proposing" conformations for the con-tinuous model to evaluate. The goal is to increase the efficiency of the computation by exchanging information between the two approaches while exploiting parallelism in order to solve realistically-sized proteins. Specifically the project will construct a prototype hybrid computational tool, apply the prototype to a protein conformation problem, and evaluate the solution by comparison to both existing computational approaches and physi-cal reality.