论文部分内容阅读
“海量”的生物数据为生命科学研究提供了广阔前景,同时也对现有的生物数据处理能力提出了严峻挑战。如何从浩如烟海的生物序列数据中挖掘出有价值的生物信息,以获取基因、蛋白质结构、功能和进化等理性知识是生物信息学研究的主要目的。多序列比对和系统发育分析是生物信息学的重要研究领域,而提高分歧较大序列的多序列比对准确率和重构合理的全基因组系统发育树是该领域的主要研究课题,本文对此进行了深入研究和探讨,主要研究成果如下: 本文深入、细致地研究了当今国际上各种多序列比对算法,系统地阐述了最具代表性的渐进比对算法ClustalW、T-Coffee和DiAlign,以及迭代比对算法Prrp、MultAlin和Muscle,并具体地分析了各算法的优缺点。 ClustalW是目前国际上使用最为广泛且有效的多序列比对程序,但存在着对分歧较大且进化距离非均匀的多序列比对准确率低的问题。针对上述问题,本文借鉴了MultAlign算法,综合了迭代比对和渐进比对策略的优点,提出了一种新的迭代渐进多序列比对算法IPMSA。并以国际通用的多序列比对基准数据库BAliBASE中一千多条蛋白质序列构成的142组参考多序列比对数据集为测试数据,将本算法同ClustalW和MulAlign进行了比较研究。研究结果表明,本算法能有效地提高多序列比对的准确性,其准确率分别比MultAlin和ClustalW高出19.6%和3.1%。 针对以往渐进比对算法中距离矩阵基于两序列比对来构建,而存在着无法反映序列间的结构信息差异,以及人为设定参数,难以客观、有效地反映序列间进化距离的问题,本文引入一种新的计算序列间进化距离的信息理论方法——FDOD方法。该方法通过序列中相邻子序列分布(完全信息集CIS)来描述序列,充分考虑到序列中相邻字符的相关性,从序列中可以提取有关组分以及结构等更多信息;同时,以子序列分布差异度量函数FDOD计算序列距离,该函数计算简单、快速,且不需要人为设置参数,因此,能够更客观、有效地计算序列间的进化距离。此外,利用动态规划比对算法计算距离矩阵的时间复杂度为O(N~2L~2),而利用信息差异度量函数计算距离矩阵的时间复杂度为O(N~2L),所以采用信息差异度量方法计算距离矩阵可以降低相应比对算法的时间复杂度。 本文首次将利用信息熵度量序列间进化距离的FDOD方法引入到多序列比对算法研究中,提出一种新的基于IPMSA和信息差异度量的多序列比对算法MSAID。该算法包含两部分:基于信息差异度量的渐进多序列比对算法MSAID-1和迭代渐进多序列比对算法MSAID。以基准多序列比对数据库BAliBASE中142组参考比对作为测试数据集,与当前国际上著名的多序列比对算法ClustalW、Dialign、Prrp、T-Coffee