第９卷第２期 ２０１０年４月 江南大学学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆ Ｊｉａｎｇｎａｎ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｖｏ１．９ Ｎｏ．２ Ａｐｒ． ２０１０ 图挖掘在ＤＮＡ混合样本拆分中的应用 康艳荣， 李万水， 张国臣， 周冬林， 楚川红 （公安部物证鉴定中心，北京１０００３８） 摘 要：以图论为基础提出了基于图结构的ＤＮＡ混合样本拆分算法——ＭＤＧ算法，对混合ＳＴＲ 图谱中每个基因座构造不同的等位基因图，形成等位基因图集，把ＤＮＡ混合样本的拆分转化为在 图集中的挖掘问题。ＭＤＧ算法的提出进一步扩大了图论的应用范围，也为混合样本拆分提供了新 的解决思路。 关键词：图；混合样本；峰面积 中图分类号：Ｄ ９１９．２；ＤＦ ７９５．２ 文献标识码：Ａ 文章编号：１６７１～７１４７（２０１０）０２—０２１０一Ｏ３ Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｇｒａｐｈ Ｍｉｎｉｎｇ ｉｎ Ｉｎｔｅｒｐｒｅｔｉｎｇ ＤＮＡ Ｍｉｘｔｕｒｅｓ ＫＡＮＧ Ｙａｎ—ｒｏｎｇ，ＬＩ Ｗａｎ－ｓｈｕｉ， ＺＨＡＮＧ Ｇｕｏ—ｃｈｅｎ， ＺＨＯＵ Ｄｏｎｇ—ｌｉｎ， ＣＨＵ Ｃｈｕａｎ—ｈｏｎｇ （Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｆｏｒｅｎｓｉｃ Ｓｃｉｅｎｃｅ，Ｍｉｎｉｓｔｒｙ ｏｆ Ｐｕｂｌｉｃ Ｓｅｃｕｒｉｔｙ Ｐ．Ｒ．Ｃ，Ｂｅｉｊｉｎｇ １０００３８，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ａ ｌｏｔ ｏｆ ｉｎｓｔａｎｃｅｓ ｃａｎ ｂｅ ｄｅｓｃｒｉｂｅｄ ｉｎ ｇｒａｐｈ ｉｎ ｒｅａｌ ｗｏｒｌｄ ｂａｓｅｄ ｏｎ ｇｒａｐｈ ｔｈｅｏｒｙ．Ｔｈｅ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｓｅｐａｒａｔｉｎｇ ＤＮＡ ｍｉｘｔｕｒｅｓ・ＭＤＧ（Ｍｉｘｔｕｒｅｓ Ｃｏｍｐｏｎｅｎｔ Ｄｅｅｏｎｖｏｌｕｔｉｏｎ ｕｓｉｎｇ Ｇｒａｐｈ ｔｈｅｏｒｙ），ｂｙ ｗｈｉｃｈ ｅａｃｈ ｌｏｃｉ ｃａｎ ｂｅ ｃｏｎｓｔｒｕｔｅｄ ａｓ ｓｏｍｅ ａｌｌｅｌｅ ｇｒａｐｈｓ．Ｔｈｅｓｅ ｇｒａｐｈｓ ｃｏｍｐｏｓｅ ａ ｇｒａｐｈ ｓｅｔ ａｎｄ ｃｏｎｖｅｒｔ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｓｅｐａｒａｔｉｎｇ ＤＮＡ ｍｉｘｔｕｒｅｓ ｉｎｔｏ ｇｒａｐｈ ｍｉｎｉｎｇ．Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｅｘｔｅｎｄｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｇｒａｐｈ ｔｈｅｏｒｙ ａｎｄ ｐｒｏｐｏｓｅｓ ａ ｎｅｗ ａｐｐｒｏａｃｈ ｏｆ ｓｅｐａｒａｔｉｎｇ ｍｉｘｔｕｒｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｇｒａｐｈ，ｍｉｘｔｕｒｅｓ，ｐｅａｋ ａｒｅａ 在法医生物物证检验的ＤＮＡ分析中，混合样 等人进一步开发计算机程序，完善了算法，形成了 一本经常遇到，如受害人与犯罪嫌疑人的混合血。如 何进行混合样本中各个供体基因型的分离，国内尚 没有成熟的方法，这也是一直困扰ＤＮＡ检验人员多 个计算机程序包，自动对混合样本进行拆分 。 作者在文中所提出的ＭＤＧ（Ｍｉｘｔｕｒｅｓ Ｃｏｍｐｏｎｅｎｔ Ｄｅｃｏｎｖｏｌｕｔｉｏｎ ｕｓｉｎｇ Ｇｒａｐｈ ｔｈｅｏｒｙ）算法以图的挖掘 年的难题。国外关于混合样本拆分方法的研究始于 ２０世纪９０年代，Ｃｌａｙｔｏｎ、Ｇｉｌｌ等人提出了利用峰面 积分析混合样本的理论基础¨ ，随后Ｇｉｌｌ、Ｃｌａｙｔｏｎ 等人编写了一组计算机程序来推断混合样本中各 算法为基础，首先对混合ＳＴＲ图谱中每个基因座建 立不同的等位基因图，形成等位基因图集；其次根 据混合ＳＴＲ图谱中第一个包含４个等位基因的基因 座，计算该混合样本所有可能的混合比例；接着在 针对混合ＳＴＲ图谱中其余每个基因座对应的图集 的挖掘中，将不满足混合比例的拆分去掉，优化拆 分的效率；最后对每个基因座的挖掘结果任意组 合，得到对混合样本的所有可能的拆分组合。 组分的比例和生成混合样本中的基因组合，他们用 最小残差平方和方法对混合样本进行了拆分【２ Ｊ。而 后Ｐｅｒｌｉｎ和Ｓｚａｂａｄｙ、Ｗａｎｇ等人则分别利用线性混 合样本分析方法ＬＭＡ和最小平方卷积反演算法 ＬＳＤ完成了对混合样本的拆分 。最后，Ｂｉｌｌ、Ｇｉｌｌ 收稿日期：２００９—０８—１５； 修订日期：２００９—０９—２３。 作者简介：康艳荣（１９８０一），女，河北唐山人，助理研究员，工学硕士。主要从事数据挖掘研究。 Ｅｍａｉｌ：Ｋａｔｈｅｒｉｎｅ．ｋａｎｇｙｒ＠ｇｍａｉｌ．ｃｏｉｎ 第２期 康艳荣等：图挖掘在ＤＮＡ混合样本拆分中的应用 ， ， ２１ｌ １ 数学模型的建立 现实生活中的许多问题都是研究某一类事物 和它们之间的某种关系，若用点表示某一类若干事 物，用线表示它们之间的某种关系，这样就可以把 要研究的问题抽象成为由一组点和连接着点的一 组线所构成的图，从而用图论方法，即一些特定的 ），当 。（ｅ）＝Ｈ（ ）／ （ ）（ √＝１，２）满 足 Ｇ（ｅ）∈（０．６７，１．６７）时，贝０ Ｖ ， ∈Ｖ（Ｇ）（ｉ， ＝１，２）都有边ｅ∈Ｅ（Ｇ），则由 （Ｇ），Ｅ（Ｇ）组成 的图Ｇ也称为二等位基因图。③Ｖ（Ｇ）＝（ 。， ， ， ：），当 。（ｅ）＝Ｈ（ ）／Ｈ（ ）（ｉ√＝１，２）不满足 Ｇ（ｅ）∈（０．６７，１．６７）时，Ｖ ， ∈ （Ｇ）（ｉ＝Ｊ－）都 有边ｅ∈Ｅ（Ｇ），则由 （Ｇ），Ｅ（Ｇ）组成的图Ｇ也称 方法研究，使其获得解决。为了叙述方便，给出如下 为二等位基因图。由二等位基因图组成的图集称为 定义： 定义１（四等位基因图） 设 ， ：， ，， 是，基因座 （，＝１，２，…，１６）包含的４个等位基因，Ｈ（ ）（ｉ＝ １，２，３，４）是等位基因对应的峰面积，则由 （Ｇ）＝ （ １， ２， ３， ４）， Ｇ（ｅ）＝Ｉｔ（ ）／Ｈ（ ）（ｉ＝１，２，３，４； ＝１，２，３，４）满足 （ｅ）∈（０．６７，１．６７），Ｅ（Ｇ）： ｛ｅ｝，所组成的图Ｇ为四等位基因图。由图Ｇ组成的 图集称为四等位基因图集，记为Ｇ 。 性质１ 如果四等位基因图中４个顶点对应的峰面 积相同，则四等位基因图是完全图。 证 给定四等位基因图Ｇ，根据等位基因图的定 义，当Ｇ中４个顶点对应的峰面积相同，即Ｖ ， ，∈ （Ｇ），均满足 （ｅ）∈（０．６７，１．６７），也就是说Ｇ 中任意两顶点之间都有边相连，根据图论中完全图 的定义，可知该四等位基因图是完全图。证毕。 定义２（三等位基因图） 设 ， ， 是，基因座 （，＝１，２，…，ｌ６）包含的３个等位基因，日（＇／３ ）（ｉ＝ １，２，３）是等位基因 对应的峰面积，设 （Ｇ）＝ （ 。， ：， ，， ），其中 与 （ｉ－Ｗ－１，２，３）中的一顶点 相同。①设 ∈Ｖ（Ｇ）， 。＝ （ｉ＝１，２，３）， （ｅ）＝ 日（ ）／ｉ４（ ）（ｉ＝１，２，３）无法确定…，则ｅ∈ Ｅ（Ｇ）。②设 ， ∈Ｖ（Ｇ）， ≠ ≠ （矗，ｍ＝１， ２，３且 ≠ｍ）， 。（ｅ ）＝ （ ）／Ｈ（ ）（ ＝１，２，３） 无法确定， （ｅ ）＝Ｈ（ ）／Ｈ（ ）（ｍ＝１，２，３）无 法确定，则ｅ ，ｅ ∈Ｅ（Ｇ）。③设 ， ∈Ｖ（Ｇ）， ≠ ≠ （ ，ｍ＝１，２，３； ≠ｍ）； Ｇ（ｅ） ＝ Ｈ（ ）／Ｈ（ ）（ ，ｍ＝１，２，３； ≠ｍ）；当 Ｇ（ｅ）∈ （０．６７，１．６７）时，ｅ∈Ｅ（Ｇ）；否贝０ Ｐ≠Ｅ（Ｇ）。贝Ｕ由 （Ｇ），Ｅ（Ｇ）组成的图Ｇ为三等位基因图。由三等位 基因图组成的图集称为三等位基因图集，记为Ｇ 。 定义３（二等位基因图） 设 ， 是第，基因座 （，：１，２，…，１６）包含的两个等位基因，Ｈ（ ）（ｉ＝ １，２）是等位基因 对应的峰面积。①Ｖ（Ｇ）＝（ ， Ｉ， Ｉ， ２）或Ｖ（Ｇ）＝（ １， ２， ２， ２），此时 Ｇ（ｅ）＝ Ｈ（ ）／Ｈ（ ，）（ ，Ｊ．＝１．２）无法确定，则Ｖ ， ，∈ Ｖ（Ｇ）（ｉ，Ｊ．＝１，２）都有边ｅ∈Ｅ（Ｇ），称由Ｖ（Ｇ）， Ｅ（Ｇ）构成的图Ｇ是二等位基因图。②Ｖ（Ｇ）＝（ ， 二等位基因图集，记为Ｇ 。 定义４（一等位基因图） 给定Ｖ（Ｇ）＝（ 。， ， ， ），Ｖ ， ∈Ｖ（Ｇ）（ｉ＝ ）都有边ｅ∈Ｅ（Ｇ），称由 Ｖ（Ｇ），Ｅ（Ｇ）组成的图Ｇ为一等位基因图。由一等位 基因图组成的集合称为一等位基因图集，记为Ｇ 性质２ 一等位基因图为完全图。 定义５（二等分子图与二等分补图） 给定等位基 因图Ｇ＝（ ， ），图Ｇ ＝（ ，Ｅ ）（Ｅ ≠ ）称为图 Ｇ的二等分子图，其中 是这样一种点的集合， 只包含两个顶点 和 ，且 ， Ｖ，（ ， ）∈Ｅ 且 （ ， ）∈Ｅ。给定等位基因图Ｇ＝（ ，Ｅ），Ｇ ＝ （Ｖ ，Ｅ ）（ ≠ ）是Ｇ的二等分子图，图Ｇ ＝ （ ，Ｅ”）称为图Ｇ的二等分补图，其中 ＝Ｖ—Ｖ ， Ｅ 是这样的集合，Ｖ ， ∈ ，如果（ ， ）∈Ｅ，则 （ ， ）∈Ｅ”。 ２ 基于图结构的ＤＮＡ混合样本拆分 算法设计 在混合ＳＴＲ图谱中，每个基因座包含的等位基 因最多为４个，算法设计如下： １）生成第，基因座对应的图集Ｇ，，（Ｊ＝１，２，３， ４）。 ２）找到第一个四等位基因图集Ｇ 。 ３）求Ｇ 中图Ｇ对应的第 种二等分子图的顶 点序列和其二等分补图的顶点序列，并计算混合比 例Ｍ （ ：１，２，３）。 ４）根据 （ ＝１，２，３）和峰面积比例区间确 定每一个等位基因图集中对应的二等分子图的顶 点序列和二等分补图的顶点序列。 ５）将每一等位基因图集生成的所有顶点序列 作为树 中某一层的结点逐层生成树 。 ６）重复以下步骤直到所有叶结点都被访问：① 找到从Ｒｏｏｔ结点到叶结点的路径；②输出该路径中 的所有结点。 ３ 仿真实验及结果分析 文中利用ＭＤＧ算法对混合比例为１：１的ＳＴＲ ２１２ 江南大学学报（自然科学版） 第９卷 图谱进行了仿真实验。实验表明最终得到的拆分个 如何确保将数据正确拆分且得到相对较少的 拆分个数，混合比例的阈值浮动选择十分关键，这 就需要借助ＤＮＡ专家在多年办案基础上积累的经 数与混合比例的阈值浮动有关。如图１所示，随着阈 值区间的不断增大，得到的拆分个数也将不断 增加。 ２５ ０００ 验，以及通过对大量混合样本的分析实验，得到一 些规律性的知识来进一步指导ＭＤＧ算法，使其得到 更优解 ２０ ０００ １５ ０００ ４ 结 语 ＜一 ｄⅡ １０ ０００ 混合样本的拆分是法医遗传学检验中经常遇 到的一个难题，文中阐述了将混合样本的拆分转化 为图挖掘的方法，算法的提出为混合样本的拆分问 题提供了一种新的解决思路，为提高混合样本的证 ０．１Ｏ０ ０，１０５ ０．１１０ ０．１２０ ０．１２５ ０．１３０ ０．１３５ ５ ０ｏ０ ０ 阚值 据价值提供了一定的理论基础，是计算机科学在生 物科学方面一个新的应用。在此基础上，将继续改 图１ 混合比例的阈值浮动范围与组合个数的关系 Ｆｉｇ．１ Ｒｅｌａｔｉｏｎｓｈｉｐ ｂｅｔｗｅｅｎ ｔｈｒｅｓｈｏｌｄ ａｎｄ ｔｈｅ 进算法效率，以得到一个完善成熟的混合样本拆分 系统。 ｎｕｍｂｅｒ ｏｆ ｃｏｍｂｉｎａｔｉｏｎｓ 参考文献（Ｒｅｆｅｒｅｎｃｅｓ）： ［１］Ｃｌａｙｔｏｎ Ｔ Ｍ，Ｗｈｉｔａｋｅｒ Ｊ Ｐ，Ｓｐａｒｋｅｓ Ｒ，ｅｔ ａ１．Ａｎａｌｙｓｉｓ ａｎｄ ｉｎｔｅｒｐｒｅｔａｔｉｏｎ ｏｆ ｍｉｘｅｄ ｆｏｒｅｎｓｉｃ ｓｔａｉｎｓ ｕｓｉｎｇ ＤＮＡ ＳＴＲ ｐｒｏｆｉｌｉｎｇ［Ｊ］． Ｆｏｒｅｎｓｉｃ Ｓｃｉｅｎｃｅ，１９９８，９ｔ：５５—７０． ［２］Ｇｉｌｌ Ｐ，Ｓｐａｒｋｅｓ Ｒ，Ｐｉｎｃｈｉｎ Ｒ，ｅｔ １．Ｉａｎｔｅｒｐｒｅｔｉｎｇ ｓｉｍｐｌｅ ＳＴＲ ｍｉｘｔｕｒｅｓ ｕｓｉｎｇ ａｌｌｅｌｅ ｐｅａｋ ａｒｅａｓ［Ｊ］．Ｆｏｒｅｎｓｉｃ Ｓｃｉｅｎｃｅ，１９９８，９１： ４１－５３， ［３］Ｐｅｒｌｉｎ Ｍ Ｗ，Ｓｚａｂａｄｙ Ｂ．Ｌｉｎｅａｒ ｍｉｘｔｕｒｅ ａｎａｌｙｓｉｓ：ａ ｍａｔｈｅｍａｔｉｃａｌ ａｐｐｒｏａｃｈ ｔｏ ｒｅｓｏｌｖｉｎｇ ｍｉｘｅｄ ＤＮＡ ｓａｍｐｌｅｓ［Ｊ］．Ｆｏｒｅｎｓｉｃ Ｓｃｉｅｎｃｅ，２００１，４６：１３７２—１３７８． ［４］ＷＡＮＧ Ｔ，ＸＵＥ Ｎ，Ｗｉｃｋｅｎｈｅｉｓｅｒ Ｒ．Ｌｅａｓｔ ｓｑｕａｒｅ ｄｅｃｏｎｖｏｌｕｔｉｏｎ（ＬＳＤ）：ａ ｎｅｗ ｗａｙ ｏｆ ｒｅｓｏｌｖｉｎｇ ＳＴＲ／ＤＮＡ ｍｉｘｔｕｒｅ ｓａｍｐｌｅｓ［Ｃ］． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １３ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｈｕｍａｎ Ｉｄｅｎｔｉｉｆｃａｔｉｏｎ．Ｐｈｏｅｎｉｘ：［Ｓ．ｎ．］，２００２． ［５］Ｂｉｌｌ Ｍ，Ｂｉｌｌ Ｐ，Ｃｕｒｒａｎ Ｊ，ｅｔ ａ１．ＰＥＮＤＵＬＵＭ—ａ ｇｕｉｄｅｌｉｎｅ－ｂａｓｅｄ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｉｎｔｅｒｐｒｅａｔｉｏｎ ｏｆ ＳＴＲ ｍｉｘｔｕｒｅｓ［Ｊ］．Ｆｏｒｅｎｓｉｃ Ｓｃｉｅｎｃｅ．２００５，１４８：１８１—１８９． ［６］Ｂｕｅｋｌｅｔｏｎ Ｊ Ｓ，Ｔｒｉｇｇｓ Ｃ Ｍ，Ｗａｌｓｈ Ｓ Ｊ．Ｆｏｒｅｎｓｉｃ ＤＮＡ Ｅｖｉｄｅｎｃｅ Ｉｎｔｅｒｐｒｅｔａｔｉｏｎ［Ｍ］．Ｂｏｃａ Ｒａｔｏｎ，Ｆｌｏｒｉｄａ：ＣＲＣ Ｐｒｏｃｅｓｓ．２００５． （责任编辑：秦和平）