AF:Small: Algorithms for Fast Simulation of Macromolecular Interaction Systems

大分子，如蛋白质和核酸，是细胞的主要组成部分。许多大分子通过相互作用来发挥它们的功能。描述这些相互作用有助于阐明生物如何在分子水平上发挥作用，有助于开发治疗癌症等疾病的方法，并有助于设计新的生物启发材料。对大分子相互作用机理的详细理解需要确定它们的络合物的三维结构。这些结构很难用实验技术获得，因此，被称为大分子对接的计算方法可能非常有用。研究人员开发了快速有效的算法和软件，根据世界范围内的评估实验，CAPRI(预测相互作用的关键评估)是预测蛋白质-蛋白质复合体结构的最佳算法和软件之一。这些方法已经在全自动对接服务器ClusPro中实现，该服务器免费供学术使用，拥有超过18,000名固定用户。然而，目前的大分子对接工具对大多数刚性大分子是有效的，这些大分子在结合时不会显著改变构象。这严重限制了该方法的适用性。该项目的目标是开发用于对接柔性分子的新算法。扩大对接方法的范围将有助于更好地了解基本的生物学问题，并将促进生化、生物医学和生物技术研究。此外，这些方法将用于研究生培训和本科生和高中生的教学。对接问题是通过计算确定两个未结合的大分子形成的复合体的三维结构，给出它们各自的结构。解决这个问题需要在复杂的搜索空间中对基于能量的评分函数进行详细采样。由于能量函数评估的高成本和极其崎岖的能源环境，采样在计算上具有挑战性。该方案的目标是开发快速能量评估算法和相应的采样方法，用于模拟多自由度柔性大分子之间的相互作用。其基本思想是将分子系统表示为由铰链连接的刚性团簇的森林(即一组不相交的树)，计算网格上所有刚性团簇的所有相对取向的相互作用能，并将计算的能量网格存储在所有转动和平移状态的流形上。然后，通过将从预先计算的团簇相互作用能查找表中提取的相互作用能相加，可以获得系统的能量。提出的方法的主要优点是显著降低了能源评估的成本。此外，在适当维度的流形上进行搜索。使上述方法在实践中应用的主要挑战是将刚性团簇的大相互作用能表存储在内存中。为了解决这个问题，研究人员将开发使用小波对相互作用能量数据进行压缩的方法和算法，从而获得良好的精度、高压缩水平和快速查找速度。此外，还将开发在搜索流形上使用小波压缩能量网格的专门采样算法，并研究其在柔性大分子对接问题中的应用。将对开发的算法进行性能和行为评估。这些方法将作为开源软件库发布，并通过ClusPro服务器提供给对接的最终用户。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Macro-molecules, such as proteins and nucleic acids, are the major building blocks of the cell. Many macro-molecules perform their function by interacting with each other. 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 macro-molecular interaction mechanisms requires determining the three-dimensional structures of their complexes. These structures are very difficult to obtain using experimental techniques, thus, computational approaches, called macro-molecular docking, can be very useful. The investigator has developed fast and effective 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 18,000 regular users. However, the current macro-molecular docking tools are effective for mostly rigid macro-molecules that do not significantly change conformation upon binding. This severely limits applicability of the approach. The goal of this project is to develop new algorithms for docking flexible molecules. Expanding the scope of the docking approaches will lead to better understanding of fundamental biological questions 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 docking problem is to computationally determine the 3-dimensional (3D) structure of the complex formed by two unbound macro-molecules, given their individual structures. Solving this problem requires detailed sampling of an energy-based scoring function over a complex search space. Due to the high cost of energy function evaluation and the extremely rugged energy landscape the sampling is computationally challenging. The goal of this proposal is to develop algorithms for fast energy evaluation and corresponding sampling methods for the modeling of interactions among flexible macro-molecules with many degrees of freedom. The basic idea is to represent the molecular system as a forest (i.e., a set of disjoint trees) of rigid clusters connected by hinges, calculating the interaction energies for all relative orientations of all rigid clusters on grids, and storing the calculated energy grids on the manifold of all rotational and translational states. The energy of the system can be then obtained by summing up the interaction energies extracted from the pre-calculated lookup tables of cluster interaction energies. The key advantage of proposed approach is a significant reduction in the cost of energy evaluation. In addition, the search is performed on the manifold of appropriate dimension. The major challenge for making the above approach applicable in practice is storing the large interaction energy tables of rigid clusters in memory. To solve this problem, the investigators will develop approaches and algorithms to compress interaction energy data using wavelets, resulting in good accuracy, high level of compression, and fast lookup speed. In addition, specialized sampling algorithms using wavelet compressed energy grids on the search manifold will be developed, and their application to flexible macro-molecular docking problems will be studied. The developed algorithms will be evaluated for performance and behavior. The approaches will be released as an open source software library, as well as made available to end users of docking by means of the ClusPro server.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.