跳到主要内容

汉明空间的凸壳能够有效地寻求基因组序列的相似性和聚类

抽象的

背景

在分子流行病学中,感染人群中宿主病毒变体的比较经常用于追踪人群的传播并检测病毒感染爆发。超深序列(UDS)的应用意义地增加了传输检测的灵敏度,但是在比较所有序列的比较时带来相当大的计算挑战。我们开发了一种基于汉明空间凸壳的新人比较方法。我们将该方法应用于从感染丙型肝炎病毒(HCV)的无关案例中获得的大量UDS样品,并将其性能与三种先前公布的方法进行了比较。

结果

汉明空间中的凸壳是一种数据结构,提供有关的信息:(1)集合内的平均汉明距离,(2)两组之间的平均汉明距离;(3)每个序列的近期中心;(4)两组成员之间的所有成对距离的下限和上限。这种过滤策略快速且正确地删除了所有成对HCV样本比较的96.2%,优于所有先前的方法。凸壳距离(CHD)算法根据实际和模拟数据集中研究群体的序列异质性显示了变量性能,表明使用聚类方法提高性能的可能性。要解决此问题,我们开发了一种新的聚类算法,K.-hulls,这减少了凸壳的异质性。该高效算法是K-Means算法的扩展,可以与任何类型的分类数据一起使用。比它更准确的6.8倍K.-mode,以前开发的分类数据聚类算法。

结论

CHD是一种快速有效的过滤策略,用于大量减少大型序列样品的成对比较的计算负担,从而促进使用基于阈值的方法计算感染个体之间的传输链路的计算。此外,凸壳有效地获得了宿主病毒群体的重要综合指标。

背景

大型遗传变异样本的比较和获得汇总统计的常见任务是许多领域,从数据库到癌症研究和分子流行病学的计算搜索。例如,来自正常组织和肿瘤的线粒体DNA变体的群体之间的比较带来了重要的见解[1].

病毒序列的系统发育分析经常用于爆发和传动链的调查[23.4.5.6.],通常使用每个受感染个体的单个序列。然而,许多病毒如丙型肝炎病毒(HCV)存在于每个感染的个体中许多遗传变异的群体。据观察,源中的少数群体变体通常是负责传输的群体,表明每个单独的单个序列的使用缺乏对检测这种变速器的灵敏度[7.]. 在疫情调查中,对从感染者身上取样的宿主内病毒群进行分子分析,在检测丙型肝炎病毒传播方面非常有效[8.9.10.11.].从流行病学特征爆发中获得的宿主内HCV变体的统计分析允许开发一种用于检测HCV变速器的简单和准确的基于阈值的方法[7.].

通过超深序列(UDS)的宿主HCV变体的采样,包括少数群体变体,提高了传输检测的灵敏度[7.].然而,比较来自每对样本的所有序列会产生相当大的计算挑战。例如,401个丙型肝炎病毒样本的相对较小的数据集需要执行80,200个两两样本比较,总共为4.56 × 1010.成对序列比较[12.].随着测试的案例的数量随着时间的推移而增加,传输网络的检测变得不切实际。然而,我们观察到,即使在高风险的人群中,我们也占所有样品对的所有样品对的占所有样品对的少于传输。因此,对所有序列对的详尽搜索是非常效率的,因为大多数样本对高于某些相关性阈值,这对应于HCV的3.77%[7.].简单地说,为了减少在一组样本上建立传输所需的计算数量,去掉这些对中的大多数将是非常有利的。

在计算机科学的各个领域的不同名称中遇到了类似的问题[13.14.15.16.17.18.19.].有快速字符串比较多的方法。病毒传输的检测是由三个因素的影响:(1)由于连续添加期间爆发调查新的数据样本,有必要比较同源序列中,两个或多个群体中的哪一个不同的序列的比较静态数据结构或静态数据库;(2)需要精确的距离计算的,使任何可用的快速启发式和不适合于目的近似方法;和(3)使用的相关性阈值的允许用于过滤策略的应用。这些因素已得到解决三个先前公布的滤波算法:K.-基于最大公共子串下界的mer-bloom滤波器[20.];每个人口的汉明半径和三角形不等式[20.];以及基于比较的签名方法K.即,K.-每对序列的块[21.].

