Branch-and Terminate: a combinatorial optimization algorithm for protein design
Branch-and Terminate: a combinatorial optimization algorithm for protein design
复制标题
DOI：
10.1016/s0969-2126(99)80176-2
复制
发表时间：
1999-09-15
期刊：
影响因子：
--
通讯作者：
Mayo, SL
中科院分区：
文献类型：
--
作者：
Gordon, DB;Mayo, SL
背景资料：一些确定性和随机组合优化算法已被应用于计算蛋白质设计和同源建模。随着结构目标的大小增加，但是，它已成为必要的，以找到更强大的方法来解决组合的复杂性增加。结果：我们提出了一种新的确定性组合搜索算法，称为“分支和终止”（B&T），这是来自分支和定界搜索方法。B&T方法是基于一个有效的，但非常严格的边界表达式，这是用于搜索的组合树表示的蛋白质系统的建设。边界表达式用于确定树的最佳组织，并执行一个高效的修剪程序命名为“终止”。对于某些计算，B&T方法可以与当前的确定性标准，死端消除（DEE）相媲美，有时找到解决方案的速度高达21倍。B&T算法的一个更显著的特点是，它可以提供一种有效的方法来完成优化的问题，已被部分减少的DEEalgorithm.Conclusions：B&T算法是一个有效的优化算法时，单独使用。此外，它可以通过完成达到DEE标准变得低效的点的DEE优化来增加氨基酸侧链放置计算（例如蛋白质设计）的问题大小限制。这两个算法一起使得有可能找到解决方案的问题，是棘手的任何算法单独。
Background: Several deterministic and stochastic combinatorial optimization algorithms have been applied to computational protein design and homology modeling. As structural targets increase in size, however, it has become necessary to find more powerful methods to address the increased combinatorial complexity.Results: We present a new deterministic combinatorial search algorithm called 'Branch-and-Terminate' (B&T), which is derived from the Branch-and-Bound search method. The B&T approach is based on the construction of an efficient but very restrictive bounding expression, which is used for the search of a combinatorial tree representing the protein system. The bounding expression is used both to determine the optimal organization of the tree and to perform a highly effective pruning procedure named 'termination'. For some calculations, the B&T method rivals the current deterministic standard, dead-end elimination (DEE), sometimes finding the solution up to 21 times faster. A more significant feature of the B&T algorithm is that it can provide an efficient way to complete the optimization of problems that have been partially reduced by a DEE algorithm.Conclusions: The B&T algorithm is an effective optimization algorithm when used alone. Moreover, it can increase the problem size limit of amino acid sidechain placement calculations, such as protein design, by completing DEE optimizations that reach a point at which the DEE criteria become inefficient. Together the two algorithms make it possible to find solutions to problems that are intractable by either algorithm alone.