基于图的标志SNP位点选择算法研究

论文摘要

单核苷酸多态性(Single Nucleotide Polymorphism,SNP)是指在基因组水平上由单个核苷酸变异所引起的DNA序列的多态性。在各类单体型中,少部分SNP位点包含绝大部分的遗传变异信息,这些位点称为标志SNP位点(TagSNP或htSNP)。通过生物实验从基因型序列中获取确定的单体型序列,即单体分型(Haplotyping)可以得到比较精确、可靠的结果。然而,代价高昂,难以满足当前海量生物数据分析。因此,借助数学和计算机结合的计算分子生物学手段寻找TagSNP位点,是解决单体分型问题的一个有效途径。本文对TagSNP位点选择问题进行了详细的阐述,并在充分研究和分析当前SNP位点选择算法的基础上,创新性地提出了基于图的TagSNP位点选择算法MDStagger,有效的提高了预测精确度,缩短了算法的运行时间。具体地,本文的主要研究内容和创新点如下:第一,描述了TagSNP位点的选择问题,包括解决该问题的数学模型和算法思想。同时,本文还分析了这些算法的优缺点及各自适用的范围。第二,提出了基于图的TagSNP位点选择算法MDStagger。文中阐述了图模型的构建法则以及将SNP位点的信息转化为最大密度子图的思想。重点描述了通过最大密度子图来寻找TagSNP位点的思想。实验表明,该算法能够避免因为随机算法带来的局部最优问题和枚举法产生的高时间复杂度等问题,与当前主要的TagSNP位点选择算法相比较,具有较优性能。第三,提出了一种改进的精确度预测方法,该方法基于多TagSNP位点联合预测非TagSNP位点。实验表明,多TagSNP位点联合预测比单一TagSNP位点预测,能够得到更高的精确度。该预测方法不仅提高了精确度,同时也为SNP位点评价准则的改进以及缺失位点的预测指明了一个新的方向。第四,实现了TagSNP位点选择算法及其精确度预测系统。该系统使用了文中提出的基于图的选择算法。该系统的数据预处理模块也适用于其它TagSNP位点选择算法的前期数据处理。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.1.1 TagSNP位点选择的意义
• 1.1.2 课题来源
• 1.2 国内外研究现状
• 1.2.1 问题的数学描述
• 1.2.2 基于LD的方法
• 1.2.3 基于block的方法
• 1.2.4 基于预测精度的方法
• 1.3 本文的主要研究内容
• 1.4 本文的组织结构
• 第2章 基于图的TagSNP位点选择方法
• 2.1 引言
• 2.2 数据预处理
• 2.2.1 删除冗余SNP位点
• 2.2.2 SNP位点聚类
• 2.3 基于图的TagSNP位点选择
• 2.3.1 图模型的构建
• 2.3.2 TagSNP位点选择
• 2.4 本章小结
• 第3章 精确度预测方法的研究
• 3.1 引言
• 3.2 算法评价准则
• 3.3 实验结果与分析
• 3.3.1 不同数据集的实验对比
• 3.3.2 相同数据集的实验对比
• 3.4 精确度预测方法的改进
• 3.4.1 多TagSNP联合预测精确度
• 3.4.2 精确度预测方法改进前后的实验对比
• 3.5 本章小结
• 第4章 系统平台
• 4.1 引言
• 4.2 系统实现所用技术
• 4.3 系统功能模块
• 4.3.1 删除冗余SNP位点模块
• 4.3.2 聚类模块
• 4.3.3 TagSNP位点选择模块
• 4.3.4 精确度预测模块
• 4.3.5 系统功能模块小结
• 4.4 数据处理流程
• 4.5 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