基于多位点连锁不平衡度量的标签SNP选择方法研究

摘要

基因组上由于单个核苷酸变异所导致的序列多态性被称为单核苷酸多态性（Single Nucleotide Polymorphism，SNP）。研究发现，在不同样本之间可以通过使用少量的SNP位点即可以表示整个样本主要的遗传信息，而这些SNP位点被称为标签SNP(tag SNP)。通过基因型序列确定其对应的单体型序列过程被称为单体分型(Haplotyping)。虽然生物实验可得到更为精确、可靠的单体分型结果，但是该过程代价高昂，难以满足实时分析大规模生物数据的需求。因此，利用生物信息学方法选择标签SNP位点，然后在标签位点上开展单体分析，可以大大降低代价，并可靠地保留原始序列的变异信息。
　　从包含几十万个SNP的基因组中选择标签SNP被证实为NP难问题。目前，已有一些方法被用于标签SNP选择。但是，它们仍存在时间复杂度高、标签SNP数目多以及样本重构准确度偏低等不足。针对这些不足，本文设计了一种基于多位点连锁不平衡度量的标签SNP选择方法。本文主要的工作如下:
　　第一:结合现有文献，更为系统地描述了标签SNP选择问题，并比较分析当前基于不同思路的方法特点，然后详细阐述基于样本重构策略的基本步骤。
　　第二:在候选子集构造阶段，本文主要创新工作在于结合SNP数据生物含义，将经典的蚁群算法用于子集构造。该过程中，为了有效降低算法的计算复杂度，本文以多位点连锁不平衡度量为优化目标，利用蚁群算法的寻找近优解，其中工作内容包括设计启发函数及路径选择算子等，以提高算法性能。
　　第三:在标签子集精选阶段，我们提出后向删除算法用于标签SNP子集精选。该过程以样本重构的准确度为目标，采用后向淘汰策略选择具有最优分类准确度的标签SNP子集，该过程的主要目的是进一步提高重构准确率及降低标签SNP的数量。
　　第四:为了验证本文改进方法的有效性，我们基于C++语言设计实现了该改进算法。然后在多个真实数据集上进行了比较实验，采用的评价指标有重构准确度、运行时间上以及标签SNP数量，实验结果表明，本文方法具备较优性能。

目录

声明

摘要

插图索引

附表索引

1 绪论

1．1 引言

1．2 研究背景及意义

1．3 国内外研究现状

1．3．1 基于单体型覆盖率的方法

1．3．2 基于样本重构的方法

1．4 本文的技术路线及研究内容

1．5 本文结构安排

2 标签SNP选择方法介绍

2．1 单体型与复杂疾病

2．2 基于样本重构的标签SNP选择问题模型

2．3 标签SNP子集构造方法

2．3．1 贪心算法

2．3．2 动态规划算法

2．3．3 遗传算法

2．3．4 粒子群算法

2．4 样本重构方法

2．4．1 多元线性回归

2．4．2 人工神经网络

2．5 小结

3 基于连锁不平衡的标签SNP选择方法研究

3．1 连锁不平衡

3．2 SNP数据预处理

3．3 基于蚁群算法的候选标签子集构造

3．3．1 蚁群算法基本原理

3．3．2 路径选择函数

3．3．3 启发式函数

3．3．4 蚁群算法构造标签SNP子集的伪代码

3．4 基于后向淘汰的标签SNP精选

3．4．1 启发式特征后向淘汰算法

3．4．2 基于支持向量机的样本重构

3．4．3 基于样本重构的后向淘汰过程伪代码

3．5 本文方法整体流程图

3．6 小结

4 仿真实验及结果分析

4．1 仿真平台

4．2 标签SNP系统设计

4．3 实验数据

4．3．1 真实数据集

4．3．2 模拟数据集

4．4 实验结果及评价

4．4．1 评价指标

4．4．2 实验结果及分析

4．5 小结

5 结束语

5．1 研究工作总结

5．2 进一步研究工作

参考文献

致谢

攻读硕士学位期间主要研究成果