摘要
分型是计算生物学的一个新兴领域，在临床决策和生物医学科学中有着重要的应用。
虽然机器学习技术在许多生物医学应用中显示出巨大的潜力，但它们在分型中的用途尚未完全理解。
在本文中，我们研究了基于聚类的多倍体生物的阶段化技术的发展，其中在所研究的生物的细胞中每个染色体存在两个以上的拷贝。
我们基于相关聚类的概念，开发了一个称为PolyCluster(多集群)的新框架，然后使用一个有效的聚类合并机制来最小化驻留在每个集群中的短读之间的不一致量。
我们首先引入一个图形模型来量化每对DNA读数之间的相似性量。
然后，我们提出了线性规划、舍入、区域生长和集群合并的组合，以分组相似的读数和重建单倍型。
我们广泛的分析表明多簇不准确和可扩展的分型的有效性。
特别地，我们发现PolyCluster分别降低了H-PoP、HapColor和HapTree的切换误差44.4%、51.2%和48.3%。
此外，PolyCluster的运行时间比HapTree少几个数量级，同时它实现了与其他算法相当的运行时间。
索引词: 计算遗传学、染色体重建、DNA分型、单倍型组装
1介绍
随着新一代测序技术的不断进步，它们有望为DNA分型提供更大、更准确和更低成本的数据，从而允许单个单体分型。
二倍体生物中的DNA定相在个体和群体遗传学的许多应用领域中被证明是有效的〔1〕。虽然DNA定序已经研究了十多年〔2〕通过实验和计算方法，它仍然是一个具有挑战性的问题。由于与实验技术相关的成本以及计算方法的复杂性。虽然计算方法已经受到社会的更多关注，但是对于开发不仅精确而且可扩展的算法只进行了有限的研究。
多倍体是指单个生物体中每一个染色体存在两个以上的拷贝。目前许多二倍体，包括人类，来自多倍体祖先[ 3 ]。它在蕨类植物和开花植物中很常见（4），存在于鱼类和两栖动物等动物中。此外，最近的证据表明，多倍体在动物进化中比以前认为的更重要[5 ]。尽管多倍体分阶段在基因组研究中发现重要的应用，如癌症基因组学、元基因组学和病毒准种测序，但是目前的大多数分阶段技术都集中在二倍体上。直到最近，研究人员才开始开发多倍体单倍型的计算技术〔6〕-〔9〕。
本文介绍了多聚体，一种重建高倍性单倍型的新框架。我们的贡献可以概括如下：
(1)我们提出了基于分区的单体型的形式化定义，目标是最小化分区误差的数量。结合分区间相似性和内插法计算相异性；
(2)通过引入图模型来捕获DNA短读数对之间的相似度，对优化问题进行建模；
（3）提出了一种基于线性的引入图的分段聚类方法。
编程、四舍五入和集群区域生长，然后是集群合并技术，用于精确划分短读和重建与每个集群相关联的单体型；
(4)将PolyCluster与几种多倍体单倍体分型算法进行了比较，结果表明，该算法在切换误差和运行时间方面显著提高了单倍体装配的精度，同时在最小误差校正分数方面获得了可比结果。
2.相关工作
重建单倍型的研究进展DNA读数可分为两大类：数据删除和单倍型更新。
数据移除方法着重于从DNA读取的集合中移除数据(即，片段或SNP)，使得所得数据无错误[10]。
一旦获得这样的数据，使用经典的计算机科学划分算法将剩余的读分组为不相交集并构造单体型拷贝就很简单了。
单倍型更新方法已经受到更多的关注[11]–[17]，它关注于处理错误的数据集和重建单倍型，从而最小化错误度量。
数据去除方法使用诸如MSR(Minimum SNP Removal)和MFR(Minimum Fra.Removal)[10]之类的目标函数，它们分别涉及从数据中去除最小数量的SNP和最小读取次数，以获得可行的片段矩阵。
属于数据删除类别的另一个度量是MWER（最小重量边缘去除），其重点是从数据的不同抽象（即加权图）而不是片段矩阵去除数据（即，边缘）。
在〔16〕〔17〕中提出的方法试图解决最小化目标目标的最优化问题。
大多数二倍体单倍型分析方法属于单倍型更新类别，使用最小误差校正（MEC）[18]作为其目标函数[19] - [23]。MEC得分指的是片段矩阵中的编辑数，使得每个读数可以映射到重建的单倍型之一上。
因此，MEC得分还表示片段组和对应的单倍型拷贝之间错配的单碱基对的量。最小化二倍体基因组中单倍型重建的MEC评分的问题显示为NP难的[24]。
使用MEC评分作为二倍体单倍型分型中的目标函数是重要的，因为MEC与基础错误调用引起的错误相关，这是最常见的错误来源[12]。 [25]中的作者引入了一个变体
被称为k-cMEC的MEC，受到未来发电技术的测序误差的均匀分布的推动，其中每列的错误数（因此，校正）由整数k限制。
大多数上述算法是为二倍体单元型分型而开发的，其中有一组片段基于相似性测量对其进行双分区，以产生一对互补的单倍型。由于二分法，这些方法无法扩展到更高的倍性水平
他们的算法的性质。然而，对于多倍体生物，问题更具挑战性，因为单倍型拷贝不是互补的，因此不能相互推断。此外，多元醇类算法的计算复杂性可以基于读取分区或SNP分区方法而变化。大多数算法将读取分成多个组，以重建单倍型集和 一些其他方法使用不同的SNP位点子集和通过迭代更新单倍型集，以满足准确度测量和生成单倍型。因为优化MEC是NP难问题[26]，
确切的解决方案具有指数复杂性。最近的研究已经分析了这种精确度测量的固定参数易处理性和近似性[27]。相关度量是在[28]中提出的wMEC（加权最小误差校正），其中每个可能的校正与表示在相应位置处分配给该SNP值的置信度的权重相关联[29]。虽然MEC已被广泛应用于文献[8]，[12] - [14]，[30]，[31]，但最近的研究表明较低的MEC评分并不一定对应于更高质量的重建单倍型。多倍体基因组[8]，[30]，[31]。
因此，不同的研究表明转换误差（SWE）[8]，[31]是评估单倍型组装算法性能的更重要的准确度量度。SWE是指重建的单倍型之间的错配量和真正的单倍型。显然，在没有真实的情况下
单倍型，无法测量SWE。因此，许多研究报告SWE作为精确性能指标，对模拟多倍体数据进行分析。[31]中的作者引入了切换误差的变化，称为矢量误差，其被定义为必须发生切换的所有染色体上的最小片段数（即，对于二倍体，矢量误差恰好是切换误差的两倍）。
使用新一代测序对多倍体单倍型分析[7]，[8]，[31] - [33]的研究很有限数据。然而，这些方法在精确度和运行时间之间的平衡能力有限。在本文中，我们开发了PolyCluster，它使用新的距离测量单倍型组装，并且特别是随着单倍型区段长度的增加而具有高度可扩展性。我们用这个新的距离测量和一个有效的片段表明通过切换误差标准测量，我们可以实现比传统算法更准确的单倍型。我们还演示了我们的方法与最先进的算法进行比较在计算复杂性和运行时间方面尤其随着读取长度的增长而增加。
3问题陈述
单倍型组装的目标是从大量DNA读取中重建生物体染色体的每个拷贝。常规的单个单倍型装配者通常将称为片段基质的标准基质作为输入，其包含DNA短读取。
片段矩阵中的每一行都与读取相关联，每列代表一个SNP站点。
每个读数由来自字母A = {A，T，C，G，' - '}的等位基因序列表示，其中“ - ”指的是未被读数覆盖的SNP位点。但是，使用基因型调用我们可以将底层字母缩小为较小尺寸的字母，如下节所述。
3.1假设
在生物体的许多变体基因座中，原始字母表可以编码成五元组with = {00,01,10,11，' - '}，以便于计算，其中每个两位入口指特定SNP位点的等位基因，' - '表示缺少信息，或者因为片段不跨越位点或由于测序分析失败。
在与较高倍性基因组相关的阅读矩阵中，我们只保留每个基因座最受欢迎的等位基因。如果存在很少见的其他等位基因，我们将它们视为“缺失”，并在片段矩阵中用' - '替换它们。
令{x1l，x2l，x3l :::，xml}是与片段矩阵X中的第l列相关联的元素。 例如，如果两个最流行的等位基因是'A'和'C'，我们对它们进行编码作为二进制值。
分配给X中的这些单元的值是任意选择的（例如，'00'和'01'）。
如果在同一列中除了'A'和'C'之外还有另一个等位基因，但很少见，我们丢弃该等位基因并在X中的相应细胞中分配' - '。
另外，倍性水平'K'在多倍体单倍型分型中是先验已知的。如果倍性水平未知，则问题转化为生物体鉴定，这超出了本研究的范围。
我们假设在构建片段矩阵之前将DNA读数与参考基因组序列比对。使用映射对齐算法执行对齐，这可能在短读取中引入错误。此外，在映射到所有当前单倍型装配者的片段矩阵之前，丢弃所有纯合位点。
由于SNP位点在基因组中稀疏，我们只维护覆盖至少两个SNP位点的片段，以便我们可以在变异位点中关联多个片段。
在本文中，我们通过识别断开的单倍型模块进行每块单元型分型。如果有两个相邻的单倍型模块被认为是“断开的”没有读取跨越两个块。识别这样的块可以使用一个使用滑动的简单算法来完成在SNP站点上大小为2的窗口。窗口指示转换如果没有碎片，从一个块到下一个块覆盖2个SNP位点的非缺失等位基因。
3.2问题定义
多倍体单倍型分型的一般形式是重建
来自给定读数组的'K'单倍型通过DNA测序从染色体的'K'拷贝获得。
由于覆盖不足和读数错误，解决这种一般单倍型组装问题具有挑战性。
覆盖不足是指DNA测序技术仅提供少量重叠读数的事实，导致仅在最终单倍型组中重建SNP位点的子集。
如果片段，问题变得更具挑战性
矩阵包含错误，例如测序错误，嵌合读取对和错误变体。
在分子生物学的现实世界中，实验绝不是没有错误的。
导致这些错误
在从相同单倍型拷贝中提取的冲突读数中。
相互矛盾的数据阻止我们在所得单倍型中的每个SNP位点可靠地重建正确的等位基因。
我们定义多倍体单倍型分型如下。
给定从染色体的'K'拷贝获得的片段矩阵X，
重建'K'单倍型，以便优化目标函数。
如前所述，
过去已经为二倍体单倍型分析引入了许多目标函数。
示例包括最小错误
校正（MEC），最小片段去除（MFR），最小SNP去除（MSR）和最长单倍型重建（LHR）[10]。
在本文中，我们介绍最小值
Fragment Disagreement（MFD），其目标是找到片段的分区以使得求和
分区间相似性和分区内不相似性的最小化。
我们假设通过在聚类过程中结合分区间相似性和分区内不相似性，
与现有技术相比，我们将在最小化切换误差方面实现更高质量的单倍型。
这个假设得到了支持
我们的结果部分
我们对多倍体单倍型分型的方法本质上是片段分割方法。
一旦片段被分成'K'个不相交的分区，
每个分区可用于合并驻留在该分区中的片段并构建一个单倍型拷贝。
该问题的形式定义如下。
令Xm n是包含SNP值xil 2的给定片段矩阵，其从片段F = ff1，:::，fmg获得，属于n个SNP位点，S = fs1，:::，sng。此外，让'K'为倍性水平，即从中得到F片段的染色体拷贝数。假设
我们的算法将每个片段fi分配给'K'个不相交的分区之一P = fp1，：::，pKg，初始化为pk = ;.每组pk可用于通过合并pk中的片段来构建单倍型hk，从而产生单倍型H = fh1，:::，hKg。然后，多倍体单元型分型是将X中的每个片段fi分配给'K'分区之一的问题
pk使得（1）中的总成本Z最小化。