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

基于海明距离的DNA序列中相似性重复片段查找技术研究

作　者: 赵毅
导　师: 王国仁
学　校: 东北大学
专　业: 计算机系统结构
关键词: DNA序列 相似性串联重复片段 相似性反向重复片段 模式单元数组 边界索引
分类号: Q75
类　型: 硕士论文
年　份: 2008年
下　载: 38次
引　用: 0次
阅　读: 论文下载
 

内容摘要


生物信息学是随着人类基因组计划的启动、基因序列和蛋白质序列等生物数据迅猛增加而逐渐兴起的一门通过综合运用数学、计算机科学和信息科学来研究生物系统中信息现象的科学。在其广泛的研究领域中,重复片段查找是一个重要的DNA序列分析基础问题,其中的相似性重复片段查找因具有重要的生物意义以及其问题本身的复杂性,一直以来都是广大生物信息学研究人员致力研究的重要课题之一。本文针对DNA序列中两类重要的相似性重复片段——相似性串联重复片段和相似性反向重复片段的查找技术进行了深入研究,在分别为两类重复片段进行形式化定义之后,设计了相应的索引技术和查找算法用于两类相似性重复片段的查找和识别。在相似性串联重复片段查找的研究中,首先在海明距离的基础上定义了模式相似度和相邻相似度的概念用于衡量相似性串联重复片段模式间的相似程度,并提出了新的相似性串联重复片段定义Largest Neighbor-similarity-based Approximate Tandem Repeats (LNATR)。之后,通过将DNA序列划分为模式单元,设计了模式单元数组(Pattern Unit Array, PUA)的索引结构用于LNATR的查找。最后在模式单元数组上,根据后继信息进行模式连接以及模式增长,设计了一种基于模式单元数组的LNATR查找算法,并与Gad M. Landau等人提出的查找算法进行了比较。在相似性反向重复片段查找的研究中,首先在海明距离的基础上定义了匹配度用于衡量相似性反向重复片段模式间的匹配相似程度,并综合考虑了反向重复片段模式间可能存在间隔的特点,提出了新的相似性反向重复片段定义Largest Matching-degree-based Approximate Inverted Repeats (LMAIR)。之后设计了边界索引(Boundary Index, BI)的索引技术用于LMAIR的查找。最后在边界索引的基础上,分别设计了基本LMAIR查找算法和优化的LMAIR查找算法,并对两种算法进行了比较。

全文目录


摘要  5-6
ABSTRACT  6-9
第一章 绪论  9-19
  1.1 DNA序列中的重复片段  9-12
    1.1.1 DNA序列  10
    1.1.2 DNA序列中的重复片段  10-12
    1.1.3 DNA序列中重复片段的查找  12
  1.2 相似性串联重复片段查找相关研究  12-15
    1.2.1 Gad M. Landau查找算法  13-14
    1.2.2 Tandem Repeats Finder  14-15
  1.3 相似性反向重复片段查找相关研究  15-17
    1.3.1 Porto & Barbosa查找算法  15-16
    1.3.2 Inverted Repeats Finder  16-17
  1.4 本文研究工作  17-19
第二章 相似性串联重复片段查找研究  19-31
  2.1 相似性串联重复片段的定义  19-21
  2.2 模式单元数组  21-24
    2.2.1 模式单元数组结构  21-23
    2.2.2 模式单元数组的建立  23-24
  2.3 相似性串联重复片段LNATR查找算法  24-29
  2.4 本章小结  29-31
第三章 相似性反向重复片段查找研究  31-49
  3.1 相似性反向重复片段的定义  31-35
  3.2 反向重复片段索引技术  35-39
    3.2.1 边界索引结构  36-37
    3.2.2 边界索引的建立  37-39
  3.3 相似性反向重复片段LMAIR查找算法  39-47
    3.3.1 基本查找算法  39-42
    3.3.2 算法优化  42-47
  3.4 本章小结  47-49
第四章 实验与性能分析  49-61
  4.1 LNATR查找的实验与性能分析  49-53
    4.1.1 模式单元数组  49-50
    4.1.2 LNATR查找  50-53
  4.2 LMAIR查找的实验与性能分析  53-59
    4.2.1 边界索引  54
    4.2.2 LMAIR查找  54-59
  4.3 本章小结  59-61
第五章 结束语  61-63
参考文献  63-67
致谢  67-69
攻读硕士期间发表的论文  69

相似论文

  1. 五倍子蚜DNA序列分子系统发育关系,S899.4
  2. 东亚和北美五倍子蚜（半翅目：瘿绵蚜科）数值分类研究,S899.4
  3. 基于时间序列理论方法的流感病毒DNA序列特征分析,R346
  4. 线粒体DNA G3635A突变导致Leber遗传性视神经病变,R774.6
  5. X连锁视网膜劈裂症家系的基因诊断与分析,R774.1
  6. DNA序列的最大频繁模式挖掘,TP311.13
  7. 生物序列的图形表示及相似性分析,Q75
  8. 基于SVM分类机的DNA序列分类方法,TP18
  9. 智能化入侵防御系统实现的关键技术研究,TP393.08
  10. DNA序列选择进化距离及其在系统发育分析中的应用,Q523
  11. 利用20个微卫星DNA标记分析柬埔寨地方鸡群体的遗传多样性,S831.2
  12. 基于DNA序列的功能位点识别,Q523
  13. 犬猫带绦虫线粒体基因组学研究,S852.734
  14. 基于主成分分析法的人类启动子识别,R346
  15. 一株新型白腐菌产漆酶规律及其酶学性质的研究,TS745
  16. 先天性肾上腺皮质增生症CYP21A2基因诊断研究,R725.8
  17. 基于智能算法的DNA聚类研究及应用,TP18
  18. 基于DNA序列与多混沌映射的数字图像加密技术研究,TP309.7
  19. 基于图形表示的DNA相似性分析及进化树构建算法研究,TP391.41
  20. 鲤鱼白细胞介素-1β基因克隆、鉴定及时空转录分析,S941

中图分类: > 生物科学 > 分子生物学 > 分子遗传学
© 2012 www.xueweilunwen.com