在生物科技发展迅速的二十一世纪,遗传变异研究在人类基因组测序计划项目完成后成为了最为关注的热门研究之一。而单核苷酸多态性(Single Nucleotide Polymorphisms,SNP)在各类遗传变异中是最为突出常见的一种形式,针对SNP的研究可以探索生物进化历程,解决很多遗传性疾病的诊疗问题、了解易感机制,以及对药物研制等方面发挥重要作用。在一些相关研究中得知,单体型所携带的遗传信息相比单个SNP位点要更丰富。然而,使用生物学的传统方法进行个体单体型测序会受到实验条件和昂贵开销的限制,个体单体型重建这个计算问题应运而生,即根据个体DNA测序片段,利用计算技术完成单体型的重建。本文针对二倍体个体单体型重建问题展开研究。HapCompass算法是求解最少带权边删除模型(The Minimum Weighted Edge Removal,MWER)的有效启发式算法,该算法采用删除权值绝对值最小的边的方式消除冲突环基,当同时存在多条权值绝对值最小的边时,HapCompass随机选择删除边,导致求解方案的不确定性,降低重建效果。针对此问题,本研究提出算法IHapCompass,该算法改进去边规则,利用(?)和(?)分型的片段支持差异数与总片段数之间的比值来确定删除边,对随机取值问题做出有效限定。此外,IHapCompass以单体型中0/1取值的概率为图中孤立点赋值,明确孤立点取值。采用HapMap发布的CEPH样本中的单体型数据,由CELSIM和MetaSim两种测序片段模拟生成器生成片段数据,在片段覆盖率、错误率、单片段长度和单体型长度等参数的不同设置下,比较分析算法IHapCompass、HapCompass、DGS和Fast Hare的重建率和运行时间。实验结果显示,IHapCompass算法在不同的参数设置下,均能获得最高的单体型重建率,具有较高的执行效率。最少错误更正模型MEC试图更正最少的测序错误来确定单体型唯一分型,本文针对该模型提出一种有效启发式算法HIEF。通过分析真实测序数据NA12878的数据特征,发现存在于真实DNA测序片段数据中的规律,即测序片段的非空位点数越多,则携带的信息越可靠。基于这个思路,算法HIEF首先选取测序片段中非空位点最多的一条片段作为基准,然后基于MEC模型将剩下的片段划分为两个不相容的集合,划分过程中不断地对非空位点数最多的测序片段做扩展,最终扩展完成重建得出二倍体单体型。采用CELSIM生成的模拟数据和NA12878的真实测序片段数据对算法性能进行测试和分析,实验结果显示,算法在多个评价指标中均能获得较Exact、Fast Hare和DGS三个算法更好的性能。综上所述,本文对二倍体单体型重建问题进行算法研究,大量实验下的多个评价指标表明,本文提出的IHapCompass和HIEF算法均能获得较高精准度的重建结果,有效地解决单体型重建的实验开销与时间成本问题,为生物学研究人员提供参考和帮助。