单体型组装加权最小字符翻转问题参数化算法研究

论文摘要

单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。但是在当前的实验技术下直接测定个体的单体型所需的时间和金钱上的花费过于昂贵,因此利用计算机技术来确定个体的单体型有极其重要的现实意义。单体型检测可分为两大类:单体型组装问题和单体型推断问题。本文主要对单体型组装问题相关模型和算法进行研究。由于单体型组装问题计算模型绝大部分是NP-hard,当片断数和SNP位点数较大时,基本上没有可行的精确算法,而诸如启发式算法、遗传算法等近似算法的近似程度很难保证,往往不能获得最优解。因而尽可能提高精确算法的时间和空间效率具有极其重要的现实意义。本文着重探索了如何利用小参数技术显著降低相关计算模型的时间和空间复杂度,并针对单体型组装加权最小字符翻转（WMLF）问题提出了一个时间复杂度为D(nk22k2+mlogm+mk1)的参数化算法,可以在较短的时间得到WMLF问题的精确解,具有良好的可扩展性和较高的实用价值。参数化算法是精确算法而且具有时空复杂度较低的特性,因此我们在现有实验条件下可利用参数化算法来比较不同计算模型的单体型重构精度。基于适用于不同模型的参数化算法,本文对MSR、MFR、MEC、WMLF、MEC/GI等单体型组装模型做了详细的分析比较,从而提出了一系列新的评价指标,然后采用真实和模拟的生物数据对相关模型进行大量实验,分析影响单体型重构精度的原因,从而为设计新的计算模型指明了思路。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 单体型推断问题
• 1.1.2 单体型组装问题
• 1.1.3 单体型组装与推断两类问题比较
• 1.2 课题研究内容
• 1.3 论文组织
• 第二章 单体型组装问题计算模型的比较研究
• 2.1 单体型组装模型评价指标
• 2.2 实验分析
• 2.2.1 实验环境
• 2.2.2 实验结果
• 2.3 本章小结
• 第三章 单体型组装问题算法研究
• 3.1 启发式算法研究
• 3.1.1 遗传算法
• 3.1.2 动态聚类算法
• 3.1.3 基于统计的方法
• 3.1.4 其它启发式算法
• 3.2 精确算法研究
• 3.2.1 动态规划法
• 3.2.2 分支限界算法
• 3.2.3 参数化算法
• 3.3 启发式算法与精确算法的性能比较
• 3.4 本章小结
• 第四章 单体型组装加权最小字符翻转问题参数化算法研究
• 4.1 WMLF问题的整数规划模型
• 4.2 WMLF问题相关研究
• 4.2.1 动态聚类算法的基本思想
• 4.2.2 动态聚类算法描述
• 4.3 WMLF问题参数化算法研究
• 4.4 实验分析
• 4.5 本章小结
• 第五章 结束语
• 5.1 研究工作总结
• 5.2 进一步研究工作展望
• 参考文献
• 致谢
• 研究成果