论文部分内容阅读
随着被誉为人类科学“登月计划”的人类基因组项目的顺利完成,生命科学进入了一个崭新的时代--“后基因时代”。基因序列的获得一方面为人们理解生物体的奥秘提供了基础,但同时人们也发现单从基因序列的角度并不能完整系统的阐述生物功能。蛋白质是生命体构成的主要成分,同时也是生命活动的主要执行者,对于理解生物体的内在功能具有重要的指导意义。寻找蛋白质结构之间的相似性有利于让人们理解功能之间的相似性,发现远程的同源关系,甚至发现蛋白质结构的进化机制。因此,寻找蛋白质相似性的手段--蛋白质结构比对应运而生,并且发展为生物信息学不可或缺的一种工具。越来越多的蛋白质结构比对算法已经被提出,例如FATCAT,CE等。但是,许多蛋白质结构比对算法都是基于序列性限制的,并不能检测到由于循环置换或是不同祖先进而来的蛋白质结构之间的序列无关相似性。基于上述背景,本文简要的介绍了当前主流的七种序列无关蛋白质结构比对算法,并且提出了一种新的基于变长AFP的序列无关蛋白质结构比对算法。与其他基于AFP的蛋白质结构比对算法不同的是我们的算法采用的AFP是变长的,这样不仅可以更好的表征蛋白质局部结构,而且可以提高运算速率。此外,我们利用AFP的空间信息对AFP进行筛选,剔除含有噪声的AFP,从而获得高质量的AFP。我们将高质量的AFP之间的关系用图论的理论处理,并用这个图的一个优质的最大团来表示初始结构对齐。最后,为了避免动态规划算法在序列无关结构比对中的局限性,我们采用贪心算法对初始对齐进行优化并得到最终的比对结果。实验结果表明,与七种序列无关的蛋白质结构比算法相比,除了含柔性的序列无关结构比对算法DEDAL和考虑了反向对齐,Cα模型等多种情况的MIACN算法外,我们的算法能够更好地寻找蛋白质结构之间的序列无关相似性。此外,相对于基于定长AFP的结构比对算法,我们的算法采用变长的AFP使得算法在执行效率上有了很大的提升。