AF: Small: Manifold optimization algorithms for protein-protein docking

蛋白质是细胞的主要组成部分。许多蛋白质通过与其他蛋白质相互作用来发挥功能。在一个典型的细胞中，会发生成千上万种不同的蛋白质相互作用。描述这些相互作用有助于阐明生物体在分子水平上的功能，有助于开发针对癌症等疾病的治疗方法，并促进新型生物灵感材料的设计。详细了解蛋白质相互作用机制需要确定蛋白质-蛋白质复合物的三维结构。这些结构很难用实验技术得到，因此，计算方法是非常有用的。Kozakov, Paschalidis， Vajda和Vakili团队开发的算法和软件，根据全球评估实验CAPRI（预测相互作用的关键评估），是预测蛋白质-蛋白质复合物结构的最佳算法和软件之一。这些方法已经在完全自动化的对接服务器ClusPro中实现，该服务器免费供学术使用，拥有超过10,000名固定用户。然而，目前的工具在计算上要求太高，无法服务于如此大的用户群或在基因组规模上模拟蛋白质相互作用。该项目的目标是使用严格的几何和生物物理原理，在保持生成模型准确性的同时，大幅提高对接算法的效率。更快地建立蛋白质复合物的模型将有助于更好地理解细胞和系统水平上的基本生物学问题，并将促进生化、生物医学和生物技术的研究。此外，该方法还将用于研究生的培养和本科生、高中生的教学中。蛋白质对接问题是通过寻找基于能量的评分函数的全局最小值，计算确定由两个未结合的蛋白质组成的复合物的三维（3D）结构，给定它们各自的三维结构。如果其中一种蛋白质（被认为是受体）处于固定的位置和方向，则搜索空间包括另一种蛋白质（被认为是配体）的6D旋转/平移空间，以及代表两种蛋白质灵活性的额外自由度。由于能量函数具有大量被高势垒分隔的局部极小值，因此最小化问题极具挑战性。拟议的项目旨在利用该小组为对接协议的各个组件开发的创新的流形和基于优化的方法，以便(i)将算法建立在坚实的理论基础上，（ii）更严格地研究它们的性能和行为，以及（iii）开发可应用于其他应用领域的算法的可推广特性。这项工作将集中在四个关键算法上。首先，将研究流形上的快速傅立叶变换（MFFT），该方法能够在一个蛋白质相对于另一个蛋白质的刚体运动空间中进行全局系统搜索。本文将分析MFFT的计算复杂度，并进行不同带宽设置下的数值性能测试。其次，将探索基于低估的采样技术，作用于相同的流形，并针对中等范围搜索来完善MFFT解决方案。将开发和测试各种低估器。第三，开发基于流形的柔性蛋白优化局部优化方法。在每种情况下，将比较不同的流形参数化和不同的最小化方法。最后，利用马尔可夫随机场理论的原理，提出了一种新的侧链填充公式和蛋白质对接中出现的其他问题。在此背景下，将开发涉及最大权重独立集（MWIS）问题和广义信念传播的不同解决方法。所开发的算法将作为开源软件库发布，用于蛋白质对接和其他应用领域。

Proteins are the major building blocks of the cell. Many proteins perform their function by interacting with other proteins. In a typical cell hundreds of thousands of different protein interactions take place. Characterizing these interactions helps elucidate how living organisms function at the molecular level, contributes towards the development of treatments against diseases such as cancer and facilitates the design of novel bio-inspired materials. Detailed understanding of protein interaction mechanisms requires determining the three-dimensional structures of protein-protein complexes. These structures are very difficult to obtain using experimental techniques, thus, computational approaches can be very useful. The team of Kozakov, Paschalidis, Vajda and Vakili has developed algorithms and software that, according to the worldwide evaluation experiment CAPRI (Critical Assessment of Predicted Interactions), are among the best for predicting the structures of protein-protein complexes. These methods have been implemented in the fully automated docking server ClusPro, which is free for academic use, and has over 10,000 regular users. However, the current tools are computationally too demanding to serve such a large user base or to model protein interactions on a genomic scale. The goal of this project is to use rigorous geometrical and biophysical principles to substantially improve the efficiency of docking algorithms while retaining the accuracy of the generated models. Faster modeling of protein complexes will lead to better understanding of fundamental biological questions at both the cellular and system levels and will facilitate biochemical, biomedical, and biotechnology research. In addition, the methods will be used in training graduate students and teaching undergraduate and high school students.The protein-docking problem is to computationally determine the 3-dimensional (3D) structure of the complex formed by two unbound proteins, given their individual 3D structures, by finding the global minimum of an energy-based scoring function. If one of the proteins, considered the receptor, is in fixed position and orientation, the search space includes the 6D rotational/translational space of the other protein, considered the ligand, as well as additional degrees of freedom that represent the flexibility of the two proteins. Since the energy function has a large number of local minima separated by high barriers, the minimization problem is extremely challenging. The proposed project aims to draw on the innovative manifold and optimization-based approaches that the group has developed for various components of docking protocols in order to (i) put the algorithms on a solid theoretical footing, (ii) study their performance and behavior more rigorously, and (iii) develop generalizable features of the algorithms that can be applied to other application domains. The work will focus on four key algorithms. First, the Fast Fourier Transform on Manifolds (MFFT) will be studied, which enables global systematic search in the space of rigid body motions of one protein with respect to the other. The computational complexity of MFFT will be analyzed and numerical performance tests for different bandwidth settings will be conducted. Second, underestimation-based sampling techniques will be explored, acting on the same manifold and targeting a medium-range search to refine MFFT solutions. A variety of underestimators will be developed and tested. Third, manifold-based local optimization approaches for flexible protein optimization will be developed. In each case, different manifold parameterizations and different minimization approaches will be compared. Finally, a new formulation of side-chain packing and other problems arising in protein docking will be developed using principles from the theory of Markov Random Fields. In this context, different solution approaches will be developed involving the Maximum Weight Independent Set (MWIS) problem and generalized belief propagation. The algorithms developed will be released as an open source software library to be used both for protein docking and in other application domains.