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

蛋白质是细胞的主要组成部分。许多蛋白质通过与其他蛋白质相互作用来发挥其功能。在一个典型的细胞中，成千上万种不同的蛋白质相互作用发生。表征这些相互作用有助于阐明生物体如何在分子水平上发挥作用，有助于开发针对癌症等疾病的治疗方法，并促进新型生物启发材料的设计。详细了解蛋白质相互作用机制需要确定蛋白质-蛋白质复合物的三维结构。这些结构是很难获得使用实验技术，因此，计算方法可以是非常有用的。Kozakov，Paschaldom，Vajda和Vakili的团队开发了算法和软件，根据全球评估实验卡普里（预测相互作用的关键评估），这些算法和软件是预测蛋白质-蛋白质复合物结构的最佳方法之一。这些方法已经在完全自动化的对接服务器PocketPro中实现，该服务器免费供学术使用，拥有超过10，000名普通用户。然而，目前的工具在计算上要求太高，无法服务于如此庞大的用户群或在基因组规模上对蛋白质相互作用进行建模。该项目的目标是使用严格的几何和生物物理原理，以大大提高对接算法的效率，同时保持所生成的模型的准确性。蛋白质复合物的快速建模将导致更好地理解细胞和系统水平上的基本生物学问题，并将促进生物化学，生物医学和生物技术研究。此外，该方法将用于培训研究生和教学本科生和高中生。蛋白质对接问题是计算确定的3-维（3D）结构的复合物形成的两个未结合的蛋白质，给定其各自的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.