当前的工作是由直觉驱动的,在一个集合中每对点之间的距离的比较可以被位于集合表面的点之间的距离的计算代替。对于欧几里得平面(图。1a) ,一组点X的凸包是包含X的最小凸集,可以将其可视化为由围绕X拉伸的橡皮筋包围的形状[22.].然而,汉明空间中的每一点是“在表面”[23.],这显然会使这种直觉无用。尽管如此,每个凸船都有一个架构,它简洁地描述了它[24.].For instance, for the set of strings Pn = (010000, 011010, 111000, 010010, 011110), the convex hull is *1***0, where * means that the position can be 0 or 1. Thus, the convex hull in the hamming space is a set comprising all binary strings matching the schema (16 sequences in this example).

图。1
图1

凸包数据结构。一种两个维度的凸壳的示例。B.给定群体的凸船体频率向量的示例。C计算两个种群之间的凸包距离

从病毒群体的核苷酸序列的多序列比对(MSA),可以使用在MSA的每个位置来计算核苷酸状态(A,C,G,T或间隙)的频率的矢量。这类似于上述凸壳模式,每个状态的频率的添加信息(图。1b)。这些载体也称为位置权重矩阵(PWMS),位置特定评分矩阵或加权模式[25.].他们已被用于转录因子绑定站点的模型和在线匹配算法[26.].

在这里,我们提出了一个快速和有效的过滤策略,其去除最成对比较,协助通过基于阈值的方法的传输链路的计算。此外,我们表明,凸包的应用显著减少了常规每个人口计算的许多重要的汇总统计数据的计算成本。

结果

源自凸船体的有用度量

