论文部分内容阅读
SNP(Single Nucleotide Polymorphism)分析在探究生物群体的遗传关系、分析疾病关联性等方面发挥着重要的作用,但与单个SNP相比,单体型数据包含了更加丰富的遗传信息,其在基因相关研究及医学治疗中发挥着重要的作用。然而,利用实验方法获取单体型数据的成本过于昂贵,因此利用计算方法获取单体型数据的单体型重建问题应运而生,并受到了广泛的关注。本文针对二倍体单体型重建问题展开研究,具体工作如下:针对最少错误更正模型对重建问题进行研究,提出一种基于支持度选取枚举值的重建算法EHDMS(Enumeration Haplotyping Diploid with More Support)。EHDMS算法依次重建单体型中的每个位点,对于给定位点,首先枚举该位点的两种取值情况,然后选择覆盖该位点的片段的更高支持度的取值,作为该位点的重建值。选取HapMap发布的CEPH样本中的单体型进行实验,采用CELSIM和MetaSim两种测序片段模拟生成器生成实验测试数据。通过设置不同片段覆盖率、错误率、单片段长度和单体型长度等参数,对算法EHDMS、 FAHR、Fast Hare和DGS的重建率和运行时间进行对比分析。实验结果表明,EHDMS算法在大部分情况下能获得较其它三种算法更高的重建率,并且具有较高的运行效率。针对最少错误更正模型,提出一种基于差异度选取枚举值的重建算法EHDLD (Enumeration Haplotyping Diploid with Least Difference)。当枚举出给定位点的取值时,分别计算两种取值情况下,单体型与覆盖该位点的片段的距离和,并选择对应于较小片段差异度的取值,即对应于距离和较小的取值。实验结果表明,EHDLD与EHDMS算法具有相近的问题求解性能,且其在大部分情况下能获得较FAHR、Fast Hare和DGS三种算法更高的重建率。综上所述,本文针对最少错误更正模型,提出选取枚举值的重建算法EHDMS和EHDLD。实验结果表明,这两个算法均能以较快的求解速度获得较高的重建精度,是重建二倍体单体型的有效方法。