Solving and analyzing side-chain positioning problems using linear and integer programming
Solving and analyzing side-chain positioning problems using linear and integer programming
复制标题
DOI：
10.1093/bioinformatics/bti144
复制
发表时间：
2005-04-01
期刊：
影响因子：
5.8
通讯作者：
Singh, M
中科院分区：
文献类型：
--
作者：
Kingsford, CL;Chazelle, B;Singh, M
动机：侧链定位是同源建模和蛋白质设计的核心组成部分。在问题的常见公式中，骨干是固定的，侧链构象来自rotamer库，并优化了成对的能量函数。即使在此问题上找到合理的近似解决方案也是NP的完整性。我们试图将这种硬度结果放在实际的环境中。分析：我们提出了侧链定位的整数线性编程（ILP）表述，使我们能够解决较大的问题大小。我们放宽了完整性约束，从而获得多项式线性编程（LP）启发式。我们将LP应用于本机和同源骨架上的侧链，并选择侧链进行蛋白质设计。令人惊讶的是，当将侧链定位在天然和同源骨架上时，通常可以使用LP找到使用简单，生物学相关的能量功能的最佳溶液。另一方面，通常无法直接使用LP解决设计问题。但是，仍然可以使用更昂贵的ILP程序找到大型实例的最佳解决方案。尽管不同的能量功能也会影响问题的难度，但LP/ILP方法能够找到最佳解决方案。我们的分析是第一个大规模证明，基于LP的方法在寻找侧链定位问题的最佳（且连续的近乎最佳）解决方案方面非常有效。
Motivation: Side-chain positioning is a central component of homology modeling and protein design. In a common formulation of the problem, the backbone is fixed, side-chain conformations come from a rotamer library, and a pairwise energy function is optimized. It is NP-complete to find even a reasonable approximate solution to this problem. We seek to put this hardness result into practical context.Results: We present an integer linear programming (ILP) formulation of side-chain positioning that allows us to tackle large problem sizes. We relax the integrality constraint to give a polynomial-time linear programming (LP) heuristic. We apply LP to position side chains on native and homologous backbones and to choose side chains for protein design. Surprisingly, when positioning side chains on native and homologous backbones, optimal solutions using a simple, biologically relevant energy function can usually be found using LP. On the other hand, the design problem often cannot be solved using LP directly; however, optimal solutions for large instances can still be found using the computationally more expensive ILP procedure. While different energy functions also affect the difficulty of the problem, the LP/ILP approach is able to find optimal solutions. Our analysis is the first large-scale demonstration that LP-based approaches are highly effective in finding optimal (and successive near-optimal) solutions for the side-chain positioning problem.