论文摘要
遗传多态性检测是进行遗传多态性研究的关键环节。近年来,为降低检测成本,以计算手段为辅助的多态性检测已得到广泛应用,同时,在该研究领域中出现了一系列以提高检测效率和降低检测成本为目的的组合优化问题。本文主要研究个体单体型检测问题、基于连锁不平衡的多种群标签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引物设计提供了一种有效的解决方法。本文对遗传多态性检测中三类典型的组合优化问题进行研究,并提出了有效的求解算法。这些研究工作能有效地提高遗传多态性检测的工作效率,并降低其成本。
论文目录
相关论文文献
标签：遗传多态性论文; 组合优化论文; 单体型论文; 标签单核苷酸多态性论文; 引物集论文;