每个文件的凸包提供以下信息:

  1. 1

    平均汉明距离汉明距离(广告P.)群体内的所有序列中P.是人口遗传异质性的一个非常常见的概述统计。但是,计算挑战,因为它需要\(\ left({n ^ {2} - n} \右)/ 2 \)成对比较,然后计算平均值。使用凸船体,我们可以获得广告P.通过以下方式:

    $$广告{\ text {p}} = \ frac {{\ mathop \ sum \ nolimits_ {a = 1} ^ {l} \ mathop \ sum \ nolimits_ {i \ ne j} ^ {{}} f_ {aif_ {ai}}} {{\ left({n ^ {2} - n} \ revaly)/ 2}} $$

    在哪里N是序列的数量,L.是长度,位置数量,FAI.是核苷酸的频率一世在职位一种FAJ.是核苷酸的频率j在职位一种

  2. 2

    CC.H每个序列每个序列的平均距离H对于人口中的所有其他人来说,它的紧密性和中心性是一致的H,是衡量中心性的一个重要指标,也是计算上的一个挑战,这是我们需要做的\(\ left({n ^ {2} - n} \右)/ 2 \)两两比较,然后计算每个序列的平均值。利用凸壳,我们可以很容易地得到CCH通过以下方式:

    $$ CC_ {H} = \ mathop \ PROD \ limits_ {A = 1} ^ {1} F_ {A} $$

    在哪里L.是长度(数在MSA位置)和F一种是核苷酸存在于序列的群体频率H, 位置一种

  3. 3.

    两个群体间的平均距离汉明距离(广告pq)两个人群的所有序列中,P.Q在群体遗传学一个非常普遍的统计信息,对于遗传相关的一些措施的基础。但是,计算挑战,因为它需要\(p_ {n} * q_ {n} \)计算平均值前两两比较。使用凸包,正ADP.可使用获得:

    $$ AD {\文本{PQ}} = \压裂{{\ mathop \总和\ nolimits_ {A = 1} ^ {1} \ mathop \总和\ nolimits_ {I \ NEĴ} ^ {{}} {F_ PAI} {F_ QAI}}} {{N ^ {2}}} $$

    在哪里F是核苷酸的频率一世在职位一种在集合中P.FQAJ.是核苷酸的频率j在职位一种在集合中问:

  4. 4.

    两组之间所有距离的下限和上限数字1C显示了两个样本总体的凸包。在这个例子中,有两个位置的交点是空的,因此,在P.和任何序列问:必须是2或者更多。这是一个下界所有p和q的构件之间的距离。此指标有助于安全地丢弃任何人口成对比较如果它的值大于阈值T.更高。因此,两个群体之间的凸包距离P.问:,CHD.pq,可以通过:

    $$CHD{pq}=\mathop\sum\limits^{l}a$$

    在哪里一种如果任何核苷酸就位,则等于0一种一套P.也存在于集Q或等于1否则。如果CHD.pq > T, this pair of samples can be safely discarded.

在该示例中,有3个具有空或部分交叉点的位置,因此任何序列之间的距离P.和任何序列问:必须是3.或更少。这是的部件之间的上界的所有距离的P.问:

过滤性能

为了说明在所有序列对完整计算滤波方法的更高的效率,我们产生20个文件与序列的可变数目和应用两种算法。由CHD滤波器所用的时间的生长速度非常慢时,每个文件增加序列的数量,因为成对样品的比较的数量保持恒定,而在二次方式全距离法的增加(图2一种)。

图2
图2.

凸包距离(CHD)的性能。一种使用可变数量的序列比较20个文件所花费的时间。B.过滤的四种方法的性能的比较。C冠心病和实际最小距离(深灰色)在病毒数据集之间的差异的箱线图,以及在上界和所述最大距离(浅灰色)。D.在观察到的最小距离和CHD之间的分歧率,用于原始样本(连续线)和分成两个簇(虚线)的样品

对于病毒数据集,CHD过滤算法快速删除了96.2%的所有样本对,优于此处用于比较的其他三种算法(图。2b)。在病毒数据集中,CHD之间的平均分歧和实际最小距离仅为7.84%(图。2C),虽然上限和最大距离之间的分歧为2.3倍(18.32%)。

我们进行了模拟以测试CHD距离的性能,其具有100个不同水平的遗传异质性(图。2d).如预期的,差异越大,true minimal distance与CHD的差异越大。

K.-hulls性能

将每个人群分成集群创建比原件更低的多样性,这可以在CHD性能中提供升高。在这里,我们提出了一种将群体分成群集的新方法:修改版本K.-mode算法,其中该群集的模式(共识)替换簇的凸包,因此利用更多的信息。我们进行的模拟到测试中的表现K.-hull算法具有不同层次的聚类分离(图。3.a).每个模拟数据集包含2、3或4个真聚类。的K.在群落分离> 0.25时,发现在序列的分类中始终如一地校正。0.25的社区分离意味着在簇之间仅发现总变化的25%,并且75%的变异是随机的。

图3.
图3.

k-hulls性能。一种比较2、3或4簇的k壳和k模式。B.按聚类数计算的差距分数,100个随机模拟的平均值,社区间隔为0.4。C选择正确数量的簇的样品的分数

At community separations > 0.5, both theK.-mode和K.- 性能方面是平等的。但是,对于较低的社区分离价值,K.-hulls更准确地为6.8倍。我们观察到更高的敏感性是因为K.-hulls使用更多的数据(集群的所有序列,而不仅仅是其一致性),因此避免了集群分配中的许多关联。

尽管K-means家族的算法可以从随机起点进行多次,但是提出了一种启发式,以找到利用使用凸船壳计算的利用闭合中心的初始种子。为了评估其性能,我们使用了所有可能的种子组,并通过平均距离排列。有人发现,平均而言,我们的方法识别一组种子优于所有其他套装的99.9946%。

聚类的主要问题是选择簇的最优数量,因为簇质量总是提高(通过任何群集内或群集间测量)的簇的数量增加的难度。我们使用的差距统计[27.]选择最佳的聚类解决方案,就像具有相同大小的随机解决方案的不同。数字3.B显示了100个随机仿真的平均间隙分数如何(具有0.4的社区分离)随不同的集群解决方案而变化。对于每种真实簇(n = 2,3或4),正确的解决方案具有最高的差距分数。在各级社区分离中,我们发现,当社区分离> 0.35时,该方法倾向于选择正确的簇数。关于群集内的成员资格,我们发现几何平均显示出比由于关系数量的减少而比算术平均值更好。

K.-HCV数据集上的外壳

我们采用K.-将hulls算法应用于HCV和模拟数据集,以评估CHD的过滤性能。在HCV数据上,聚类可以正确过滤99.92%的样本对,这比没有聚类的情况(96.2%)有所改进。在没有真实聚类的模拟数据上,分为两组的强制聚类适度地改善了CHD性能,同时增加了很少的计算工作量(图。1d)。With low mutation rates (e.g. < 0.05), clustering improves the CHD performance by 2.4-fold. However, it must be considered that the performance of any filtering strategy would be benefited by splitting the population into clusters, but we only measured its effect on the CHD method.

讨论

hamming空间中的凸包是一种简单的数据结构,它可以有效地生成以下信息:(1)集合内的平均hamming距离,(2)两个集合之间的平均hamming距离(3) 每个序列的贴近度和中心度;(4)两组成员之间所有成对距离的上界和下界。这些度量通常通过测量所有可能的序列对来计算。这里描述的方法大大减少了准确计算这些度量所需评估的对的数量。虽然我们没有提供这些捷径的正式证明,但通过将其结果与使用完整计算得到的结果进行比较,对所有这些公式的正确性进行了测试,结果相同。这些比较是在所有数据集上进行的,包括真实HCV数据集和各种多样性水平的模拟数据集。

CHD过滤算法显示了研究方法中的最佳性能。CHD也是最简单的,这导致快速处理时间(桌面计算机上的<1s,以完成此处使用的任何数据集的分析)。此外,每个样本的凸壳生成一个非常小的文件,需要仅计算一次。存储此文件的存储需要最小的空间,使新文件存入数据库时​​,可以随时使用重复使用。

此处提出的CHD过滤策略适用于许多设置。它可用于通过基于阈值的方法检测病毒传输[7.]或可以被施加到与他们的迅速比较常见分类变量的数据的任何集合。

正如预期的那样,更大的多样性导致了真正最小距离和冠心病之间更大的差异。因此,冠心病对其他病毒数据集的过滤性能预计会受到高多样性的负面影响,例如,当患者感染> 1毒株时。然而,这种情况可以通过应用聚类算法来缓解。

通常,基因组序列或其他分类数据的聚类是使用以下方法对所有序列或变量对的距离矩阵进行的:

  1. (1)

    的相似性树(例如UPGMA)与聚类,其满足某些约束的水平的选择(例如自举支撑或差的阈值电平)。

  2. (2)

    基于距离矩阵的网络应用于网络的社区检测算法。

  3. (3)

    对应分析(如主成分分析,而是应用于使用距离矩阵的分类数据),其次应用于二次聚类算法。

可以应用于分类数据的不同方法类型是K.-模式算法[28.,这是K.- 用于群集具有分类值的大型数据集的算法。该算法通过计算每个位置的群集模式来工作。因此,将每个序列与集群的共识进行比较,而不是在连续数据中的质心相反。在这里,我们改进了K.- 用簇的凸壳替换共识来替换群集的算法,从而在社区分离弱时维护有关集群的更多信息并实现更高的精度(6.8x)。我们还表明,差距统计信息为选择最佳分区解决方案提供了一种有效的方法K.-hulls算法。

UDS的出现之前,病毒的传输的检测,根据每个患者单个病毒序列的系统发育分析。增加UDS从每个感染者帧内宿主病毒变异体的采样改善传输检测的灵敏度[7.]但是由非常增加待比较所需序列的数目扩增的计算负担。新的分子监控技术,如全球肝炎疫情和监测技术[29.]从许多感染的个体迅速产生和累积大量的宿主病毒型病毒体,呈现出显着的计算挑战,以及时准确地处理分子数据。据估计,美国2.0-2.8万人患有慢性HCV感染[30.].高效的分子监测对如此大的人口将需要对管理和分析快速增长的分子数据的能力来帮助制定公共卫生干预以控制和消除病毒疾病的能力。降低了由大规模数据引起的计算负担的计算方法,例如我们在此提出的方法,对于加强监督努力非常重要。

结论

我们提出了一种快速高效的过滤策略,大大减少了比较大型基因组序列所需的计算量。所提出的滤波算法在不同的领域中具有许多应用,处理了分类变量的大规模数据集的比较,例如分析用于检测传输和传输网络的主机内病毒型的序列。此外,这种方法在计算病毒群体的重要摘要度量方面是有效的。

方法

问题定义

给定p =(p1,P.2,......),每一个样品一世与集合S关联一世 = (S一世1,S.一世2,…)的同源序列,列举所有样本对(P一世,P.j)任何成对序列比较(s一世X,S.jy)汉明距离低于相关性阈值T(参见图11)。鉴于需要考虑每个序列对,它产生一个O(n2)算法,其中n为序列数。

病毒数据集

病毒数据集由来自401个HCV感染个体[获得先前公布的HCV序列的7.12.20.21.31.32.].UDS获得的序列编码HCV E1/E2连接(306 bp的扩增子,去除引物序列后为264 bp),包含HCV高变区1。平均每个样本的独特序列数为534.3。对于每个样本对,它的所有序列被用来创建一个多序列比对(MSA),然后用来计算每对序列之间的汉明距离。如果两个样本序列之间的汉明距离的最小值小于T,则认为这两个样本是相关的,在我们的例子中,T = 3.77% [7.].该病毒数据集中的所有样本对高于该阈值,因此彼此不相关,覆盖亚型内部和亚型之间的HCV分集(1A,1B,2A,3A和4A)。

性能比较

我们通过测试通过测试所有人口成对比较的百分比安全丢弃该方法的性能,因为它们不能具有任何具有汉明距离低于阈值的序列。该方法的基本原理是大多数样本对具有高度不同的序列(不相关,并且除去这些成对是有利的,以减少在一组样本中建立传输所需的计算量。每个样品-pair仍然认为,屈服于o(p2)算法,其中p为样本个数,但只进行一次比较,而不是所有序列对。我们将我们的性能与之前发布的三种算法进行了比较:

  1. (1)

    最大公共子串[20.,基于最大公共子串的下界,应用于K.- MAR Bloom过滤器。

  2. (2)

    汉明半径滤波器[20.],基于每个人口的汉明半径和三角形不等式。

  3. (3)

    签名方法[21.],基于比较K.即,K.-chunks每对序列的。

K.-Hulls聚类算法

利用聚类方法,可望提高凸包距离的性能。在这里,我们修改K.-模式算法[28.]通过用群集的凸壳替换共识群集,从而获得了有关群集的更多信息。该算法如下:

  1. 1

    选择所需的集群数量,K.

  2. 2

    找到k种子:

    1. 一种

      计算所有数据的凸孔

    2. B.

      第1种使用描述的紧密中心性公式(CC)计算每个序列的紧密中心性H)。最遥远的序列是第一个种子。

    3. C

      第二种子计算从第一种子到所有其他人的距离,并找出最遥远的。

    4. D.

      对于每一个额外的种子:计算前面的种子到所有其他序列的距离,并找到几何平均值最高的序列。

  3. 3.

    准备:

    1. 一种

      将每个序列转换为凸包格式。

    2. B.

      每个集群开始只是一粒种子。

  4. 4.

    虽然群集成员身份更改:

    1. 一种

      计算每个序列的凸包与每个簇的凸包之间的欧氏距离。

    2. B.

      将序列分配给最接近的群集并获取集群成员身份列表。

    3. C

      重新计算每个群集的凸壳。

为了找到最佳的群集数,我们使用了GAP分数[27.]以下面的方式:

  1. 1

    计算聚类解决方案的良好。对于每个群集上的每个位置,计算Shannon熵,然后在所有位置上平均。

  2. 2

    善“集群内”计算平均的(而不是“之间集群”)。

  3. 3.

    将这个值与1000个大小相同的随机分区通过gap评分得到的值进行比较。

  4. 4.

    选择最佳分数的解决方案。

模拟数据集

为了测试CHD和K-HULLS算法的性能,我们创建了几个具有不同程度的序列异质性和可变数量的真实集群的模拟数据集。用于测量的距离CHD遗传异质性的效果,5000模拟对文件的创建,用50个复制品用于突变率(100级)的每个电平,并与每对比较两个群体与模拟分集的相同的水平。

对于聚类算法,39,900模拟数据集被创建,用100个复制品的每个参数的组合。每个文件50个核苷酸长组成48个的序列,每个序列。序列可以被分离成2个,3个或4个真簇,用20个级别的社区分离的,范围从0.05至0.95。例如,只有5%的总变化的被集群和变化的95%之间发现的0.05手段社区分离是随机的。

数据和材料的可用性

数据和软件可根据要求提供。

缩写

HCV:

丙型肝炎病毒

UDS:

超深度测序

CHD:

凸壳距离

CC:

亲密的中心

脉宽调制:

位置重量矩阵

MSA:

多个序列对齐

广告:

平均距离

参考

  1. 1。

    Campo DS,Nayak V,Srinivasamoorthy G,Khudyakov Y.血液中循环的线粒体DNA熵与肝细胞癌有关。BMC Med Genom。2019; 12(4):74。

    文章CAS谷歌学术

  2. 2。

    SPADA E,ABBATE I,Sicurezza E,Mariano A,Parla V,Rinnone S,Cuccia M,Capobianchi Mr,Mele A.意大利血液透析装置丙型肝炎病毒爆发的分子流行病学。J Med Virol。2008; 80(2):261-7。

    文章CAS谷歌学术

  3. 3。

    布拉科马,戈萨尔贝斯MJ,布拉斯科D,莫亚A,冈萨雷斯坎德拉F。血液透析病房丙型肝炎病毒爆发的分子流行病学。临床微生物学杂志。2005;43(6):2750–5.

    文章CAS谷歌学术

  4. 4.

    冈萨雷斯·坎德拉F、布拉科·马、沃贝尔B、莫亚A。法庭上的分子进化:从进化来源分析大规模丙型肝炎病毒爆发。BMC生物。2013;11:76.

    文章谷歌学术

  5. 5。

    Prosperi Mc,De Luca A,DI Giambenedetto S,Bracciale L,Fabbiani M,Cauda R,Salemi M.该阈值自初群集:在分子Quasispecies中查找家庭或传输群集的新方法。Plos一个。2010; 5(10):E13619。

    文章CAS谷歌学术

  6. 6。

    Feray C,BouscaillouĴ,Falissard B,穆罕默德MK,阿拉法N,贝克尔I,埃尔 - Hoseiny男,达利ME,埃尔 - Kafrawy S,Plancoulaine S,等人。一种新颖的方法来识别丙型肝炎病毒传播途径。Plos一个。2014; 9(1):e86098。

    文章CAS谷歌学术

  7. 7。

    Campo D,夏G,Dimitrova Z,Lin Y,Ganova-Raeva L,Punkova L,Ramachandran S,Thai H,Sims S,Rytsareva I等。揭发环境中丙型肝炎病毒传输的准确遗传检测。j感染dis。2015; 213(6):957-65。

    文章谷歌学术

  8. 8。

    Nainan O、Alter M、Kruszon Moran D、Gao F、Xia G、McQuillan G、Margolis H。美国普通人群调查参与者的丙型肝炎病毒基因型和病毒浓度。胃肠病学。2006;131(2):478–84.

    文章CAS谷歌学术

  9. 9。

    汤普森N、诺瓦克R、怀特康斯托克M、夏G、加诺瓦·雷瓦L、拉马钱德兰S、胡迪亚科夫Y、比亚莱克S、威廉姆斯I。血液透析病房感染控制违规相关的丙型肝炎病毒患者间传播。肾治疗学杂志。2012;S10:002。

    谷歌学术

  10. 10

    Ganova-LM Raeva,季米特洛娃ZE,坎普DS,林Y,拉马钱德兰S,夏GL,Honisch C,康托尔CR,Khudyakov YE。通过使用DNA质谱丙型肝炎病毒传输的检测。j感染dis。2013; 207(6):999-1006。

    文章CAS谷歌学术

  11. 11.

    Ramachandran S,Purdy Ma,Xia Gl,Campo DS,Dimitrova Ze,Teshale EH,Teo Cg,Khudyakov Ye。美国乙型肝炎病毒的近期人口扩展。J病毒。2014; 88(24):13971-80。

    文章CAS谷歌学术

  12. 12.

    Rytsareva I,坎普DS,郑Y,模拟人生S,Thankachan SV,Tetik C,奇拉格Ĵ,Chockalingam SP,苏A,Aluru S,等人。有效检测与下一代测序数据的病毒传输。BMC基因组。2017; 18(增刊4):372。

    文章谷歌学术

  13. 13。

    秦杰,王文,鲁y,小c,林X.具有非对称签名方案的高效精确编辑相似查询处理。:ACM SIGMOD数据管理国际会议,SIGMOD'11:2011;纽约,p。1033-1044(2011)。

  14. 14。

    Gionis A,Indyk P,Motwani R.相似性在高尺寸上通过散列搜索。:第25届关于非常大型数据库的国际会议,VLDB'99 1999. Morgan Kaufmann Publishers Inc.,旧金山,CA,P。518-529(1999)

  15. 15.

    Li C,王B,杨X.Vgram:使用可变长度克提高字符串集合对近似查询的性能。:第33届关于非常大的数据库国际会议,VLDB '07 2007;维也纳,p。303-314(2007)。

  16. 16。

    关键词:高通量测序,非均匀覆盖,误差修正生物信息学。2011;27(13):137 - 41。

    文章CAS谷歌学术

  17. 17。

    Nikolenko S,Korobeynikov A,Alekseyev M. Bayeshammer:贝叶斯群体用于单细胞排序中的纠错。BMC基因组。2013; 14(1):7。

    文章谷歌学术

  18. 18。

    Broder A,Glassman S,Manasse M,Zweig G. Web的句法聚类。计算NetW ISDN Syst。1997年; 29(8-13):1157-66。

    文章谷歌学术

  19. 19。

    Altschul S,Gish W,Miller W,Myers E,Lipman D.基本的本地对准搜索工具。J Mol Biol。1990年; 215(3):403-10。

    文章CAS谷歌学术

  20. 20

    Rytyareva I,Campo D,Zheng Y,Sims S,Tetik C,Chirag J,Chockalingam S,Chinnhachan S,Sue A,Aluru S等人。基于阈值的方法有效地检测病毒传输。:5日,生物与医学科学(ICCAB):5日国际计算进展国际会议:2015年10月15日至17日;迈阿密,佛罗里达州,美国(2015)

  21. 21

    TSYVINA V,Campo DS,SIMS S,Zelikovsky A,Khudyakov Y,Skums P.在密切相关的基因组变体的异质群体成员之间的快速估计遗传相关性。BMC生物素。2018; 19(41):360。

    文章CAS谷歌学术

  22. 22

    德伯格男,面包车Kreveld男,奥维马斯男,施华蔻O.计算几何:算法和应用。柏林:斯普林克;2008年。

    谷歌学术

  23. 23。

    艾根M.从陌生简单性复杂的熟悉:对物质,信息,生活和思想的论文。牛津:牛津大学出版社;2013年。

    谷歌学术

  24. 24。

    莫拉格里奥A。进化算法的几何统一。科尔切斯特:埃塞克斯大学;2007

    谷歌学术

  25. 25。

    斯托莫GD、施耐德TD、黄金L、埃伦费赫特A。使用“感知器”算法区分大脑中的翻译起始位点大肠杆菌. 核酸研究,1982年;10(9):2997–3011.

    文章CAS谷歌学术

  26. 26。

    尔霍宁Ĵ,Martinmaki P,皮兹C,拉斯塔派P,Ukkonen E. MOODS:快速搜索在DNA序列位置权重矩阵的匹配。生物信息学。2009; 25(23):3181-2。

    文章CAS谷歌学术

  27. 27。

    Tibshirani R,Walther G,Hastie T.估计通过差距统计数据集的数据中的簇数。J R统计SOC B. 2001; 63:411-23。

    文章谷歌学术

  28. 28。

    Huang Z.延伸到K-Means算法,用于将大数据集与分类值进行聚类。数据最小知识Discov。1998年; 2(3):283-304。

    文章谷歌学术

  29. 29。

    Longmire A、Sims S、Rytsareva I、Campo D、Skums P、Dimitrova Z、Ramachandran S、Medrzycki M、Thai H、Ganova Raeva L等。GHOST:全球肝炎暴发和监测技术。基诺姆。2017;18(补编10):916。

    文章CAS谷歌学术

  30. 30.

    Hofmeister Mg,Rosenthal Em,Barker Lk,Rosenberg ES,Barranco Ma,Hall EW,Edlin Br,Mermin J,Ward JW,Ryerson Ab。估计美国丙型肝炎病毒感染的患病率,2013 - 2016年。肝脏。2019; 69(3):1020-31。

    文章谷歌学术

  31. 31

    威廉姆斯I.美国丙型肝炎的流行病学。我是J Med。1999; 107(6B):2S-9S。

    文章CAS谷歌学术

  32. 32

    Campo DS,Dimitrova Z,Yamasaki L,Skums P,Lau Dt,Vaughan G,Forbi JC,Teo Cg,Khudyakov Y.下一代测序显示了主机内HCV变体的大型连接网络。BMC基因组。2014; 15(SLOP 5):S4。

    文章谷歌学术

下载参考

关于这个补充剂

本文已作为BMC生物信息学的一部分发布21卷补充18,2020:第8次研讨会的诉讼程序欧宝娱乐合法吗分子流行病学计算进展(来自2019年)。补充的完整内容可在线提供//www.christinemj.com/articles/supplements/volume-21- supplement-18

基金

研究和收集,分析或数据的或书面的稿件解释的设计:所有的工作和出版费用由美国疾病控制和预防,其中有中没有的角色资助。

作者信息

隶属关系

作者

贡献

DSC设计了这项研究。DSC设计并实现了凸包滤波器,DSC和YK分析了数据并撰写了文稿。所有作者阅读并批准了最终的手稿。

通讯作者

对应于David S. Campo

伦理宣言

伦理批准和同意参与

根据疾病控制和预防的机构审查委员会批准进行了研究。本报告中的调查结果和结论是作者的结果,不一定代表疾病控制和预防中心的官方立场。

同意出版物

用内部CDC间隙系统获得同意出版。

利益争夺

作者宣称他们没有任何竞争的利益。

附加信息

出版商的注意事项

欧宝体育黑玩家Springer Nature在发表地图和机构附属机构中的司法管辖权索赔方面仍然是中立的。

权利和权限

开放访问本文是基于知识共享署名4.0国际许可,允许使用、共享、适应、分布和繁殖在任何媒介或格式,只要你给予适当的信贷原始作者(年代)和来源,提供一个链接到创作共用许可证,并指出如果变化。本文中的图像或其他第三方材料都包含在本文的知识共享许可中,除非在该材料的信用额度中另有说明。如果资料不包括在文章的知识共享许可协议中,并且你的预期用途没有被法律规定允许或超过允许用途,你将需要直接从版权所有者获得许可。如欲查阅本许可证副本,请浏览http://creativecommons.org/licenses/by/4.0/。Creative Commons公共领域奉献豁免(http://creativecommons.org/publicdomain/zero/1.0/)适用于本文中提供的数据,除非另有用入数据的信用额度。

重印和权限

关于这篇文章

通过Crossmark验证货币和真实性

引用这篇文章

hamming空间中的凸包能够有效地搜索基因组序列的相似性和聚类。欧宝娱乐合法吗21,482(2020)。https://doi.org/10.1186/s12859-020-03811-z

下载引用

关键词

  • 人口的距离
  • 汉明
  • 聚类
  • 居民
\