论文题目: 生物信息学中多序列比对等算法的研究
论文类型: 博士论文
论文专业: 计算机应用
作者: 张敏
导师: 迟忠先
关键词: 生物信息学,多序列比对,渐进比对算法,迭代比对策略,函数,系统发育树
文献来源: 大连理工大学
发表年度: 2005
论文摘要: “海量”的生物数据为生命科学研究提供了广阔前景,同时也对现有的生物数据处理能力提出了严峻挑战。如何从浩如烟海的生物序列数据中挖掘出有价值的生物信息,以获取基因、蛋白质结构、功能和进化等理性知识是生物信息学研究的主要目的。多序列比对和系统发育分析是生物信息学的重要研究领域,而提高分歧较大序列的多序列比对准确率和重构合理的全基因组系统发育树是该领域的主要研究课题,本文对此进行了深入研究和探讨,主要研究成果如下: 本文深入、细致地研究了当今国际上各种多序列比对算法,系统地阐述了最具代表性的渐进比对算法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
论文目录:
第一章 绪论
§1.1 引言
§1.2 分子生物学概论
§1.2.1 核酸、蛋白质和遗传信息
§1.2.2 中心法则、遗传密码和变异
§1.2.3 系统发育分析
§1.3 序列比对方法及多序列比对算法研究进展
§1.3.1 渐进比对(Progressive alignment)算法
§1.3.2 迭代比对算法(Iterative alignment)
§1.4 国内研究现状
§1.5 本文主要研究内容及组织方式
第二章 迭代渐进多序列比对算法IPMSA
§2.1 概述
§2.2 ClustalW算法的优缺点
§2.3 一个新的迭代渐进多序列比对算法IPMSA
§2.4 多序列比对算法评价基准数据集BAliBASE以及评价标准
§2.4.1 多序列比对算法评价基准数据集BAliBASE
§2.4.2 多序列比对算法评价标准SPS、CS
§2.4.3 统计有效性(Statistical validation)
§2.5 与其它比对算法的比较研究
§2.6 在lidy上的应用
§2.7 本章小结
第三章 基于信息差异度量的多序列比对算法MASID
§3.1 引言
§3.2 信息差异度量方法
§3.2.1 完全信息集CIS
§3.2.2 FDOD函数
§3.2.3 蛋白质序列、比对序列的完全信息集以及FDOD函数在距离计算中的应用
§3.3 MSAID算法
§3.4 和其他多序列比对算法的比较研究
§3.5 比较结果
§3.5.1 MSAID-1与ClustalW的比较
§3.5.2 与类似的迭代渐进比对算法的比较
§3.5.3 与其他多序列比对方法的比较
§3.5.4 FDOD度量的有效性
§3.6 应用到1r69
§3.7 本章小结
第四章 重构全基因组系统发育树方法FNJ
§4.1 概述
§4.2 构建系统发育树的方法
§4.3 DNA序列之间距离的一种度量
§4.4 基于信息差异度量重构全基因组系统发育树方法FNJ
§4.5 FNJ方法在SARS冠状病毒与其他冠状病毒种系进化分析中的应用
§4.6 本章小结
第五章 生物信息学多序列比对算法研究系统
§5.1 系统目标及功能
§5.2 系统功能模块划分
§5.2.1 序列文件管理
§5.2.2 序列比对算法选择
§5.2.3 基于BAliBASE的算法评估
§5.2.4 重构系统发育树
§5.2.5 其他辅助功能
§5.3 本章小结
第六章 结论与展望
参考文献：
作者攻读博士学位期间参加的科研项目和发表的学术论文
学位论文创新点摘要
致谢
大连理工大学学位论文版权使用授权书
发布时间: 2005-09-07
相关论文
- [1].DNA序列及蛋白质序列的分析与比较[D]. 贺平安.大连理工大学2003