学位论文 > 优秀研究生学位论文题录展示

基于序列两两比较的进化树构造方法研究

作　者: 王方圆
导　师: 李玉鑑
学　校: 北京工业大学
专　业: 计算机应用技术
关键词: 进化树 归一化编辑距离 分块递归 时间复杂度 空间复杂度
分类号: TP301.6
类　型: 硕士论文
年　份: 2008年
下　载: 216次
引　用: 3次
阅　读: 论文下载
 

内容摘要


系统进化分析是生物信息学中的重要研究领域,它的主要研究手段是从一组同源的DNA或蛋白质序列出发,计算各个序列之间的进化距离,进而构建反映物种进化关系的进化树。构建进化树的方法主要分为三类,即距离法、简约法和似然法。本文将对距离法做一些探索性的改进研究。传统的距离法一般通过多序列比对计算距离矩阵,而多序列比对是一个NP难问题,在序列数目较多时难以获得最优比对结果。一种解决方法是采用启发式的多序列比对算法,另一种方法是通过计算某种序列之间的两两距离代替多序列比对。对于计算两两距离的方法而言,Hansan H.Out和Khalid Sayood提出了一种基于LZ复杂度的距离,能够正确地重构某些进化树。本文则试图通过利用一种满足三角不等式的归一化编辑距离来绕过多序列比对的困难,但仍然需要对序列进行两两比对分析。序列的两两比对通常采用Needle-Wunschman算法,其时间和空间复杂度均为O（mn） （m, n为比对两序列的长度）,对长序列容易超过计算机的内存限制。Hirschberg算法具有线性空间复杂度,可以用来解决Needle-Wunschman算法的内存问题,但是计算时间需求要多一倍,约为O（ ）。本文试图在时间和空间复杂度之间进行折衷,通过引入一种新的检查点（CheckPoint）计算方法,提出了基于分块递归的序列比对算法。理论分析表明,该算法的空间需求大约在到O（5（m+n） + Ls×min（ m - 1, n - 1） + C2）O （5（ m + n ） + Ls×（ m + n - 2） + C2）之间,时间需求介于O（1.5mn）到O （3m n ）之间,但在序列相似度较高时介于O（1.5mn ）到O （2 mn）之间。同源物种的线粒体全基因组序列比对实验进一步证明了新算法的正确性,表明在序列之间的归一化编辑距离小于0.25时,新算法能够比Hirschberg算法快10%以上。因此分块递归序列比对算法在诸如同源序列分析、系统进化树构造等领域具有一定的应用价值。由于直接通过序列比对得到的距离易受序列长度影响,与真实进化距离的差别较大,因此需要进行归一化处理才能减小序列长度对构建进化树的影响。本文采用的归一化编辑距离是一种取值介于[0,1]之间的度量,由于能够完全满足三角不等式,所以还可以避免某些与进化树相关的负枝长问题。最后,本文通过两组实验说明了这种归一化编辑距离能够用来成功地构建某些已经被多种方法验证过的进化树。

全文目录


摘要  3-4
Abstract  4-8
第1章 绪论  8-16
  1.1 课题背景  8-9
  1.2 国内外研究概况  9-14
    1.2.1 距离度量标准  10
    1.2.2 序列比对算法  10-11
    1.2.3 建树方法  11-14
  1.3 本文的主要研究工作  14-15
  1.4 文章结构  15-16
第2章 进化距离度量  16-22
  2.1 距离度量的定义和基本性质  16-17
  2.2 常用距离度量简介  17-18
  2.3 编辑距离  18-20
    2.3.1 编辑距离  18-19
    2.3.2 归一化编辑距离  19-20
  2.4 距离和相似度  20-21
  2.5 本章小结  21-22
