基于单体型重建的一种改进启发式聚类算法研究.pdfVIP

学兔兔 1 勺 化 基于单体型重建的一种改进启发式聚类算法研究 Research on an improved heuristic clustering algorithm based on haplotype reconstruction 侯 锟 HOU Kun (吉林师范大学 计算机学院。长春1 36000) 摘 要：单核苷酸多态性(SNPs)是一个物种中DNA序列中某个位点上的碱基变化，研究单体型对于 诊断疾病和药物研制有着重要作用。基于信息工程的单体型重建就是对由SNP片段组成的基 因片段进行组裴，从而构造出原来的一对单体型。本文在k最近邻和粒子群算法的基础上，提 出一种解决单体型重建问题的一种聚类算法。最后，本文分别采用模拟数据和真实数据来检验 本文所提出的算法，实验结果证明所提出算法的可行性与高效性。 关键词：单核苷酸多态性；单体型重建；聚类；k最近邻算法；粒子群算法 中囝分类号：TB1 1 文献标识码：A 文章编号：1 009-01 34(201 2)1 0(上)-0094-03 Doi：1 O．3969／J．i88n．1 009-01 34．201 2．1 0(上)．30 0 引言 验，验证所提出算法的科学性与高效性。 如今，随着时代的发展，科技的进步，生物 1 单体型建模过程分析 工程建模已成为计算机理论及应用领域内最具吸 SNP位点是一个物种的基因组DNA序列中不 引力、最具挑战性的一个方向之一。随着人类基 同个体可能出现不同碱基的位置。位于一个SNP 因组图谱的基本完成u ，人们对遗传的差异性、由 位点的碱基称为等位基因。对于任意一个SNP位 基因突变引起的疾病复杂性有了更精确的阐释【2J。 点来说，若两条同源染色体上的碱基相同，则称 现在人们普遍认为，DNA序列中少数的差异是导 为纯和位点；若不相同，则称为杂合位点。几乎 致遗传疾病的主要原因。单核苷酸多态性(SNPs)， 所有的SNP位点上的碱基都只有两种取值，为方 DNA某一位置碱基的变化p ，被认为是一个物种 便起见，我们用字符集{0，1，．}上的字符序列来表 不同个体表型的主要遗传来源 】。研究SNPs对基 示单体型，而不必用真正的碱基字符，其中 “-” 因的研究、遗传疾病的诊断和药物研制有着重要 表示该位点的取值未知，被称为空。因此单体型 作用。 可看作是一个字符串序列。 现存研究成果主要集中与相关理论研究。依 人类的DNA序列是按染色体成对出现的，每 赖于不同的数据错误类型，主要有几种不同的解 一 条染色体上SNP位点上的碱基序列叫做单体型， 决模型。其中主要有最少片段删除模型、最少 所以人类等二倍体生物都有一对单体型。在医学 SNP去除模型和另外一种被普遍应用的模型、最 研究中，单体型数据通常比单个SNP携带更多的 少错误纠正模型。其中MER模型首先被Lippert 信息。基于单体型在遗传分析上的重要性，现在 等人证明是NP—hard问题 。实际上单体型重建问 人们较为关注的是单体型的检测问题。 题可以被看作是一个聚类问题，这便是本文的落