A new algorithm for protein folding in the HP model
A new algorithm for protein folding in the HP model
复制标题
HP 模型中蛋白质折叠的新算法
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Alantha Newman
中科院分区：
文献类型：
--
作者：
Alantha Newman
我们在二维方格上的 HP 模型中考虑蛋白质折叠问题。这个问题在组合上相当于折叠一串0和1，使得该串在格子上形成自回避行走，并且相邻的1对的数量最大化。我们针对这个问题提出了一种线性时间 1/3 近似算法，改进了之前的最佳近似因子 1/4。该算法的近似保证基于 Hart 和 Istrail [6] 提出的上限，并在之前所有解决该问题的论文中使用。我们证明这个上限不能用于获得优于 1/2 的近似因子。
We consider the problem of protein folding in the HP model on the two-dimensional square lattice. This problem is combinatorially equivalent to folding a string of 0's and 1's so that the string forms a self-avoiding walk on the lattice and the number of adjacent pairs of 1's is maximized. We present a linear-time 1/3-approximation algorithm for this problem, improving on the previous best approximation factor of 1/4. The approximation guarantee of this algorithm is based on an upper bound presented by Hart and Istrail [6] and used in all previous papers that address this problem. We show that this upper bound cannot be used to obtain an approximation factor better than 1/2.