论文摘要
研究背景近年来,生物信息学获得了飞速的发展。生物信息学用数学,计算机等理论、方法和技术,研究生物大分子,主要包括脱氧核糖核酸(DNA)和蛋白质(Protein)的序列、结构和功能。蛋白质在生物活动进程中起着重要作用。分析蛋白质的功能是生物学中一个核心问题。蛋白质的功能不仅决定于蛋白质的一级结构,而且与其特定的空间结构密切相关。在现有的生物技术条件下,蛋白质序列(一级结构)可以通过基因测序获得。但是,测定蛋白质的三维结构需要花费大量的时间和费用。因此,通过蛋白质序列(一级结构)来推测蛋白质的功能和对蛋白质进行分类具有重要的理论和实用价值。随着基因组计划的实施,DNA序列和蛋白质序列数据激增。通过在生物数据库中寻找同源蛋白质来推测蛋白质的功能和对蛋白质进行分类成为一种有效的方法。本文对这一问题进行研究。染色体组重组问题是在计算生物学中的一个重要问题。染色体组的重组是微生物,植物,动物进化的一种重要模式。虽然染色体组的重组过程十分复杂,但是也存在几种基本操作。在变异的过程中,染色体组的基因序列主要进行几种主要的变换:反转,移位和转位。生物物种之间的进化实际上就是生物基因的变异过程,计算基因序列之间变换距离的问题称为染色体组排序问题。本文对其中的染色体组的移位距离进行了研究。方法序列比对与模体(motif)识别是进行生物序列分析的两个重要方法。具有相似氨基酸序列的蛋白质通常会具有相似的功能。对于一个新的蛋白质序列,我们可以在其中寻找和其他蛋白质相似的子序列,并可以根据已知的相似蛋白质的功能来推测新的蛋白质的功能并对其进行分类。由于DNA序列和蛋白质序列的数据量巨大,快速有效的计算机算法成为在大量的数据中寻找有用信息的关键。本论文主要针对多序列比对问题和模体识别问题进行了方法上的研究。我们提出了一种新的算法来对一组蛋白质序列进行局部比对,并找到相应的模体(motif)。我们的算法(PSEM)使用了两个技术:随机的模体种子的选取和EM优化方法。对于有向染色体组的移位距离问题,我们分析了其中断点图的特性,并且找到了改进原有算法的方法。算法改进的关键是在引入了长圈的分裂以及集合的寻找和合并算法。结果我们从Pfam蛋白质家族数据库中提取了100组同属一个蛋白质家族的蛋白质序列。实验结果显示,PSEM算法在每组蛋白质序列中都找到了高质量的的模体。利用找到的模体,我们进行了对新的蛋白质序列进行分类的测试。实验结果表明,该方法对蛋白质序列进行分类具有很高的准确性。对有向染色体组的移位距离问题,本文给出了一个O(nlog*n)改进算法,改进了以前的O(n~2)算法。结论本文主要研究如何通过蛋白质序列寻找同源蛋白质来推测蛋白质的功能和对蛋白质进行分类。我们提出了一个新的PSEM算法来寻找一组蛋白质序列中的模体并用得到的模体对蛋白质序列进行分类。实验结果表明PSEM算法可以找到高质量的模体,而且利用得到的模体可以对蛋白质序列进行准确的分类。因此,PSEM算法是一个有效的蛋白质序列的分析方法。有向染色体组的移位距离问题的快速算法也为染色体组的重组距离问题提供了新的计算方法。