单体型装配问题的研究现状

单体型装配问题的研究现状杨英杰（铜仁学院数学与计算机科学系，贵州铜仁554300）摘要：单核苷酸多态性（SNP）是指不同个体DNA序列上的单个碱基的差异，是人类基因组中最丰富的遗传变异。单体型是指位于一条染色体上或某一区域的一组相关联的SNP等位基因。研究表明在复杂性疾病研究方面，由多个变异位点组合构成的单体型所携带的信息比单个的SNP数据的信息更有价值，由此衍生了单体型装配问题。文章论述了SNP，单体型，基因型的定义，综述了求解单一个体单体型装配问题的主要模型及算法，同时阐述了求解群体单体型装配问题的5种方法及算法。关键词：单体型；单体型装配；SNP；基因型中图分类号：R394文献标识码：A文章编号：1673-9639(2011)02-0135-041．SNP、单体型与基因型国际人类基因组测序计划的完成，为全世界的科学家提供了一套精准的人类基因组序列图谱，为人类真正了解自身奠定了重要基础。同时，我们也惊奇地发现：任何两个不同个体的基因组序列至少有99.99%的碱基对是相同的，也就是说剩下的仅仅0.01%的差异包含了遗传上的差异因素。人们普遍认为DNA序列上的差异是不同个体之间表型差异（如肤色、发色，以及对疾病、药物的敏感性等）的重要原因。这些序列上单个碱基的差异称为单核苷酸多态性（SNP）。它是人类可遗传变异中最常见的一种，占已知多态性的90%以上。双倍体生物的基因组由一对染色体组成，一条来自父方，一条来自母方。单核苷酸多态性（SNP）是指染色体上的某些核苷酸位置，在这些位置上，不同个体的DNA序列有多种取值。在SNP位置上出现的核苷酸称为等位基因。一般地，在一个生物种群当中，出现在某个SNP位置上的核苷酸只有两种，而不是四种（A、G、C、T）。位于一条染色体上某一区域的一组等位基因称作单体型。位于一对染色体上某一区域的由成对的等位基因所组成的序列称作基因型，基因型是一对单体型的混合信息，如图1所示。如果基因型的某个位置上的一对等位基因相同，则称这个SNP位置上是纯合的，否则称为杂合的。图1某个个体的单体型与基因型由于单体型包含着多个SNP的遗传信息，许多研究表明，在与复杂性状的相关分析中，采用单体型比单个SNP具有更好的统计分析效果。由于在现有的实验条件下获得单体型数据非常困难，也非常昂贵，而获得基因型数据或SNP数据却很容易，因此利用计算收稿日期：2010-03-03基金项目：铜仁学院自然科学基金（编号TS10018）。作者简介：杨英杰（1982-），女，硕士，讲师，主要研究方向：最优化方法、生物信息学。第13卷第2期铜仁学院学报Vol.13,No.22011年3月JournalofTongrenUniversityMar.2011SNPSNPSNP染色体1AGAGAATTCGACATCCCGTTC染色体2ACAGAATTCGACATCCCGATC单体型1GAT单体型2CAA基因型{C；G}{A；A}{T；A}的手段推测单体型数据越来越重要，由此衍生了单体型装配问题。它大致分为两类，一类是单一个体单体型装配问题，一类是群体单体型装配问题。2．单一个体单体型装配问题单一个体单体型装配问题是从给定的某对染色体上的SNP片段数据来装配某个个体的一对单体型。给定的数据可能是比对好的带有SNP信息的基因组片段（由鸟枪测序法得到），也可能是进行大规模单体型推测时前期工作所得到的。当我们只考虑SNP位置时，这些短的基因组片段实际上就是比对好的SNP片段。如果知道一个个体的某对染色体上的全部DNA序列，装配单体型实际上就是简单地检查一些SNP位置上的核苷酸取值。然而，由于DNA测序方法的限制，我们只能得到一些短的DNA片段，而且这些片段不可避免地含有一些错误。另外，两条染色体的同源性也使问题变得复杂，因为我们不知道哪个片段属于哪条染色体。从计算的角度讲，单体型装配问题就是从给定的数据（可能有错误，有矛盾）中确定出一对“最好”的单体型。也就是说，如何根据片段上的SNP信息将给定的比对好的SNP片段分成两个集合，从而每个集合确定一条单体型。单一个体单体型装配问题目前主要有以下几种组合优化计算模型。2．1．最少片段去除模型和最少SNP去除模型二者是由Lancia等在2001年提出的。前者假定造成数据不一致的原因是由于污染，即有些SNP片段不是来自目标生物体，而是来自其他生物体，因此，强调去除最少的片段使得剩下的数据一致、不再有矛盾。后者假定所有的DNA片段都来自同一生物体，但测序过程中产生一些错误，因而要求去掉最少的SNP位置使得片段在余下的SNP位置上不再有冲突。Lancia还讨论了这两个问题的计算复杂性，在给定的片段没有间隙时是多项式可解的，片段在有间隙时是NP-难问题。Rizzi等在2002年给出了求解这两个模型的动态规划算法。[1]当SNP片段上的最多间隙数k固定时，这些动态规划算法是多项式时间的算法。2．2．最少错误纠正（MEC）模型最少错误纠正（MEC）模型是由Lippert等在2002年提出的，并证明是一个NP-难问题。这个模型假定所有片段来自同一个生物体，数据的不一致是由测序错误造成的，并且这些错误可以纠正而不是去除整个SNP片段或SNP位置（这种情况很实际）。针对MEC模型的求解的方法主要有两类，一类是精确算法，主要指基于分支定界的精确算法，[2]但是在可接受的时间之内仅仅能解决小规模的问题，另一类是启发式算法，这类算法虽然不一定能够找到准确最优解，但是它可以在短时间之内找到一个相当好的近似解。王瑞省等在2005年提出了基于遗传算法的启发式算法，[3]钱伟懿，杨英杰等在2008年提出了基于粒子群算法的启发式算法，[4][5]有效地解决了最少错误纠正模型中大规模的求解问题。2．3．带基因型信息的最少错误纠正（MEC/GI）模型带基因型信息的最少错误纠正（MEC/GI）模型是对上一个模型——MEC模型的改进，这个模型是由章祥荪，王瑞省等人在2004年提出的。他们将这一问题表述成一个整数线性规划模型，并证明是NP-难的，并且给出了一类特殊的MEC/GI模型动态规划算法，然后又设计了求解一般问题和大规模（SNP片段较多）问题的前馈神经网络算法。[6]该模型假定数据的不一致来自现实的DNA测序错误，这些错误应该得到纠正，在现有实验条件下，获得个体基因型信息较为容易，那么在纠正过程中利用了基因型的信息，装配出的单体型准确率会更高。2．4．加权最少错误纠正模型加权最少错误纠正模型也是对MEC模型的改进。在DNA测序过程中，测得的每一个碱基除了本身的信息外，还附加了所测碱基的检测质量值，也就是该碱基被正确测定的概率。在最少错误纠正模型中考虑每个碱基被正确测定的概率信息，Greenberg等提出了加权最少错误纠正模型，赵玉英等证明了加权的最少错误纠正模型是NP-难的，并且给出了基于动态聚类算法的启发式算法来求解这个模型。[7]3．群体单体型装配问题136铜仁学院学报2011年群体单体型装配问题：根据群体的基因型信息推断群体的每个个体的单体型。从基因型数据推断单体型就是消去基因型的杂合子位置，即确定杂合子位置上的两个等位基因到底属于哪条染色体。也就是说，对给定的一组基因型，寻找一个单体型集合，使得对每个基因型在这个集合中都有一对单体型对应这个基因型。目前，应用群体基因组数据推断单体型的方法主要有五类。3．1．系谱推断法系谱推断法是通过家系中相关个体的基因型，即追溯染色体片段的传递来推断单体型状态。尽管家系内推断单体型并不比在连锁作图中构建单体型的众多方法更简单，但这样的推断可以为紧密连锁的SNP提供真实的连锁信息。基于谱系数据的单体型装配方法大致分为两类。一类是Lin等提出的统计方法，[8]这种方法装配出来的每个单体型具有一个频率值，但是算法很浪费时间。另一类是Tapadar等提出的基于规则的方法，[9]这种方法装配出来的单体型没有一个数值评价，但算法很快。然而，当某些家系成员资料无法获得或数据缺失都可能使SNP间的关系状态模糊不清。3．2．Clark算法Clark第一个提出了在无相关个体间利用基因分型数据推断单体型的算法。[10]如果有二倍体生物的一组序列，并具有多个变异位点，该算法首先找出样本中所有纯合子与仅有单变异位点的杂合子，将这些个体的单体型作为已识别的单体型。然后再判断每一个已识别的单体型是否为那些尚未确定单体型并有变异位点的序列的等位基因，如果是，就将这种SNP的组合确定为新单体型。Clark方法存在的问题是，样本需要数量较多，否则会出现没有纯合子或单个变异的杂合子的情况，从而导致单体型的推断无法开始。3．3．最大似然算法:在运用Clark算法时，如果样本中没有纯合子或单变异的杂合子就无法开始单体型的推断。此外，当推断过程中出现多种可能的单体型时，依据已有的单体型来确定其中一种为新单体型的结果将受到抽样中个体排列顺序的影响。为了克服上述问题，Excoffier等提出了最大似然算法。[11]该方法以群体处于哈代-温伯格平衡状态为假设前提，对样本单体型频率采用EM算法进行最大似然估计。该方法首先建立关于各单体型频率的合理的似然函数。然后对单体型的频率或其对数求偏导数，得出其最大似然估计。但当单体型非常多时，运算量也非常大，如果采用EM算法进行迭代求解将大大提高运算速度。3．4．贝叶斯算法随着公共数据库中SNP位点的增多，需要考虑的单体型将呈指数增加，这会使EM算法的统计效力降低。为了克服EM算法的上述缺点，2001年贝叶斯理论被Stephens，Smith等引入单体型的推断问题中。[12]他们采用蒙特卡罗-马尔卡夫链方法进行推断，他们的算法也被称为SSD算法。该算法又包含了两个算式，一个是伪Gibbs抽样法，另一个是结合群体遗传的溯祖理论，采用了近似溯祖的先验分布。随后，Niu等采用Dirichlet先验分布提出另两种贝叶斯算法。[13]3．5．纯节俭模型方法纯节俭模型方法是由Gusfield等在2003年首先提出来的，目的是要寻找唯一单体型数目最少的单体型集作为解。这个方法是基于这样一个事实：在一个自然种群中，观察到的不同单体型的数目远远小于理论上所应有的数目（SNP位置数的指数个），这一点符合群体遗传学。王瑞省等对这个模型给出了基于分支定界的精确算法，[14]这个算法有一个预处理过程，从而减少了可能解的个数，对中小规模很有效。后来，王瑞省，吴凌云等又提出了利用遗传算法来求解较大规模（具有较多的SNP位置或较多基因型）的纯节俭模型方法，并在其中引入局部优化思想，即在进行了选择、交叉、变异之后，根据种群中个体适应度的标准差采用自适应局部优化策略。引用局部优化策略以后，可以在遗传算法迭代时使用比较小的种群规模。4．展望随着人类基因组单体型图的完成，单体型的研究必将在探究复杂性遗传疾病的遗传机理、患病风第2期杨英杰：单体型装配问题的研究现状137险与药物反应不同中扮演重要角色，因此单体型装配问题的研究显得尤为重要。然而，目前对单体型的研究还是初步阶段，还有很多问题等待着人们去探索。参考文献：[1]RizziR,etal.Practicalalgorithmsandfixed-parametertractabilityforthesingleindividualSNPhaplotypingproblem[C].InProceedingsofSecondInternationalWorkshoponAlgorithmsinBioinformatics(WABI),LectureNotesinComputerScience,Springer,2002,2452:29-43.[2]Rui-ShengWang,Ling-YunWu,Ji-HongZhang,etal.AlgorithmsforSNPhaplotypeassemblyproblem[J].高校应用数学学报(A).2004,19(z1):515-528.[3]Rui-ShengWang,Ling-YunWu,Zhen-PingLi,etal.Haplotypecon