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

基于锚点的多基因组序列比对算法

作　者: 苗素超
导　师: 霍红卫
学　校: 西安电子科技大学
专　业: 计算机软件与理论
关键词: 多基因组序列比对保守区域后缀数组图论模型最长递增子序列
分类号: TP301.6
类　型: 硕士论文
年　份: 2010年
下　载: 7次
引　用: 0次
阅　读: 论文下载

内容摘要

多基因组序列比对是现代生物信息学研究领域非常重要的核心问题。为了能够比对多种近亲物种之间的多条基因组序列,我们迫切需要一种多基因组序列比对工具。当前基因组序列比对的研究主要集中于基因组双序列比对,而有效的多基因组序列比对算法只有少数几个,并且这些算法的比对效率较低。本文提出了一种有效的多基因组序列比对算法,该算法结合后缀数组及图模型,计算保守区域并使用现有序列比对工具完成多基因组序列比对。算法首先计算出序列之间的保守区域,然后基于图模型计算最大递增保守区域集,最后利用ClustalW比对方法来比对相邻保守区域之间的缝隙。在六组基因组(人类,老鼠,支原体等)DNA序列集上进行的序列比对实验表明,本文算法和MGA, EMAGEN等其他同类算法相比具有可比的精度,识别效率更高,时间开销更小,为解决多基因组序列比对问题提供了一个较好选择。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-13
  1.1 引言  7-8
  1.2 基因组序列比对的背景及现状  8-12
    1.2.1 基因组序列比对的生物学背景  8-10
    1.2.2 基因组序列比对现状  10-12
  1.3 本文的工作  12-13
第二章基因组序列比对研究现状  13-19
  2.1 基因组双序列比对算法  13-15
  2.2 多基因组序列比对算法  15-17
  2.3 本章小结  17-19
第三章基于锚点的多基因组序列比对策略  19-33
  3.1 锚点定位算法  19-23
  3.2 计算锚点的线性不交叉序列  23-29
    3.2.1 构造锚点关系图  24-26
    3.2.2 计算锚点关系图的最大独立集  26-29
  3.3 比对锚点之间片段  29-32
  3.4 本章小结  32-33
第四章多基因组序列比对算法设计  33-45
  4.1 计算基因组的MUM集合  33-38
    4.1.1 构造拼接序列的后缀数组  33-35
    4.1.2 计算LCP,PS,SO集合  35-37
    4.1.3 计算MUM区间  37-38
  4.2 构造MUM图  38-39
  4.3 计算LIS-MUMs  39-43
  4.4 多基因组序列比对算法的整体结构  43
  4.5 本章小结  43-45
第五章实验结果和性能分析  45-51
  5.1 参数设置  45
  5.2 实验结果  45-48
  5.3 性能分析  48-50
  5.4 本章小结  50-51
第六章结束语  51-53
致谢  53-55
参考文献  55-57

基于锚点的多基因组序列比对算法

内容摘要

全文目录

相似论文