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

发布时间：2017-12-21 19:01

  本文关键词：基于多位点连锁不平衡度量的标签SNP选择方法研究　出处：《中南大学》2014年硕士论文　论文类型：学位论文

  更多相关文章： 单核苷酸多态性 标签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数量,实验结果表明,本文方法具备较优性能。
【学位授予单位】：中南大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：Q811.4;TP18

【参考文献】

中国期刊全文数据库 前1条

1 裴志利;梁艳春;卢奕南;曹忠波;孔英;;从SNP到标签SNP的算法实现与讨论[J];内蒙古民族大学学报(自然科学版);2006年06期

，

本文编号：1316798