学位论文 > 优秀研究生学位论文题录展示
单体型组装加权最小字符翻转问题参数化算法研究
作 者: 周伟
导 师: 王建新
学 校: 中南大学
专 业: 计算机应用技术
关键词: 单核苷酸多态性 单体型 NP-难问题 参数化算法
分类号: TP301.6
类 型: 硕士论文
年 份: 2008年
下 载: 22次
引 用: 1次
阅 读: 论文下载
内容摘要
单体型检测在遗传病基因的定位、药理反应的研究、个体识别等方面有极其广阔的应用前景。但是在当前的实验技术下直接测定个体的单体型所需的时间和金钱上的花费过于昂贵,因此利用计算机技术来确定个体的单体型有极其重要的现实意义。单体型检测可分为两大类:单体型组装问题和单体型推断问题。本文主要对单体型组装问题相关模型和算法进行研究。由于单体型组装问题计算模型绝大部分是NP-hard,当片断数和SNP位点数较大时,基本上没有可行的精确算法,而诸如启发式算法、遗传算法等近似算法的近似程度很难保证,往往不能获得最优解。因而尽可能提高精确算法的时间和空间效率具有极其重要的现实意义。本文着重探索了如何利用小参数技术显著降低相关计算模型的时间和空间复杂度,并针对单体型组装加权最小字符翻转(WMLF)问题提出了一个时间复杂度为D(nk22k2+mlogm+mk1)的参数化算法,可以在较短的时间得到WMLF问题的精确解,具有良好的可扩展性和较高的实用价值。参数化算法是精确算法而且具有时空复杂度较低的特性,因此我们在现有实验条件下可利用参数化算法来比较不同计算模型的单体型重构精度。基于适用于不同模型的参数化算法,本文对MSR、MFR、MEC、WMLF、MEC/GI等单体型组装模型做了详细的分析比较,从而提出了一系列新的评价指标,然后采用真实和模拟的生物数据对相关模型进行大量实验,分析影响单体型重构精度的原因,从而为设计新的计算模型指明了思路。
|
全文目录
摘要 4-5 ABSTRACT 5-8 第一章 绪论 8-18 1.1 课题研究背景 8-16 1.1.1 单体型推断问题 10-11 1.1.2 单体型组装问题 11-15 1.1.3 单体型组装与推断两类问题比较 15-16 1.2 课题研究内容 16 1.3 论文组织 16-18 第二章 单体型组装问题计算模型的比较研究 18-25 2.1 单体型组装模型评价指标 18-19 2.2 实验分析 19-23 2.2.1 实验环境 19-20 2.2.2 实验结果 20-23 2.3 本章小结 23-25 第三章 单体型组装问题算法研究 25-39 3.1 启发式算法研究 25-27 3.1.1 遗传算法 25-26 3.1.2 动态聚类算法 26 3.1.3 基于统计的方法 26-27 3.1.4 其它启发式算法 27 3.2 精确算法研究 27-37 3.2.1 动态规划法 27-28 3.2.2 分支限界算法 28-29 3.2.3 参数化算法 29-37 3.3 启发式算法与精确算法的性能比较 37-38 3.4 本章小结 38-39 第四章 单体型组装加权最小字符翻转问题参数化算法研究 39-48 4.1 WMLF问题的整数规划模型 39-40 4.2 WMLF问题相关研究 40-42 4.2.1 动态聚类算法的基本思想 40-41 4.2.2 动态聚类算法描述 41-42 4.3 WMLF问题参数化算法研究 42-45 4.4 实验分析 45-47 4.5 本章小结 47-48 第五章 结束语 48-50 5.1 研究工作总结 48-49 5.2 进一步研究工作展望 49-50 参考文献 50-55 致谢 55-56 研究成果 56
|
相似论文
- 鸡CFL2基因遗传变异及其效应与表达的研究,S831
- 水稻胁迫应答基因3’UTR模体及相关miRNA的生物信息学研究,Q943.2
- 家畜布鲁氏菌病流行病学调查及布鲁氏菌单核苷酸多态性分子分型研究,S855.12
- 心脏离子通道SCN5A基因和minK基因多态性与房颤的关联性研究,R541.75
- 急性白血病儿童还原型叶酸载体基因多态性研究,R733.71
- 年龄相关性皮质性白内障波形蛋白基因外显子和启动子的研究,R776.1
- 4号染色体上四个SNP位点与高度近视的关联性分析,R778.11
- 尼古丁乙酰胆碱受体基因多态性与焦炉工DNA损伤的关联性研究,R131
- NPPA基因多态性与中国汉族人群心房颤动的关联分析,R541.75
- CD226基因多态性与系统性红斑狼疮相关性研究,R593.241
- 上皮钙粘蛋白启动子-160 C/A位点多态性与鼻咽癌危险性分析,R739.63
- XPA、XPC和XRCC1基因多态性与非小细胞肺癌铂类化疗患者预后的关系,R734.2
- 华南汉族人群中MAFB、IRF6、8q24和10q25多态性与非综合征性唇腭裂的关联,R782.2
- 新疆维吾尔族、汉族CD14基因多态性与变应性鼻炎的关联研究,R765.21
- XRCC1基因单核苷酸多态性与汉族、维吾尔族乳腺癌临床病理参数的研究,R737.9
- cPLA2基因多态性与中国湖南汉族人群阿尔茨海默病的相关性研究,R749.16
- miRNA-146a和EPHX2基因多态性与长沙地区汉族人群缺血性脑卒中遗传易感性的关联研究,R743.3
- Clock基因T3111C和T257G多态性与湖南地区汉族人群睡眠癫痫的相关性研究,R742.1
- BST1基因rs4698412多态性与散发性帕金森病关联研究,R742.5
- 儿童糖尿病易感基因的相关研究,R725.8
- 儿童哮喘危险因素和TIM基因多态性研究,R725.6
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 一般性问题 > 理论、方法 > 算法理论
© 2012 www.xueweilunwen.com
|