单体型组装问题MEC／GI模型的参数化算法.pdfVIP

高技术通讯 2008年4月 第18卷第4期 单体型组装问题MEC／GI模型的参数化算法① 谢民主②一 王建新 陈建二 ( 中南大学信息科学与工程学院 长沙410083) ( 湖南师范大学物理与信息科学学院 长沙410081) 摘 要 根据DNA测序片段数据的特点，提出了一个时间复杂度为0(nk22 ：+mlogm+ mk1)的单体型组装问题MEC／GI模型的参数化算法，其中 为片段数，rt为单体型的SNP 位点数，k1为一个片段覆盖的最大SNP位点数(通常小于1O)，k2为覆盖同一SNP位点的 片段的最大数(通常不大于1O)。对于·实际DNA测序中的片段数据，即使 m和n都相当 大，该算法也可以在较短的时间得到MEC／GI模型的精确解，具有良好的可扩展性和较高 的实用价值。 关键词 生物信息学，参数化算法，基因型，单体型，单核苷酸多态性 rameterized algorithm)，有效地计算出了MEC／GI模型 0 引 言 的精确解。 单体型(haplotype)是人类染色体某一区域的单 1 SNP值的字符序列表示 核苷酸多态性(single nucleotide polymorphism，SNP) 位点上的碱基序列。单体型组装问题(haplotypes as． 单核苷酸多态性(SNPs)指的是在人群中1％的 sembly problem)也叫个体单体型问题(individual hap． 个体中出现的染色体某个位点上的碱基变异。SNPs 1otyping proplem)，指的是直接利用个体的DNA测序 广泛分布在人类基因组中，在整个人类基因组中大 片段数据来确定某个体的一对单体型(人类染色体 约有340万个SNPs。人类的染色体是成对存在的，’ 成对存在)。分析和识别单体型，对于遗传病等疾病 一 条染色体上的某一区域的SNP位点上的碱基序 的致病基因的精确定位、诊断和药物研究有重要作 列叫做单体型(haplotype)(见图1)，而一对染色体上 用。不幸的是在当前的实验技术下，直接测定个体 的某一区域的SNP位点上混合的碱基序列叫做基 的单体型既费钱又费时间，因此利用计算机技术来 因型(genotype)。在图1中，该个体的单体型是(A， 确定个体的单体型有极其重要的现实意义。目前已 T，A，C，G)和(G，C，A，T，G)；基因型为(A／G， 有多种单体型组装问题计算模型及其变种，如最小 C／T，A／A，C／T，G／G)。 片段清除(minimum fragment removal，MFR)模型、最 A．．T．．A．．C．．G 小SNP清除(minimtma SNP removal，MSR)模型-l J、最 小误差校正(minimun elTOr correction，MEC)模型 J 图1 单体型 等。为了提高模型的单体型重构精度，Wang等对 MEC进行了改进，引入了有基因型(genotype)信息的 一 对染色体上对应位点上的SNP值可以是相 MEC计算模型，即MEC／GI(MEC with genotype infor- 同的，这种现象叫纯合(homozygous)；也可以是不同 mation)模型[引。单体型组装问题MEC／GI模型指在 的，这种现象叫做杂合(heterozygous)。这样单体型 个体的基因型已知的条件下，利用个体的DNA测序 就可以用字符集{0，1}上的字符序列来表示，其中 片段数据和翻转最少的SNP位点值以确定该个体