单体型组装(Haplotype Assembly)是根据测序得到的DNA片段通过各种模型算法来重建出生物个体的单体型。随着人类基因组计划(Human Genome Project,HGP)的逐渐完成,人们已经认识到个体之间基因序列的差异是造成个体之间各种表型差异的主要原因,如发色、体型、罹患疾病的不同风险程度等。因此分析个体的单体型在遗传领域有非常重要的意义,其主要应用有疾病诊断、药物研究等。如果能仅通过生物手段就获得个体正确的完整DNA序列,那么单体型组装问题是容易解决的。然而,在实际过程中,由于生物实验的的限制,通常仅能得到一些较短的DNA片段,并且实验中会不可避免地发生一些测序错误。因此,根据一些有测序错误的DNA片段并结合计算机技术来组装出错误最少甚至是正确的个体单体型既是目标,也是挑战。机器学习领域的半监督学习策略是一种科学利用无类标签数据的学习模式,由于有标签样本仅占少数,因此结合少量有标签数据和大量无标签数据来提高模型的学习性能是非常有必要的。基于以上,本文提出两种结合半监督学习的单体型组装算法。K均值算法(K-Means)是机器学习中非常经典的聚类算法,算法在迭代过程中不断地进行划分和更新聚类中心以获得最优聚类效果。本文提出一种基于半监督学习的单体型组装K均值算法,称之为SKMEANS。SKMEANS算法利用在预处理阶段可确认类别的片段构建初始聚类中心,然后通过比较片段与聚类中心之间的距离完成片段的划分,并更新聚类中心,这一阶段不断重复,直到聚类中心不再变化。K均值聚类阶段完成后得到的聚类中心被认为是最优单体型,通过两个聚类中心还原两条单体型,从而完成单体型组装。K最近邻算法(K-Nearest Neighbor,KNN)是机器学习中最基本的分类算法之一,算法的基本原理是:在特征空间中,如果样本的K个最近距离的样本类别多数属于某一个类别,那么该样本也属于这一个类别。本文提出一种基于半监督学习的单体型组装K最近邻算法,称之为SKNN。SKNN的数据预处理阶段与SKMEANS相似,通过已确认类别的片段构建初始SKNN模型。然后利用初始模型对剩下未确认类别的片段逐个进行分类,并且将置信度高的片段加入训练集,来逐渐完善模型。分类完成后,模型将得到两个不相交集合,通过每个集合里的片段的重叠位点可以推导出两条单体型。在实验设计部分,本文同时利用模拟数据和真实数据对SKMEANS和SKNN的算法进行测试,并与另外两种单体型组装算法ProbHap和PEATH进行算法性能比较,实验结果显示,SKMEANS算法和SKNN算法是可行的,与其他两种算法相比有更高的准确率,并且在真实数据实验中,SKMEANS有运行时间上的优势。