第3章 序列比对算法  22-31
  3.1 罚分模型和打分矩阵  22-24
    3.1.1 空位罚分模型  22-23
    3.1.2 打分矩阵模型  23-24
  3.2 两序列比对算法简介  24-28
    3.2.1 动态规划算法思想  25
    3.2.2 两序列全局比对算法  25-27
    3.2.3 两序列局部比对算法  27-28
  3.3 多序列比对算法简介  28-30
    3.3.1 基本的多序列比对算法  28
    3.3.2 CLUSTALW多序列比对算法  28-30
  3.4 本章小结  30-31
第4章 基于分块递归的序列比对算法  31-47
  4.1 Hirschberg算法简介  31-34
    4.1.1 Hirschberg算法B  31-32
    4.1.2 Hirschberg算法C  32-34
  4.2 K-Band算法简介  34-36
  4.3 分块递归序列比对算法  36-43
    4.3.1 分块递归序列比对算法A  36-37
    4.3.2 分块递归序列比对算法B  37-43
  4.4 实验数据与结果分析  43-46
    4.4.1 人造伪序列数据比对实验  43-44
    4.4.2 七条同源线粒体全基因组序列数据比对实验  44-46
    4.4.3 实验结果分析  46
  4.5 本章小结  46-47
第5章 基于归一化编辑距离的进化树构建方法  47-62
  5.1 距离法简介  47-51
    5.1.1 不加权算术平均组对法  48-50
    5.1.2 邻接法  50-51
  5.2 基于归一化编辑距离的系统进化树构建方法  51-56
    5.2.1 基于归一化编辑距离构建进化树的步骤  51-54
    5.2.2 Multi-Tree分子进化分析软件的完善  54-56
  5.3 实验数据与结果分析  56-60
    5.3.1 十一种脊椎动物序列数据的实验  56-57
    5.3.2 二十种有胚胎哺乳动物序列数据的实验  57-60
    5.3.3 实验结果分析  60
  5.4 本章小结  60-62
结论  62-64
参考文献  64-68
攻读硕士学位期间发表的学术论文  68-70
致谢  70

相似论文

  1. 鸡传染性支气管炎病毒河南地方株分离鉴定及HN104株与HN091株全基因组序列测定,S852.65
  2. 新疆加工番茄抗黄瓜花叶病毒转基因技术的研究,Q943.2
  3. 多视点立体视频编解码算法的研究与应用,TN919.81
  4. 多重幻方的构造与若干问题研究,O157
  5. 杨树与玉米细胞周期蛋白基因家族全基因组研究,S513
  6. 无线传感器网络中的K覆盖问题,TN929.5
  7. 基于泛化竞争和局部渗透机制自组织网TSP问题的算法分析与研究,TP301.6
  8. 网络编码在传输层的应用研究,TN915.01
  9. 牛病毒性腹泻病毒非结构蛋白NS3 B细胞线性表位的鉴定,S852.65
  10. 计算生物学中有关基因组移位—删除排序问题的研究,Q75
  11. DNA序列选择进化距离及其在系统发育分析中的应用,Q523
  12. 基于块Broyden方法的并行预处理技术的研究,O241.7
  13. P2P网络深度包业务识别（DPI）方法的改进,TP393.02
  14. 禽传染性支气管炎病毒Sczy3株全基因组序列测定分析,S852.659.2
  15. 基于信息熵理论的基因组特性研究,O236
  16. 湘琼两地蝙蝠携带星状病毒与诺如病毒的调查研究,R373
  17. 基于16S rDNA-RFLP技术对圈养成年大熊猫秋季肠道菌群多样性的研究,S865
  18. 猪繁殖与呼吸综合征病毒分子流行病学调查及NSP2、ORF5基因的遗传变异分析,S858.28
  19. 低毒力病毒CHV1（Cryphonectria hypovirus 1）5’-端3个基因的克隆及板栗疫病生物防治,S436.64
  20. 基于微粒群的LTE-Advanced通信系统自适应资源分配算法,TN929.5
  21. 用于异常检测的进化非选择算法性能分析,TP18

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com