改进的自组织映射(SOM)蛋白质折叠算法和计算实现

蛋白质结构预测是生物信息学中的重要研究方向．为了研究蛋白质折叠的机理,人们引入了只考虑蛋白质疏水核心和亲水外围位置导致能量差别的简化HP模型．即使是求解二维HP模型已被证明是一个NP完全问题,因此需要设计有效的近似算法来求解较大规模的HP模型．从旅行商问题(TSP)的求解看,自组织映射是构造近似算法的有效工具．本文将归一化的F-W自组织模型应用到蛋白质二维HP问题的求解中,结合为克服多重映射构造的局部线搜索算法．数值试验表明,该算法改进了现有的HP模型的SOM求解算法, 只需很少的迭代步数就能找到最低能量构象．这一改进算法可以成为进一步研究的基础．

IMPROVED SELF-ORGANIZING MAP ALGORITHM FOR PROTEIN FOLDING AND ITS REALIZATION

Protein structure prediction is one of the main research topics in bioinformatics. A simple exact HP model is introduced in order to go deep into the principles of the protein folding, which only considers the energy difference caused by the hydrophobic core and polar periphery. It has been proved that this problem is NP-complete and the right way is looking for approximate solution. In this paper a normalized F-W SOM algorithm is constructed for the two dimensional HP model of protein folding, inspired by the efficient behavior of SOM in solving the classical Traveling Salesman Problem (TSP). Also a local search method is designed to overcome the multi-mapping phenomenon. Numerical results show that this algorithm improves the existed SOM algorithm for HP model and can find the minimum energy configuration in less iterations.