Purvine Emilie, Monson Kyle, Jurrus Elizabeth, Star Keith, Baker Nathan A
Division of Applied Mathematics, Brown University , Providence, Rhode Island 02912, United States.
J Phys Chem B. 2016 Aug 25;120(33):8354-60. doi: 10.1021/acs.jpcb.6b02059. Epub 2016 May 3.
There are several applications in computational biophysics that require the optimization of discrete interacting states, for example, amino acid titration states, ligand oxidation states, or discrete rotamer angles. Such optimization can be very time-consuming as it scales exponentially in the number of sites to be optimized. In this paper, we describe a new polynomial time algorithm for optimization of discrete states in macromolecular systems. This algorithm was adapted from image processing and uses techniques from discrete mathematics and graph theory to restate the optimization problem in terms of "maximum flow-minimum cut" graph analysis. The interaction energy graph, a graph in which vertices (amino acids) and edges (interactions) are weighted with their respective energies, is transformed into a flow network in which the value of the minimum cut in the network equals the minimum free energy of the protein and the cut itself encodes the state that achieves the minimum free energy. Because of its deterministic nature and polynomial time performance, this algorithm has the potential to allow for the ionization state of larger proteins to be discovered.
计算生物物理学中有几个应用需要对离散相互作用状态进行优化，例如氨基酸滴定状态、配体氧化态或离散旋转异构体角度。这种优化可能非常耗时，因为它在要优化的位点数量上呈指数级增长。在本文中，我们描述了一种用于优化大分子系统中离散状态的新的多项式时间算法。该算法改编自图像处理，并使用离散数学和图论技术，根据“最大流 - 最小割”图分析来重新表述优化问题。相互作用能量图是一种顶点（氨基酸）和边（相互作用）用各自能量加权的图，它被转换为一个流网络，其中网络中的最小割值等于蛋白质的最小自由能，并且割本身编码实现最小自由能的状态。由于其确定性性质和多项式时间性能，该算法有潜力发现更大蛋白质的电离状态。
