Mixed-Integer Linear Programming Algorithm for a Computational Protein Design Problem
Mixed-Integer Linear Programming Algorithm for a Computational Protein Design Problem
复制标题
DOI：
10.1021/ie0605985
复制
发表时间：
2007
影响因子：
4.2
通讯作者：
Yushan Zhu
中科院分区：
文献类型：
--
作者：
Yushan Zhu
计算蛋白质设计问题或侧链定位问题是预测蛋白质结构和设计蛋白质序列的计算方法的核心部分。然而，计算蛋白质设计问题是NP-完全的，并且找到该问题的合理近似解也是NP-完全的。在这里，我们提出了一个关键的发现，嵌入在整数线性规划公式的计算蛋白质设计问题的网络流结构，使其相当于一个混合整数线性规划公式与较少的二进制变量。这种新的配方有效地降低了组合的计算蛋白质设计问题的难度，从而使大蛋白质的全局最小能量构象的序列选择变得易于处理，通过使用标准的优化算法。对20个核心蛋白质的初步计算结果表明，混合整数线性规划算法具有很好的收敛性。
The computational protein design problem or the side-chain positioning problem is a central part in computational methods for predicting protein structure and designing protein sequences. However, the computational protein design problem is NP-complete, and it is also NP-complete to find a reasonable approximate solution to this problem. Here, we present a critical finding that the network flow structure embedded in the integer linear programming formulation of the computational protein design problem makes it equivalent to a mixed-integer linear programming formulation with fewer binary variables. This novel formulation effectively reduces the combinatorial difficulty of the computational protein design problem, thereby allowing the sequence selection of the global minimum energy conformation for large proteins to become tractable by using the standard optimization algorithms. Our preliminary calculation results for 20 core redesigned proteins show that the mixed-integer linear programming algorithm with...