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

遗传多态性检测中组合优化问题的研究

作　者: 吴璟莉
导　师: 陈建二；王建新
学　校: 中南大学
专　业: 计算机应用技术
关键词: 遗传多态性组合优化单体型标签单核苷酸多态性引物集
分类号: TP399-C8
类　型: 博士论文
年　份: 2008年
下　载: 95次
引　用: 0次
阅　读: 论文下载

内容摘要

遗传多态性检测是进行遗传多态性研究的关键环节。近年来,为降低检测成本,以计算手段为辅助的多态性检测已得到广泛应用,同时,在该研究领域中出现了一系列以提高检测效率和降低检测成本为目的的组合优化问题。本文主要研究个体单体型检测问题、基于连锁不平衡的多种群标签SNPs选择问题及多元聚合酶链反应引物集设计问题。本文针对个体单体型检测问题的带权最少字符修改模型,提出一种启发式算法HAW。该算法先对每条SNP片段计算其全局兼容集,再选出包含片段数最多且交集为空的两个全局兼容集以生成一对初始单体型,最后通过剩余片段对其扩充完成重建。大量实验结果表明HAW算法能快速求解该模型,并获得较目前求解该模型的算法更高的单体型重建率。针对个体单体型检测问题的最少片段删除模型,本文提出一种粒子群优化算法PSO-MFR。该算法利用二进制编码粒子,并重新定义了粒子位置和速度之间的运算操作。由于利用了SNP位点杂合率较低的特性,该算法所引入的编码方式较短,能产生一个较小的解空间,从而快速地获得好的结果。实验结果表明,PSO-MFR算法是一种求解该模型的有效方法,能在较短时间内获得较高的单体型重建率,并得到较Fast Hare算法更高的重建率。针对个体单体型检测问题的最少错误更正模型,本文深入分析了以往算法在求解该问题时遗失最优解的原因,提出一种生成小规模优化解集合的新研究思路。通过引入较短的染色体编码方式和一种利用片段信息来修正染色体的重组算子,提出求解最少错误更正模型的单亲遗传算法PGA-MEC。实验结果表明PGA-MEC算法能有效求解该模型,在更短的运行时间内获得较以往求解该模型的算法更高的单体型重建率。进一步,将优化解集合的思想运用于PGA-MEC算法,提出IPGA-MEC算法。实验结果显示优化解集合的引入能有效避免最优解的遗失,从而进一步提高单体型的重建率。针对基于连锁不平衡的多种群标签SNPs选择问题,给出其形式化描述,并通过对集合覆盖问题在多项式时间内的归约证明其是NP-难的。进一步,本文提出一种求解该问题的贪婪算法MP-Tagging,该算法在每次迭代过程中选择1个或2个标签SNPs。实验结果表明MP-Tagging算法能有效求解该问题,并能够找到较以往算法更少的标签SNPs。针对多元聚合酶链反应引物集设计问题,提出一种多约束最小引物集选择问题的数学模型。针对该模型,本文提出贪婪算法MG,并基于MG算法设计一种新颖的重组算子,从而给出求解该模型的单亲遗传算法MG-PGA。实验结果表明MG-PGA算法在满足多约束条件下能获得较以往求解算法更小的引物集,为MP-PCR引物设计提供了一种有效的解决方法。本文对遗传多态性检测中三类典型的组合优化问题进行研究,并提出了有效的求解算法。这些研究工作能有效地提高遗传多态性检测的工作效率,并降低其成本。

全文目录

摘要  4-6
ABSTRACT  6-11
第一章绪论  11-34
  1.1 研究背景  11-12
  1.2 遗传和变异的相关知识  12-21
    1.2.1 遗传的物质基础及遗传法则  12-16
    1.2.2 可遗传的变异  16-19
    1.2.3 遗传多态性检测中的基因扩增技术  19-21
  1.3 遗传多态性检测中的组合优化问题  21-31
    1.3.1 个体单体型检测问题  22-27
    1.3.2 基于连锁不平衡的多种群标签SNPs选择问题  27-29
    1.3.3 多元聚合酶链反应引物集设计问题  29-31
  1.4 论文主要研究内容  31-33
  1.5 论文结构安排  33-34
第二章个体单体型检测问题的WMLF模型和算法  34-49
  2.1 基本概念  34-37
  2.2 定义和记号  37-39
  2.3 HAW算法  39-42
  2.4 实验结果与分析  42-48
    2.4.1 实验数据  42-43
    2.4.2 实验结果与性能分析  43-48
  2.5 本章小结  48-49
第三章个体单体型检测问题的MFR模型和算法  49-61
  3.1 定义和记号  49-50
  3.2 粒子群优化算法简介  50-51
  3.3 PSO-MFR算法  51-55
  3.4 实验结果与分析  55-60
  3.5 本章小结  60-61
第四章基于优化解集合求解个体单体型检测问题  61-76
  4.1 优化解集合  62-63
  4.2 单亲遗传算法简介  63-64
  4.3 PGA-MEC算法  64-68
  4.4 IPGA-MEC算法  68-69
  4.5 实验结果与分析  69-74
  4.6 本章小结  74-76
第五章基于连锁不平衡的多种群标签SNPs选择问题  76-88
  5.1 基本概念  76-77
  5.2 定义和记号  77-80
  5.3 MP-Tagging算法  80-84
  5.4 实验结果与分析  84-86
    5.4.1 实验数据  84
    5.4.2 实验结果与性能分析  84-86
  5.5 本章小结  86-88
第六章多元聚合酶链反应引物集设计问题  88-102
  6.1 基本概念  88-90
  6.2 定义和记号  90-92
  6.3 一种求解MPSSPMC模型的单亲遗传算法  92-97
    6.3.1 MG算法  92-95
    6.3.2 MG-PGA算法  95-97
  6.4 实验结果与分析  97-101
    6.4.1 实验数据  97-98
    6.4.2 实验结果与性能分析  98-101
  6.5 本章小结  101-102
第七章总结  102-105
  7.1 工作总结  102-103
  7.2 研究展望  103-105
参考文献  105-116
致谢  116-117
攻读博士学位期间主要的研究成果  117-118

遗传多态性检测中组合优化问题的研究

内容摘要

全文目录

相似论文