求解蛋白质折叠问题的拟物拟人算法

摘要

蛋白质所具有的生物学功能取决于蛋白质的空间折叠结构，研究蛋白质的空间结构在生物学领域具有重要意义。Anfinsen等人的研究工作表明，给定蛋白质一级结构序列，利用理论计算对蛋白质结构进行预测是一个可行的方法。由于蛋白质折叠问题的复杂度太高，理论界提出了一些简化模型。其中，Dill等提出的HP模型和Stillinger提出的AB模型最受欢迎，研究也最为广泛。基于HP模型和AB模型的蛋白质折叠问题都已被证明是NP完全问题，这意味着不存在既完整严格又不是太慢的求解算法。为了满足实际需要，人们于是着手研究非绝对完整但是是快速实用的启发式算法。沿着拟物拟人的工作途径，分别对基于HP模型和AB模型的蛋白质折叠问题的高效求解进行了研究。
　　 本研究给出了一种带随机策略的剪枝算法来求解基于二维HP模型的蛋白质折叠问题。在算法中，保留那些前景好的结点，并允许它以一定概率向下分支，而那些前景不太好的结点则以一定概率被删除，其下相连的分支也被“剪掉”。这样减小了搜索空间，使得相应的搜索时间也大大降低。基于裁剪复制策略的PERM (pruned-enriched Rosenbluth method)算法是一种链生长算法，它通过制定一定的评判准则，让有前途的个体得以繁衍，而不具备发展潜力的个体停止繁殖，从而减少了搜索树的分支数。通过分析PERM算法，指出了影响PERM算法效率的关键，并从拟人思想的角度对PERM算法做出了进一步的分析：PERM算法实际上可以理解为一种人口控制策略，通过对社会中的个体给出评价，然后给出个体的生育指标，从而实现“优生优育”。在这样一个生动形象的背景的指导下，提出了更为合理和有效的评判准则，从而得到了一种改进的PERM算法。计算结果表明改进的PERM算法在求解基于HP模型的蛋白质折叠问题时表现出非常高的效率。通过拟物思想，引入引力势能和斥力势能，建立了一个启发式的引导函数，把基于三维HP模型的蛋白质折叠问题由一个约束优化问题转化为无约束优化问题，然后给出了一个基于局部搜索策略的启发式算法。
　　 本研究为基于三维AB模型的蛋白质折叠问题找到了一个贴切的物理模型，该物理模型是一个力学系统。将氨基酸单体看作弹性小球，想象在蛋白质链上相邻两球球心之间连接着一根长度为1的弹簧。这样，系统能量中除了Lennard-Jones势能、弯曲势能和扭转势能外，还有弹簧势能。弹簧势能相当于一个罚函数，它是“松弛”约束条件的关键，把基于三维AB模型的蛋白质折叠问题由一个约束优化问题转化为无约束的优化问题。对此无约束优化问题，给出了一个梯度算法，并设计了一个产生初始构形的启发式策略。在用梯度法求解的过程中，计算很容易落入局部极小值的陷阱。为了跳出局部极小值陷阱，让计算走向前景更好的区域中去，在拟物算法的基础上，分别与模拟退火算法和禁忌搜索算法相结合，得到了效率更高的、具有全局优化能力的混合算法。尤其值得指出的是，以ELP(energy landscape paving minimizer)算法得到的结果构形作为拟物算法的初始构形，对于文献中的绝大多数算例，拟人算法都找到了当今国际学术界最好的构形，这种构形比文献中报道的构形具有更低的势能。以上研究工作表明，通过对物理世界中物质运动的演化规律和人类的社会经验进行抽象和形式化，可以启发人们为蛋白质折叠问题设计出高效的求解算法。在以后的研究工作中，我们将沿着拟物拟人的思路继续为基于其它模型的蛋白质折叠问题和其它NP完全问题寻求高效的求解算法。