CN108779491B - 用于全基因组序列数据的从头组装的系统、方法和介质 - Google Patents

Abstract

描述了用于从个体的核酸样品生成的核酸序列数据的从头定相二倍体组装的计算机实现的方法、系统和介质，所述核酸序列数据利用核酸标签来保留所述个体的长程序列环境，以使得从共同起始序列导出的短读取序列数据的子集共享共同标签。所述定相的二倍体组装在不与源自除所述个体以外的生物体的参考序列比对的情况下实现。所描述的方法、系统和介质是计算机资源有效的，从而允许按比例放大。

Description

用于全基因组序列数据的从头组装的系统、方法和介质

交叉引用

本申请要求2016年2月11日提交的美国申请序列号62/294,184和2016年5月6日提交的美国申请序列号62/332,914的权益，所述申请两者均特此以引用的方式整体并入。

背景技术

基因组测序在医学、法医学和生物技术领域具有广阔的前景。已经基于不同的测序化学开发了多种DNA测序方法，并且进行基因组测序的机器已经变得更加稳健且有效。在技术上，可获取原始基因组数据的速度超过了将这种原始数据组装成基因组—特别是二倍体或多倍体基因组的能力。当前的序列组装方法是复杂的，需要大量处理器能力，并占用大量内存。

发明内容

确定个体活生物体或组织的基因组序列对生物学和医学具有基本重要性。几十年的研究已经产生了大量针对这一问题的实验室方法和计算方法。这些方法在它们的总体实验负担(包括输入DNA量、成本、复杂性和时间线)上差别很大，其还更大的负担倾向于产生更高质量的基因组序列。

在低端，一些方法对DNA的短片段进行测序，然后将所得读取段(reads)与来自同一物种的单倍体参考序列进行比对，以鉴定与所述参考序列的差异，从而部分推断样品的序列。所述方法已被各自用于产生并分析超过一千份人样品，从而跨群体产生极其深入的信息。然而，这些方法可能因参考比较而具有内在偏差，并且通常不能鉴定对给定样品来说新颖或代表大规模变化的序列，也不能区分亲本等位基因上的变化。

相比之下，数据(通常来自长DNA片段)可在称为从头组装、而不利用参考序列并且对于大型且复杂的基因组来说特别困难的方法中合成。核心挑战是高度相似序列的正确表示。一个特别强大的实例出现在真核生物中，其中有性生殖有助于母本和父本染色体“拷贝”。虽然这些拷贝对于长链段将是非常相似的，但一些区域可具有巨大差异，从而不仅导致小规模差异，而且常常导致基因拷贝数差异。由于同源染色体编码单独的基因拷贝，因此需要了解其单独序列以理解表型。

然而即使对于高端从头实验室制剂来说，所述领域的标准是在计算上编织同源染色体，从而为每个基因座产生通常在自然界中不存在的单个单倍体共有序列。更好的是，将产生单倍体组装体以及两种起源染色体之间的差异的分阶段目录。

通过以非常低的实验负担创建真实二倍体，从头组装体，本文提供的公开内容缩小了低端方法与高端方法之间的差距。所公开的技术还基于使用自动微流体系统的基因组分区。所述技术能够从一个文库生成组装体项目的全部数据。此外，所公开的方法从约1纳克的高分子量DNA开始，其比替代方法小约一百万倍。有利地，数据的成本在基于读取比对的低端方法的范围内，并且组装不需要专门知识，因为所述方法是自动的。

本公开提供了使用短DNA序列读取段将全基因组测序读取段从头组装成完整基因组的平台、系统、媒介和方法。所述方法与任何短读取测序技术兼容。本文描述的方法有利地用于将重叠群“定相”成更大的序列区块并解析基因组结构变异，如大的插入缺失、重复和易位。

与其他短读取组装技术和长读取技术如单分子实时(SMRT)测序相比，本公开的方法具有许多优点。所述优点中的一些包括：输入DNA减少、对序列覆盖率的要求减少、组装时间减少、处理要求减少、由于能够在商品化的计算机资源上运行而具有商业可扩展性以及效率和成本效益的总体提高。例如，与利用SMRT技术的太平洋生物科学公司(PacificBiosciences)(PacBio)的FALCON汇编器相比，本公开的方法允许处理能力降低近180倍并且存储器利用率降低21倍。另外，长读取测序技术受到技术的平均读取长度如10-20kb的限制。本文描述的技术已经显示产生在85-105kb范围内的完全定相的重叠群和长度至少5Mb的完全定相的序列区块。

在一方面，本文公开了一种用于从生物体的核酸样品生成的核酸序列数据的从头基因组组装的计算机实现的方法，所述方法包括：由一台或多台计算机生成基于短读取序列数据的初始组装体，所述初始组装体包括一个或多个未解析的序列模糊性区域，其中所述短读取序列数据是从来自核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，以使得从共同起始序列导出的所述短读取序列数据的子集共享共同标签；通过利用所述标签来解析多个序列模糊性区域，由所述一台或多台计算机生成基于所述初始组装体的多个局部组装体；由所述一台或多台计算机生成基于所述多个局部组装体的全局组装体；通过移除与由所述标签指示的长程序列环境不一致的序列数据，由所述一台或多台计算机清除所述全局组装体；并且通过利用所述标签来分离定相的核苷酸序列，由所述一台或多台计算机生成基于所述全局组装体的定相基因组组装体；其中，在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。在某些实例中，所述基因组是二倍体。在某些实例中，所述短读取序列数据从单个测序文库生成。在某些实例中，所述短读取序列数据产生所述生物体的基因组的50x或更低覆盖率。在某些实例中，对所述短读取序列数据进行标记以保留在比所述读取段长2x–1000x的起始序列内的环境。在某些实例中，对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。所述初始组装体可以是初始组装图。在某些实施方案中，通过以下方式来生成初始组装图：鉴定在所述生物体的基因组中存在的概率高的多个k-聚体；使用所述标签来基于每个k-聚体出现的起始序列的数量来过滤所述多个k-聚体；并且将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。所述方法还可包括通过以下方式由所述一台或多台计算机修订初始组装图：基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；并且通过咨询原始短读取序列数据来填充所述初始组装图中的空位。K可以是介于24与96之间。可通过以下方式来生成多个局部组装体：使用所述初始组装图作为临时参考；鉴定明确序列的边缘；鉴定共享在阈值数量的标签以上的多个标签的相邻边缘；并且将明确序列的边缘与所鉴定的相邻边缘汇集在一起。可通过以下方式来产生全局组装体：鉴定所述多个局部组装体中在所述生物体的基因组中存在的概率高的多个z-聚体，其中z>k；并且将所述多个局部组装体中的z-聚体汇集在一起。Z可以是介于100与300之间。可从少于10ng的DNA输入材料生成短读取序列数据。可从少于2ng的DNA输入材料生成短读取序列数据。在一些实施方案中，所述组装可在不到60分钟内完成。在这些实施方案中，所述一台或多台计算机可包括小于512GB的存储；在某些实施方案中，所述一台或多台计算机可包括小于60GB的存储。在某些实例中，所述组装在不到20分钟内完成。在这些实例中，所述一台或多台计算机包括小于512GB的存储。在某些实例中，所述一台或多台计算机包括小于60GB的存储。在某些实例中，所述生物体是人类。在某些实例中，所述DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。在某些实例中，所述一台或多台计算机占用一立方英尺或更小的物理空间。

在另一方面，本文公开了一种计算机实现的系统，所述系统包括：数字处理装置，所述数字处理装置包括：至少一个处理器；操作系统，所述操作系统被配置用于执行可执行指令；存储器；以及计算机程序，所述计算机程序包括可由所述数字处理装置执行以创建从生物体的核酸样品生成的核酸序列数据的从头基因组组装应用程序的指令，所述应用程序包括：第一软件模块，所述第一软件模块生成基于短读取序列数据的初始组装体，所述初始组装体包括一个或多个未解析的序列模糊性区域，其中所述短读取序列数据从来自所述核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，以使得从共同起始序列导出的所述短读取序列数据的子集共享共同标签；第二软件模块，所述第二软件模块通过利用所述标签来解析多个序列模糊性区域而生成基于所述初始组装体的多个局部组装体；第三软件模块，所述第三软件模块生成基于所述多个局部组装体的全局组装体；第四软件模块，所述第四软件模块通过移除与由所述标签指示的长程序列环境不一致的序列数据而清除所述全局组装体；以及第五软件模块，所述第五软件模块通过利用所述标签来分离同源定相的核苷酸序列而生成基于所述全局组装体的定相的基因组组装体；其中，在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。在某些实例中，所述基因组是二倍体。在某些实例中，所述短读取序列数据从单个测序文库生成。在某些实例中，所述短读取序列数据产生所述生物体的基因组的50x或更低覆盖率。在某些实例中，对所述短读取序列数据进行标记以保留在比所述读取段长2x–1000x的起始序列内的环境。在某些实例中，对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。在某些实例中，所述初始组装体是初始组装图。在某些实例中，所述生成初始组装图的软件模块通过以下方式来生成所述初始组装图：鉴定在所述生物体的基因组中存在的概率高的多个k-聚体；使用所述标签来基于每个k-聚体出现的起始序列的数量来过滤所述多个k-聚体；并且将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。在某些实例中，所述生成初始组装图的软件模块通过以下方式来修订所述初始组装图：基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；并且通过咨询原始短读取序列数据来填充所述初始组装图中的空位。K可以是介于24与96之间。可通过以下方式来生成多个局部组装体：使用所述初始组装图作为临时参考；鉴定明确序列的边缘；鉴定共享在阈值数量的标签的以上的多个标签的相邻边缘；并且将明确序列的边缘与所鉴定的相邻边缘汇集在一起。可通过以下方式来产生全局组装体：鉴定所述多个局部组装体中在所述生物体的基因组中存在的概率高的多个z-聚体，其中z>k；并且将所述多个局部组装体中的z-聚体汇集在一起。Z可以是介于100与300之间。可从少于10ng的DNA输入材料生成短读取序列数据。可从少于2ng的DNA输入材料生成短读取序列数据。在某些实例中，所述组装在不到60分钟内完成。在一些实施方案中，所述组装可在不到60分钟内完成。在这些实施方案中，所述一台或多台计算机可包括小于512GB的存储；在某些实施方案中，所述一台或多台计算机可包括小于60GB的存储。在某些实例中，所述组装在不到20分钟内完成。在这些实例中，所述一台或多台计算机包括小于512GB的存储。在某些实例中，所述一台或多台计算机包括小于60GB的存储。在某些实例中，所述生物体是人类。在某些实例中，所述DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。在某些实例中，所述数字处理装置占用一立方英尺或更小的物理空间。

在另一方面，本文公开了一种用计算机程序编码的非暂时性计算机可读存储介质，所述计算机程序包括可由处理装置执行以创建从生物体的核酸样品生成的核酸序列数据的从头基因组组装应用程序的指令，所述应用程序包括：第一软件模块，所述第一软件模块生成基于短读取序列数据的初始组装体，所述初始组装体包括一个或多个未解析的序列模糊性区域，其中所述短读取序列数据从来自所述核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，以使得从共同起始序列导出的所述短读取序列数据的子集共享共同标签；第二软件模块，所述第二软件模块通过利用所述标签来解析多个序列模糊性区域而生成基于所述初始组装体的多个局部组装体；第三软件模块，所述第三软件模块生成基于所述多个局部组装体的全局组装体；第四软件模块，所述第四软件模块通过移除与由所述标签指示的长程序列环境不一致的序列数据而清除所述全局组装体；以及第五软件模块，所述第五软件模块通过利用所述标签来分离同源定相的核苷酸序列而生成基于所述全局组装体的定相的基因组组装体；其中，在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。在某些实例中，所述基因组是二倍体。在某些实例中，所述短读取序列数据从单个测序文库生成。在某些实例中，所述短读取序列数据产生所述生物体的基因组的50x或更低覆盖率。在某些实例中，对所述短读取序列数据进行标记以保留在比所述读取段长2x–1000x的起始序列内的环境。在某些实例中，对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。在某些实例中，所述初始组装体是初始组装图。在某些实例中，所述生成初始组装图的软件模块通过以下方式来生成所述初始组装图：鉴定在所述生物体的基因组中存在的概率高的多个k-聚体；使用所述标签来基于每个k-聚体出现的起始序列的数量来过滤所述多个k-聚体；并且将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。在某些实例中，所述生成初始组装图的软件模块通过以下方式来修订所述初始组装图：基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；并且通过咨询原始短读取序列数据来填充所述初始组装图中的空位。K可以是介于24与96之间。可通过以下方式来生成多个局部组装体：使用所述初始组装图作为临时参考；鉴定明确序列的边缘；鉴定共享在阈值数量的标签以上多个标签的相邻边缘；并且将明确序列的边缘与所鉴定的相邻边缘汇集在一起。可通过以下方式来产生全局组装体：鉴定所述多个局部组装体中在所述生物体的基因组中存在的概率高的多个z-聚体，其中z>k；并且将所述多个局部组装体中的z-聚体汇集在一起。Z可以是介于100与300之间。可从少于10ng的DNA输入材料生成短读取序列数据。可从少于2ng的DNA输入材料生成短读取序列数据。在某些实例中，所述组装在不到60分钟内完成。在一些实施方案中，所述组装可在不到60分钟内完成。在这些实施方案中，所述一台或多台计算机可包括小于512GB的存储；在某些实施方案中，所述一台或多台计算机可包括小于60GB的存储。在某些实例中，所述组装在不到20分钟内完成。在这些实例中，所述一台或多台计算机包括小于512GB的存储。在某些实例中，所述一台或多台计算机包括小于60GB的存储。在某些实例中，所述生物体是人类。在某些实例中，所述DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。在某些实例中，所述数字处理装置占用一立方英尺或更小的物理空间。

附图说明

图1示出使用本公开的方法生成的比对的非限制性实例，其保留关于SNP和结构变体两者的信息。

图2示出基因组组装过程的非限制性实例。

图3示出具有巨大气泡和微结构的基因组组装过程的替代示意性图示的非限制性实例。

图4示出基因组组装过程的非限制性实例。

图5示出可从基因组组装过程获得的输出的非限制性实例。

图6示出数字处理装置的非限制性示例；在这种情况下，所述数字处理装置是具有一个或多个CPU、存储器、通信接口和显示器的装置。

图7示出从头组装的非限制性实例。

图8示出长同聚物附近的优势误差的非限制性实例。

图9示出从头汇编器的计算体系结构的非限制性实例。

具体实施方式

某些定义

除非另外定义，否则本文使用的所有技术术语具有与本发明所属领域的普通技术人员通常理解的相同的含义。如本说明书以及随附权利要求中所用，除非上下文另外明确指示，否则单数形式“一个/种(a/an)”和“所述”包括复数提及形式。除非另有说明，否则本文对“或(or)”的任何提及意图涵盖“和/或(and/or)”。

如本文所用，“定相的”组装体或序列是指创建其中将核苷酸数据精确地顺式置于特定基因座如染色体或其他亚基因组间隔处的组装体。这可包括例如正确地解析单倍型、二倍体基因组、多倍体基因组、不同样品、不同细胞、不同生物体或甚至单倍体基因组的结构变体如大插入缺失、易位和融合。

如本文所用，“下一代测序”是指在24小时周期内产生大量核苷酸序列数据(通常大于1千兆碱基)的任何技术。非限制性示例系统可从Illumina(San Diego,CA)、LifeTechnologies(Carlsbad,CA)和Pacific Biosystems(Menlo Park,CA)获得。

从头组装的优点

本公开涉及用于获得并分析来自生物样品的基因组信息的新颖方法，所述方法允许如此导出的序列数据的改进的遗传组装。具体地说，本文描述的方法、系统和介质涉及测序文库的制备，所述测序文库被编码以保留个体的长程序列环境，以及如通过给定序列系统输出的确定的序列信息的更短链段(在本文中称为“读取段”)。这种长程序列环境允许在比个体读取段的长度更长的序列环境下(例如，2x、5x、10x、100x、1000x)或甚至更长的连续序列链段以及这些之间的任何长度范围内对读取段进行排序，无论长度如何。此类长程环境可在大约10kb、100kb、200kb、500kb、1Mb、2Mb、3Mb、4Mb、5Mb或甚至更长以及这些之间的任何长度范围的连续序列链段内。

通过提供这种长程序列环境，可鉴定通常可从长的连续序列链段导出的序列特征，如鉴定大规模结构变异、确定单倍型信息等。所有这些益处在能够准确组装真实基因组序列以及此外真实二倍体或多倍体基因组序列中特别有用，无论是从参考序列操作还是从头组装特定二倍体基因组。本文描述的平台、系统、介质和方法提供了在先前测序和从头组装方法中一直缺乏的益处，所述益处包括使用：(i)非常少量的输入，(ii)较低的序列覆盖率，(iii)低成本以及(iv)计算效率。

本文描述的平台、系统、介质和方法允许将单个测序文库组装成完整基因组。从含有至少一个整个基因组、染色体或DNA片段的DNA样品开始创建测序文库。然后通过将所述DNA分段成通常大于1千碱基、通常大于10、50或100千碱基的大片段来制备DNA。然后对这些区段进行物理分区，其中每个分区包含DNA片段和用于鉴定所述DNA片段的独特条形码或标签，以及从较大片段生成的任何较小片段。所述条形码可包括于寡核苷酸上。所述寡核苷酸可以可释放地连接至固体结构，如珠粒或微囊。在一些实施方案中，所述寡核苷酸可包含随机序列、与靶序列互补的序列、用于引物连接的序列或通用引发位点。

一旦用独特的标签对大DNA片段进行分区，就生成并入所述标签的较小片段，然后将所述较小片段汇集到文库中并进行测序。所述文库可通过任何下一代测序技术进行测序。在某些实施方案中，作为非限制性实例，通过焦磷酸测序、通过合成测序、通过连接测序、离子半导体测序或单分子实时测序来生成DNA序列数据。在某些实施方案中，通过能够每24小时时期生成1千兆碱基核苷酸读取段的任何技术来生成DNA序列数据。

通过拥有来自各种片段及其相关条形码序列的读取段的序列数据，可从头执行更大序列的组装。测序反应和组装步骤不必由同一个体或实体进行。可从第三方获得序列数据。如本文所述，这可以保持计算效率、同时允许完成复杂组装过程的方式完成。在美国专利申请号14/175,935中描述了对核酸分子进行分段、分区和标记的示例性方法，所述专利申请的全部公开内容以引用的方式整体并入本文。

为了识别所有类型的变体，原则上可将所述组装体与参考序列进行比对，且然后读出所述变体。对组装体进行比对具有比对读取段进行比对显著更大的特异性，从而消除与基于标准参考的分析相关的大多数伪像。图1是来自HGP组装体的一个实例。它示出SNP、一个等位基因上的两个小插入和554碱基插入。另一个等位基因显示相同的插入。GenBank没有BLAST命中。如果代替查看NA12878，则发现相同的插入，但仅在一个等位基因上。

计算效率

当从短读取序列数据组装基因组环境时，最终组装体是样品、细胞或不同单倍型/染色体的共有序列组装体。因此，即使从长程序列创建基因组的真实二倍体组装体迄今为止在很大程度上也是不可能的。具体地说，这些组装体通常可呈现二倍体基因组的平均组装体，而不是特异性鉴定单倍体变体。根据本文所描述的方法，可获得另外同源的基因座(例如，来自每种单倍型、染色体、细胞或样品)的不同变体的单独组装体。

由于较短序列读取段的性质和计算密集的组装过程，传统的组装过程对计算基础结构施加巨大压力。在一些情况下，如本文所描述，采用具有比常规使用的那些计算过程显著更有效的计算过程的方法。具体地说，在本文描述的方法中，制备初始组装图。这种初始组装体相当于“草图”组装体并且暂时忽略未解析的复杂性区域，例如，在第一眼看上去可能是模糊的区域，从而保持计算能力。一旦创建了这种初始组装体，然后就可通过使用条形码化的测序数据来进一步处理模糊性区域，以创建模糊性区域的精确组装体。这允许从在组装过程期间创建的测序读取段导出的k-聚体可寻址到某一染色体、细胞、群体、单倍型等。这允许有效地解析模糊性–通过降低组装中的总体复杂性–从而节省计算资源，如RAM、ROM或处理器周期。在某些实施方案中，本文描述的方法可将组装所需的RAM的量减少至512、256、128、64、32、16、8或4千兆字节以下。

使用条形码化的分段核酸通过使从序列读取段导出的k-聚体置于环境中而有助于基因组序列的有效组装。作为举例，在不使用条形码的常规组装过程中，在清除全局组装体之后，所述全局组装体中的大多数基因座将代表两个或更多个染色体基因座(例如，母本遗传的和父本遗传的染色体)。使用所述条形码，这些基因座现在彼此分开。这一过程将分离同源染色体并且还解析复杂的区段重复。这在图2中示意性地示出。如所示，示出部分组装的序列，其中一个或多个未组装的部分由方框表示(步骤I)。使用邻域组装来利用条形码化或加标记的相邻序列以到达黑盒中来提供其中的序列组装。此外，在所述序列代表不同的单倍型或定相的序列信息的情况下，例如，如双箭头所示(步骤II)，这些条形码也将告知，在这些区域内产生例如单独的变体组装体。从所述单独组装体，可在同源基因座处生成真实的二倍体组装体(步骤III)。将条形码化的读取段放回到所述组装体上，并且鉴定其确切序列未确定已知的基因座并且如此标记。现在将全局组装图与参考序列进行比对。对第一边缘进行单独比对。在这些比对不一致的情况下(在两个边缘相交的点处)，通过对这些边缘的拼接进行比对来解析不一致性。参考比对连同质量标记现在暗示所有类型的变体(单碱基和结构)的特定等位基因的存在或不存在–以及必要时的不确定性。这是由传统的以参考为中心的方法尝试的变体调用的“正确”型式。可将两种或更多种相关样品组装在一起，从而产生单个图，从所述图中可推断出在每个基因座处所述样品之间的准确关系。这包括肿瘤和正常的情况(例如，来自一种混合的临床样本)，以及通过对家族进行测序观察到的儿童中的新生突变(包括重组)的情况。直接比较将揭示参考序列中不存在的基因座中的差异。

在本文描述的某些实现方式中，使用短读取段核苷酸测序技术来创建初始从头组装体。这种从头组装体可基于短读取序列数据。所述短读取序列数据可来自少于300、250、200、150、100、75或50个碱基对的读取段，包括其中的增量。所述短读取序列数据可来自配对端读取段。可以导致与基因组大小相比较小的存储使用的方式创建初始从头组装图。这样可优化初始组装的速度。存储使用不会随输入数据量成比例增加。所述技术的关键是：

(a)基于频率和碱基质量得分，鉴定在基因组中存在的概率高的k-聚体–这些k-聚体的数量因此由基因组大小决定。

(b)K-聚体在生成过程中通过将共享共同最小p-聚体(p<k)的那些k-聚体汇集在一起而自然地合并-这使存储使用降低一个数量级。

(c)随后的组装操作将初始组装体视为临时“参考序列”，并且因此具有非常低的存储要求。

给定所述组装体中表示样品中的未分支序列的边缘e，找到其相邻边缘-这些是与e共享最少量的条形码的边缘。在某些实施方案中，所述边缘共享至少1、2、3、4、5、6、7、8、9或10个条形码序列。然后连续地组装这些序列，从而产生局部组装体(邻域)。这一过程还填充了初始组装体中缺失的空位。然后使用非常大的k-聚体值组装所有邻域。所得到的组装体再次是图。现在通过移除与条形码不一致的连接来清除全局组装体。

组装方法

从短序列读取段(读取k-聚体)生成的k-聚体近似将通过沿着完美k-聚体匹配折叠样品基因组而获得的图。可执行预滤波以排除可能错误的读取k-聚体，因为例如它们仅出现在一个条形码中，或者具有低质量得分或者在读取段中罕见。然后，从所述k-聚体构建初始图。将此图的边缘用DNA序列标记，从而表示De Bruijn图中的未分支路径(称为“单路径”)。接下来，可在此图上执行修补空位。最后，可从所述图中修整“悬挂端”，从而生成初始组装体。

用于组装所述初始组装体的读取k-聚体可以是任何有助于组装的长度，并且可根据正组装的基因组的大小而变化。所述读取k-聚体可大于1、10、20、30、40、40、60、70、80、90或100个碱基对，包括其中的增量。在某些实例中，所述读取k-聚体可少于10、20、30、40、40、60、70、80、90或100个碱基对，包括其中的增量。通常，介于30与50个碱基对之间的k-聚体对于初始从头组装体来说是理想的。在某些实例中，所述k-聚体可介于40与50个碱基对之间。所述k-聚体的长度可以是40、41、42、43、44、45、46、47、48、59或50个碱基对。理想地，所述k-聚体是四的倍数。

在创建初始组装体后，构建新的全局组装体(超图)。所述超图的边缘通过初始组装体中的路径标记(并且因此表示为整数序列)。在形式上，此图具有与初始组装体中相同的K值，但是被解析为更高的K值。这通过在基图中找到为读取对的闭包的路径来实现，所述路径因此具有大约100、200、300、400或500k-聚体的长度。将这些路径沿着长完美重叠在形式上比对以产生超图。这些第二较大k-聚体被表示为z-聚体。

在全局组装体后，使用条形码来定位和填充空位。由于在De Bruijn图的单路径中的分支点，可将空位可视化为发散的“气泡”。参考图3，每个支架均具有巨大气泡，从而表示所述组装体的完全定相部分。连续的巨大气泡不是相对于彼此定相的。一般来说，所述支架图中所示的每个边缘包含在其“微结构”内，其描述未完全确定的序列。如图3中所示的这些气泡可从生成k-聚体的读取段的不同环境导出。所述不同的环境可以是不同的染色体、样品或结构变体，如插入缺失、重复和易位。条形码允许推断应覆盖所述组装体中的空位的读取池，包括具有特定条形码序列的所有读取。在从此池创建局部组装体后，可将其重新插入到全局组装体中。这在图4中例示，其中一种亲本等位基因呈实心点线401，而另一种呈圆圈点线402。所示的是落在呈实点的所有等位基因上的一个条形码分子，以及落在呈圆点的所有等位基因上的一个条形码分子，从而将它们分开为411和412，并且因此正确地定相序列环境。实际上，许多条形码化的分子串通以执行这种定相操作。在某些实施方案中，本文所述的方法可创建包含超过1、2、3、4、5、6、7、8、9、10或更多个兆碱基的核苷酸序列的定相区块。对于3千兆碱基(人)基因组，这些定相水平可在50x或更低、40x或更低或30x或更低的覆盖水平下实现。

输出

参考图5，算法可以多种方式向用户输出信息。输出501表明数据可以“原始”样式输出，其中非常组装边缘(包括微泡臂和空位)作为单独的FASTA记录出现。这是软件看到组装体的方式。输出502表明数据可以“巨大气泡样式”输出，其中每个巨大气泡臂对应于单个FASTA记录，每个插入序列也是如此。在一些情况下，用户可设置阈值以仅在巨大气泡或插入序列在基因组的某一链段上出现或超过e(特定大小阈值)时可视化所述巨大气泡或插入序列。输出503表明数据可以“psuedohap样式”(每个支架单个记录)输出。巨大气泡臂是任意选择的，因此许多记录混合母本和父本等位基因。输出504表明数据可以“psuedohap2样式”输出，其中，对于每个支架，创建两种“并行”伪单倍型并将其置于单独的FASTA文件中。

数字处理装置

本文描述的方法、系统和介质包括至少一个数字处理装置，或其用途。所述数字处理装置包括执行所述装置的功能的一个或多个硬件中央处理单元(CPU)或通用图形处理单元(GPGPU)。所述数字处理装置还包括被配置用于执行可执行指令的操作系统。所述数字处理装置任选地连接至计算机网络。作为举例，所述数字处理装置任选地连接至互联网，以使得它可访问万维网。作为另一实例，所述数字处理装置任选地连接至云计算基础结构。作为另一实例，所述数字处理装置任选地连接至内联网。作为另一实例，所述数字处理装置任选地连接至数据存储装置。

根据本文的描述，作为非限制性实例，合适的数字处理装置包括本领域技术人员已知的商业服务器计算机和台式计算机。合适的数字处理装置还包括使用本领域技术人员已知的硬件和技术定制的装置。

所述数字处理装置包括被配置用于执行可执行指令的操作系统。所述操作系统是例如包括程序和数据的软件，所述操作系统管理所述装置的硬件并提供用于执行应用程序的服务。本领域技术人员将认识到，作为非限制性实例，合适的服务器操作系统包括FreeBSD、OpenBSD、

Linux、

Mac OS X

Windows

以及

本领域技术人员将认识到，作为非限制性实例，合适的个人计算机操作系统包括

Mac OS

以及类似UNIX的操作系统如

在一些情况下，所述操作系统通过云计算来提供。

所述装置包括存储和/或存储器装置。所述存储和/或存储器装置是用于在临时或永久的基础上存储数据或程序的一个或多个物理设备。在一些实施方案中,所述装置是易失性存储器并且需要维护存储信息的电源。在一些情况下，所述装置是非易失性存储器，并且在所述数字处理装置未通电时保留存储的信息。非易失性存储器可包括闪速存储器、动态随机存取存储器(DRAM)、铁电随机存取存储器(FRAM)、相变随机存取存储器(PRAM)等。在其他情况下，所述装置是存储装置，作为非限制性实例包括CD-ROM、DVD、闪速存储器装置、磁盘驱动器、磁带驱动器、光盘驱动器、基于云计算的存储器等。在各种情况下，所述存储和/或存储器装置是如本文公开的那些的装置的组合。

所述数字处理装置任选地包括用于向用户发送视觉信息的显示器。合适的显示器包括液晶显示器(LCD)、薄膜晶体管液晶显示器(TFT-LCD)、有机发光二极管(OLED)显示器(包括无源-矩阵OLED(PMOLED)和有源矩阵OLED(AMOLED)显示器)、等离子体显示器、视频投影仪以及与数字处理装置通信的头戴式显示器(如VR头戴式耳机)。作为非限制性实例，合适的VR头戴式耳机包括HTC Vive、Oculus Rift、Samsung Gear VR、Microsoft HoloLens、Razer OSVR、FOVE VR、Zeiss VR One、Avegant Glyph、Freefly VR头戴式耳机等。在各种情况下，所述显示器是如本文公开的那些的装置的组合。

所述数字处理装置任选地包括一个或多个输入装置以接收来自用户的信息。合适的输入装置包括键盘、指向装置(作为非限制性实例，包括鼠标、轨迹球、轨迹板、操纵杆、游戏控制器和触控笔)、触摸屏或多点触摸屏、用于捕获语音或其他声音输入的麦克风、用于捕获运动或视觉输入的摄像机或其他传感器。在特定情况下，所述输入装置是Kinect、LeapMotion等。在各种情况下，所述输入装置是如本文公开的那些的装置的组合。

参考图6，在特定实施方案中，示例性数字处理装置601被编程或以其他方式配置来将短读取段DNA序列组装成完全定相的完整基因组序列。装置601可调节本公开的序列组装方法的各个方面，例如像执行初始比对、质量检查、执行后续比对、解析模糊性以及定相杂合基因座。在此实施方案中，数字处理装置601包括中央处理单元(CPU，在本文中也称为“处理器”和“计算机处理器”)605，其可为单一核心或多核心处理器，或用于并行处理的多个处理器。数字处理装置601还包括存储器或存储单元610(例如，随机存取存储器、只读存储器、闪速存储器)、电子存储单元615(例如，硬盘)、与一个或多个其他系统通信的通信接口620(例如，网络适配器)以及外围装置525，如高速缓冲存储器、其他存储器、数据存储和/或电子显示适配器。存储器610、存储单元615、接口620和外围装置625经由通信总线(实线)诸如母板与CPU 605通信。存储单元615可以是用于存储数据的数据存储单元(或数据存储库)。数字处理装置601可借助于通信接口620来可操作地耦接至计算机网络(“网络”)630。网络630可以是互联网、互联网和/或外联网或与互联网通信的内联网和/或外联网。网络630在一些情况下为电信和/或数据网络。网络630可包括一个或多个计算机服务器，其可实现分布式计算，如云计算。网络630在一些情况下借助于装置601，可实现对等网络，其可使得耦接至装置601的装置能够作为客户端或服务器来运作。

继续参考图6，CPU 605可执行序列机器可读指令，所述指令可在程序或软件中具体实现。所述指令可存储于存储单元，如存储器610中。所述指令可被引导至CPU 605，其可随后编程或以其他方式配置CPU 605来实现本公开的方法。由CPU 605执行的操作的实例可包括撷取、解码、执行和写回。CPU 605可以是电路的一部分，如集成电路。装置601的一个或多个其他部件可包含于电路中。在一些情况下，所述电路是专用集成电路(ASIC)或现场可编程门阵列(FPGA)。

继续参考图6，存储单元615可存储文件，如驱动程序、文库和保存程序。存储单元615可存储用户数据，例如，用户偏爱性和用户程序。数字处理装置601在一些情况下可包括一个或多个额外数据存储单元，所述一个或多个额外数据存储单元在外部，如位于经由内联网或互联网通信的远程服务器上。

继续参考图6，数字处理装置601可经由网络630与一个或多个远程计算机系统通信。例如，装置601可与用户的远程计算机系统通信。远程计算机系统的实例包括个人计算机(例如，便携式PC)、平板(slate)或平板(tablet)PC(例如，

iPad、

GalaxyTab)、电话、智能手机(例如

iPhone、支持Android的装置、

)或个人数字助理。

如本文描述的方法可经由机器(例如，计算机处理器)可执行代码来实现，所述代码存储于数字处理装置601的电子存储单元上，例如像，存储器610或电子存储单元615。机器可执行或机器可读代码可以软件形式提供。在使用期间，所述代码可由处理器605执行。在一些情况下，所述代码可从存储单元615检索并且存储在存储器610上准备由处理器605访问。在一些情况下，可排除电子存储单元615，并且机器可执行指令存储于存储器610上。

非暂时性计算机可读存储介质

本文公开的方法、系统和介质包括用程序编码的一个或多个非暂时性计算机可读存储介质，所述程序包括可由任选联网的数字处理装置的操作系统执行的指令。在一些情况下，计算机可读存储介质是数字处理装置的有形部件。在其他情况下，计算机可读存储介质任选地可从数字处理装置移除。作为非限制性实例，计算机可读存储介质包括CD-ROM、DVD、闪速存储器装置、固态存储器、磁盘驱动器、磁带驱动器、光盘驱动器、云计算系统和服务等。在一些情况下，所述程序和指令在所述介质上永久地、基本上永久地、半永久地或非暂时性地编码。

计算机程序

本文描述的方法、系统和介质包括至少一种计算机程序，或其用途。计算机程序包括可在数字处理装置的CPU中执行的指令序列，所述计算机程序被编写以执行指定任务。计算机可读指令可被实现为执行特定任务或实现特定抽象数据类型的程序模块，如功能、对象、应用程序编程接口(API)、数据结构等。鉴于本文提供的公开内容，本领域技术人员将认识到，计算机程序可以各种语言的各种版本来编写。

计算机可读指令的功能性可根据需要在各种实施方案中进行组合或分布。在一些情况下，计算机程序包括一个指令序列。在其他情况下，计算机程序包括多个指令序列。在一些情况下，计算机程序从一个位置提供。在其他情况下，计算机程序从多个位置提供。在各种情况下，计算机程序包括一个或多个软件模块。在各种实现方式中，计算机程序部分或全部包括一个或多个web应用程序、一个或多个移动应用程序、一个或多个独立应用程序、一个或多个web浏览器插件、扩展、加载项或附加软件或其组合。

独立应用程序

在一些实施方案中，计算机程序包括独立应用程序，所述独立应用程序是作为独立的计算机进程运行的程序，而不是对现有进程的附加软件(例如，不是插件)。本领域技术人员将认识到经常编译独立应用程序。编译程序是一种或多种计算机程序，其将用编程语言编写的源代码转换成二进制目标代码，如汇编语言或机器代码。作为非限制性实例，合适的编译编程语言包括C、C++、Objective-C、COBOL、Delphi、Eiffel、Java^TM、Lisp、Python^TM、Visual Basic以及VB.NET或其组合。通常至少部分地执行编译以创建可执行程序。在一些情况下，计算机程序包括一个或多个可执行的编译应用程序。

软件模块

本文公开的方法、系统和介质包括软件、服务器和/或数据库模块，或其用途。鉴于本文提供的公开内容，使用本领域已知的机器、软件和语言，通过本领域技术人员已知的技术创建软件模块。本文公开的软件模块以多种方式实现。在各种实现方式中，软件模块包括文件、代码段、编程对象、编程结构或其组合。在其他各种实现方式中，软件模块包括多个文件、多个代码段、多个编程对象、多个编程结构或其组合。作为非限制性实例，所述一个或多个软件模块包括web应用程序、移动应用程序和独立应用程序。在一些情况下，软件模块是在一个计算机程序或应用程序中。在其他情况下，软件模块是在多于一个计算机程序或应用程序中。在一些情况下，软件模块主存在一台机器上。在其他情况下，软件模块主存在多于一台机器上。在特定情况下，软件模块主存在一个或多个云计算平台和/或服务上。在一些情况下，软件模块主存在一个位置的一台或多台机器上。在其他情况下，软件模块主存在多于一个位置的一台或多台机器上。

数据库

本文公开的方法、系统和介质包括一个或多个数据库，或其用途。鉴于本文提供的公开内容，本领域技术人员将认识到许多数据库适合于存储和检索序列和图形信息。作为非限制性实例，合适的数据库包括关系数据库、非关系数据库、面向对象的数据库、对象数据库、实体关系模型数据库、关联数据库以及XML数据库。其他非限制性实例包括SQL、PostgreSQL、MySQL、Oracle、DB2以及Sybase。在一些情况下，数据库是基于互联网的。在其他情况下，数据库是基于web的。在其他情况下，数据库是基于云计算的。在其他情况下，数据库是基于一个或多个本地计算机存储装置。

实施例

以下说明性实施例代表本文描述的软件应用程序、系统和方法的实施方案并且并不意图以任何方式进行限制。

实施例1–使用标记读取的二倍体从头序列组装生成长基因组定相链段

为了在不同的基因组上充分测试本公开的方法，此实施例生成来自七个不同血统和性别的个体和三只混合品种狗的数据集，如表1中所示。这些数据集分别展示大小为3.2和2.5Gb的基因组。所有都是由大小≥80kb的DNA创建的。

表1图例：在移除短于10kb的支架后计算所有统计数据。与参考文献的比较使用GRCh37(chr1-22，X，Y)，其中对于女性样品不包括chrY。ID：此表中组装体的标识符。样品：起始材料的类型。对于文库RPCI 1、3、4、5(可在http://bacpac.chori.org/library.php？id＝1获得)，HGP是来自人类基因组计划的活匿名供体，其中340Mb的完成序列在GenBank中。狗和HGP是来自血液，其他是来自Coriell细胞系。种族：种族，或对于狗，品种起源。性别：样品的性别。数据描述：数据类型的简要描述。X：通过序列读取估计的基因组的覆盖率。对于这项工作的组装体，读取是2x150；对于每个人组装体使用1200M读取；对于每个狗组装体使用940M读取；将狗和样品G在HiSeq 2500上以快速运行模式进行测序；其他样品在HiSeq X上进行测序。F：DNA的推断长度加权平均片段长度(kb)。N50重叠群大小：在以10个或更多个n或N字符的序列中断后，FASTA记录的N50大小。N50支架大小：FASTA记录的N50大小，不包括N。空位度：模糊的碱基的分数。N50完美链段：来自同一样品的完成序列上在组装体中完美镜像对称的区段的N50长度(kb)(参见文本)。在1Mb的定相误差％：其中定相与大多数不一致的巨大气泡分支中的定相位点的分数。缺失k-聚体：在参考中在组装体中缺失的100k-聚体的分数。单倍体：组装体的单倍体型式。单倍体：组装体的二倍体型式。在给定距离处的差异：在组装体中在给定距离处的k-聚体对的差异，并且对于其两者均独特地放置在参考上，对于其参考染色体、取向、顺序或分离(±10％)不一致的分数。挂钟：使用具有384GB可用内存的单一服务器(使用“mem＝384G”引导)从FASTQ文件开始的组装体的运行时间(天)。

实施例2–测序数据的生成

先前已经描述了核酸制备和测序数据的生成。简言之，使用数百万个珠粒作为给定文库构建的输入，其中每个珠粒含有对于所述珠粒来说独特的14碱基条形码的许多拷贝。微流体装置将单独珠粒与基因组DNA和试剂一起递送到大约一百万个分区中。每个分区含有若干长片段(如下所论述)，并且所述系统被布置成创建具有条形码的构建体，以及来自夹在Illumina适配器之间的片段的约300bp的基因组DNA。在第一次读取开始时成对放置条形码。

在负载的核酸中，大约40％出现在文库中。例如，如果负载1.25ng材料、分布在106个分区中并且具有50kb的平均大小，则每个分区的平均分子数将是约10–代表每个分区约0.5Mb的基因组。在56x覆盖率下，人基因组每分子的平均读取对数因此将是(1200M/2)/(106×10)＝60，并且覆盖分子至深度(120*150)/(50,000)＝0.36x。

对于较小基因组，并且在相同的固定覆盖水平(56x)下，每个分子的读取对的数量成比例地下降，这可降低数据类型的功率。例如，对于大小为人基因组大小的1/10(320Mb)的基因组，每个分子的平均读取对的数量是约6，并且读取对之间的距离是约8kb，从而使得难以将条形码锚定至短的初始重叠群。

然后在Illumina仪器上对这些构建体进行测序。应生成各自长度为150个碱基的成对读取段。选择这种读取长度，以使得可在HiSeq X仪器上对数据进行测序，其在Illumina仪器中产生最低成本数据并且其具有150的最大读取长度。也可在快速运行模式下在HiSeq 2500上生成数据。建议对于人基因组将样品测序至56x或约1200M读取段，然而，更低覆盖率是可能的并在后面描述。

实施例3–使用不同大小的核酸的组装体

在若干不同大小的DNA上测试了所述系统的性能，从而表明DNA长度是重要因素。表2中的数据显示关于来自四个不同文库的数据的组装体性能，所述文库由不同长度的NA12878DNA构建并测序至38x覆盖率。特别是对于DNA<30kb，数据表明大小为约20kb的DNA产生N50大小为0.6Mb的支架，而大小为约50kb的DNA产生大小为N50 12.8Mb的支架。

实施例4–不同覆盖率下HGP样品的组装体

另外，在不同的覆盖率下进行人类基因组计划供体样品的测序和组装。表3表明可从38x序列覆盖率生成至少2.3兆碱基的大相位区块。

实施例5-从头组装

条形码化数据提供每个分子的浅覆盖，不可能通过在每个分区中单独组装读取段来开始组装过程(否则其将是自然的方法)。相反，在此实例中，组装过程通过逐渐构筑较大组装单元来进行。一旦这些单元是几kb长，给定单元与来自给定分子(在同一基因座处)的读取段重叠的概率就较高，并且因此有可能鉴定入射到所述单元上的许多条形码，因此将条形码分组，并且因此组装所述组。这是从每个分区单独组装读取段的类似物。

Supernova算法遵循这一点，因此推迟了条形码的主要用途。开始，趋近De Bruijn图形算法，从而采用DISCOVAR方法扩展至全基因组数据集并利用条形码化数据。对K-聚体(在一些实施方案中K＝48)进行预滤波以除去仅存在于一个条形码中的那些，从而降低假k-聚体的发生率，即样品中不存在的那些。将剩余的k-聚体形成初始定向图，其中边缘代表未支化的DNA序列，并且邻接的边缘重叠K-1碱基。然后进行操作以恢复缺失的k-聚体并除去残余假k-聚体。此时，图形(称为基图)是通过沿着完美48-聚体重复序列折叠真实样品基因组序列而将获得的图形的近似。

接下来对于每个读取对，在可能的情况下，在图中找到可表示原始插入的序列的一条路径或有时更多的路径。这些路径被表示为与基图中边缘的标识符对应的整数序列。每当存在两条路径完全重叠K＝200个碱基时，所述路径经由等价关系在形式上连接。这产生新的定向图(称为超图)，其边缘由表示基图中的路径的整数序列标记。每个超图边缘可被翻译成DNA序列。在超图边缘邻接的情况下，它们的相关序列重叠K-1碱基(在此实施例中K＝48)。然而，超图表示通过沿着完美200-聚体重复序列折叠真实样品基因组序列而将获得的图形的近似。因此，它远比基图解析度更高。

组装过程的剩余部分由一系列修改此图的操作组成，旨在改进所述图。为了便于这些操作并了解单独组装体的性质，将所述图分解成称为线的单元。参考图7，线是延伸的线性区域，仅由“气泡”打断。气泡是图形中的位置，其中序列沿着交替路径暂时分叉，然后重新连接。最初大部分来自基因组中的杂合位点。在图7中，每个边缘代表DNA序列。在图701中，部分702描述组装图中的线，其是两端由单边缘界定的非循环图形部分。所述线在五个共同区段和四个气泡之间交替，其中三个气泡具有两个分支。第三个气泡703更复杂。可对整个图形进行分区，以使得其边缘各自位于唯一的线中(从而允许简并情况，包括单边缘线和圆形)。图711显示线712与线702相同，但现在每个气泡被由所有其路径组成的气泡所替代。在这种变化之后，每个气泡仅由平行边缘组成。

可使用线来支撑超图。这涉及确定两条线的相对顺序和取向，然后断开在其端部的连接，然后在所述线之间插入特殊的“空位”边缘。最终结果是新的线，其具有仅由空位边缘组成的特殊“气泡”。后续操作(稍后描述)可移除这些空位中的一些，用序列替代它们。

首先使用读取对进行支架支撑。如果一条线的右端通过读取对明确地连接至另一条线的左端，则它们可连接。读取对可达到短空位。

为了跨越更大空位支架，使用了条形码。简言之，如果两条线在基因组中实际上彼此靠近，则很可能多个分子(在分区中)桥接所述两条线之间的空位。因此，对于任何线，可通过寻找共享许多相同条形码的其他线来在其邻域中找到候选线。然后测试这些线的替代顺序和取向(O&O)，从而明智地将测试限制为线的小集以避免组合展开。

对于组装体中的所有线，进行初始计算。计算为每条线分配线性坐标系，并在其上标记唯一放置的读取段的位置，通过条形码组构。现在，对于给定线集S，可对替代O&O可能性进行评分，如下所示。因此，S的每个O&O沿着假设的合并线产生条形码读取位置序列。计算了给定O&O的得分，所述分数是所有其组成条形码的总和。对于每个条形码，首先计算所述条形码的连续读取段布局之间的平均间隔(在合并的线中)。然后，按顺序遍历这些布局，找到桥接从一条组成线至另一条组成线的跳跃的那些连续布局对，并且其可能因此表示错误连接。对于此对将间隔除以条形码的平均间隔。如果商小于固定界限，例如2.0，则基于它可能是噪声的理论而被丢弃。将剩余商添加至得分总和中。

如果给定O&O的得分至少比同一线集的竞争测试的O&O可能性低固定量，则将其视为“优胜者”。在此基础上，使用条形码对线进行支架支撑。

一旦组装体已进行支架支撑，就可用序列填充一些空位。对于短空位，来自空位两侧的读取对达成并且可覆盖插入序列，从中可推断出。对于长空位，首先找到入射在靠近空位的左侧和右侧的序列上的条形码。然后，找到这些条形码中的所有读取段。这组读取段将包括正确地位于空位内的读取段，并且比所述集大约十倍(因为每个液滴包含约十个分子)。组装读取段的全集。在空位基因座之外的读取段倾向于处于低覆盖率，并且因此不能组装。以这种方式，通常有可能用图形组块填充空位，并且由此从组装体中移除空位。所述组块可能不是单一序列。例如，在此阶段，空位内的杂合位点通常将表现为简单的气泡。

组装过程中的最后一步是对线进行定相。参考图7，首先，对于每条线，可找到所有其简单气泡，即只有两个分支的气泡。然后，定义了一组分子。这些是由入射到线上的来自同一条形码的一系列读取段定义的，并且没有非常大的空位(>100kb)。

“定相”是每个气泡的取向，从而将一个分支放在“顶部”而另一个分支放在“底部”。初始选择任意取向。每个分子触及一些气泡，并且因此(相对于给定定相)可被表示具有条目对于顶部+1、对于底部-1或对于沉默0的序列。如果每个分子是相干的，则定相是“良好的”，从而含有几乎全部1或几乎全部-1(在沉默位置加0)。因此，定相的得分被定义为Max(加号，减号)─Min(加号，减号)的所有分子的总和。

然后，此实施例进行迭代扰动，所述扰动各自翻转一些气泡，并且仅保留提高定相得分的那些扰动。尝试了三种类型的扰动：(a)在给定分子上翻转气泡以使其完全相干；(b)翻转个别气泡；以及(c)在给定点枢转，从而将所有气泡向左翻转。

现在进行了初始定相。然后，可考虑其中的弱点。首先，如果翻转气泡对得分的影响太小，则将其排除在定相操作之外。例如，在长均聚物处可能出现气泡，其长度在样品中固定但在数据生成期间发生变化。其次，如果枢转对得分的影响太小，则定相在枢轴点处被破坏，从而产生给定支架的多个相位区块。例如，如果给定样品中足够长的区块是纯合的，则可能发生这种情况。

在一些应用程序中，Supernova被设计为在单个Linux服务器上运行。对于人类大小的基因组，典型的内存使用峰值是300GB；建议使用≥384GB RAM的服务器。挂钟运行时间在表1中示出。在固定覆盖率下，存储器和运行时间作为基因组大小的函数是大致线性的。

实施例6–Supernova输出

再次提及图3，Supernova组装体可捕获二倍体基因组的生物学。相位区块显示为“巨大气泡”，其中每个分支表示一个亲本等位基因，而巨大气泡之间的序列名义上是纯合的。连续巨大气泡相对于彼此不是定相的(如果它们是，则它们将被合并)。如所示的一系列巨大气泡包含给定支架。除了大规模特征外，Supernova图还可编码较小的特征，如对长均聚物处的空位和气泡，所述均聚物的长度不完全由数据决定。在图3中，Supernova组装体编码二倍体基因组体系结构。每条边缘表示一个序列。巨大气泡臂表示在给定基因座处的替代亲本等位基因，而巨大气泡之间的序列是纯合的(或者对于Supernova而言似乎如此)。小规模特征311作为空位和气泡出现。

再次提及图5，超新星组装体可以几种不同的方式转换为FASTA，这可能对不同的应用程序有用。这些允许表示完整的“原始”图形501，或清除微特征(在小气泡处选择最可能的分支并用N替代空位边缘)。存在多于一种方式来打包结果，这取决于以巨大气泡样式502、pseudohap样式503和pseudohap2样式504处理巨大气泡分支点的方式。注意，清除微特征导致一些信息丢失，因为在一些情况下选择错误气泡分支。

图中的循环提供令人感兴趣的测试用例。循环意味着一组一个或多个边缘，所述边缘包括图形的循环部分。这些在全图中保持完整，然而在其他形式中，用通过至少一次遍历每个边缘的循环的路径替代，然后用N替代。遗憾的是，这表示空位(原则上可表示任何序列)，而全图精确地指示了哪些序列可存在于基因座处。

图5示出若干样式。在501中，原始样式将组装体中的每个边缘表示为FASTA记录(视为红色区段)。这些包括微泡臂以及还有空位(对于通过读取对桥接的空位印刷为包含100N的记录，或更大的数量，估计的空位大小，补充注释6)。未解析的循环被通过循环的路径替贷，随后被10N替代。气泡和空位通常每10-20kb出现一次。原始图形记录比巨大气泡臂大约短两个数量级。对于原始图中的每个边缘，还存在编写至FASTA文件的边缘，其表示反向互补序列。对于剩余的输出样式，通过选择具有最高覆盖率的分支压平每个气泡，合并与相邻序列的空位(留下N)并且丢弃反向互补边缘。在第二种样式502中，每个巨大气泡臂对应于FASTA记录，每个插入序列也是如此。第三种样式503是pseudohap样式，每个支架生成单一记录。例如，在样式二的动画中，顶部的七个红色边缘(对应于七个FASTA记录)被组合成单一FASTA记录。巨大气泡臂是任意选择的，因此许多记录将混合母本和父本等位基因。第四种样式504像pseudohap选项一样，除了对于每个支架，创建两个“并行”伪单倍型并放置在单独的FASTA文件中。

实施例7–推断的DNA长度

对于所述组装体中的每个，可推断出DNA分子的统计数据，所述统计数据使其成为一个分区，然后进行测序，从而反映输入材料的质量和在文库构建的初始步骤期间降解。表1显示这些分子的长度加权平均值(LWM)的推断值，如场F。狗DNA在83-90kb范围内，而人DNA在92-139kb范围内。可想象这种差异可归因于碱基组成的差异，如在CpG岛。所有狗DNA都是从新鲜血液中获得，最长的人DNA样品也一样。其他人样品获自细胞系。由于重复处理DNA管来创建多个文库，最短的人样品(NA12878)可能是最短的，因此所述DNA样品用作许多实验的对照。

实施例8–人组装体的评估

此实施例评估七种组装体和六种人组装体，从而涵盖广泛的实验室方法，从低覆盖率(30x)PacBio到覆盖率更高的多种技术的复杂组合(表1)。对于每种组装体，计算了若干统计数据，以便可计算那些统计数据。在计算这些统计数据之前，第一步骤从每种组装体中移除短于10kb的所有支架，从而针对用于定义所述组装体的实际截止值的差异进行标准化，否则这将显著影响统计数据，包括基因组的覆盖率。

为了评估组装体的连续性，第一步骤计算N50重叠群大小。七种Supernova组装体的平均值是117kb，几乎没有变化。基于PacBio的三种组装体具有更大的重叠群，而来自其他组装体的重叠群比来自Supernova的重叠群短两倍或更短。

所有Supernova组装体都是二倍体，其中N50相位区块大小在2.7至10.7Mb的范围内，变异可能是由于不同的血统和不同的DNA长度。在六种其他人组装体中，只有702x组装体是二倍体，并且其N50相位区块大小为0.5Mb。Linked-Reads下面的大分子能够实现其他技术难以实现的长相位区块。

Supernova组装体中的支架在15至19Mb(N50)的范围内。虽然仅PacBio组装体具有更短的支架，但是四种组合组装体具有更长的支架，范围从23至43Mb。这些支架中的空位(N的分数)也变化很大，从PacBio组装体的0％至Supernova组装体的2％，到组装体I的10％。

对组装连续性的任何评估都将通过评估这些相同组装体的准确度和完整性来缓和。虽然可通过与人参考序列进行比较来做到这一点(并且稍后会这样做)，但理想的将是利用来自组装的相同样品的地面实况数据。这些数据将由已经独立测序和组装的克隆组成，并且代表基因组。只能找到两种样品，对于所述样品可获得这种真实数据并且可获得高质量的DNA来创建组装体。这些是来自活人类基因组计划供体的样品，其中340Mb的完成克隆已经在计划期间进行了测序和组装，费用很高；以及NA12878，之前已对其进行测序并组装了4Mb的随机克隆。尽管HGP克隆不是真正随机的，但一个原因是它们构成了基因组的如此多(约10％)，以至于它们将合理地代表它。

对于给定样品，如果已知每个其染色体的确切序列，则可通过枚举在组装体中完美表示的基因组的最大区域来评估所述样品的组装的准确度。大多数此类区域将因组装体中的错误或空位终止。(注意，显示错误的等位基因将被视为误差。)此类完美代表区域的N50大小被称为“N50完美链段”。对于二倍体基因组，如果具有二倍体组装体(从而试图显示所有染色体)和来自完全相同的样品的代表性完成序列(从而提供那些染色体的样品)，然后可近似N50完美链段。在表1的样品中，只有组装体F和G满足这些要求。

发现，这些Supernova组装体中的N50完美链段是约19kb(表1)。此外，检查完成序列与组装体的比对揭示组装体缺陷的确切性质，所述缺陷终止这些完美链段。例如图8(以及数千个其他克隆的相应比对)显示在长均聚物附近的优势误差，这可能归因于文库构建缺陷、测序缺陷、算法缺陷或完成序列中的可能的误差。更详细地，图8显示在162kb区域内部(令人感兴趣的是因为它包含了尼安德特人起源的一个区域)，在所述区域的组装体与完成序列之间存在七种差异(加两个空位)。其中一种差异是单碱基错配。因为所有的组装体读取都支持组装序列，所以在这种情况下完成序列似乎可能是错误的(并且不是Supernova组装体)。事实上，这个位点在GRCh38中得以纠正，并且因此匹配我们的组装体。六种剩余差异是长均聚物中的插入缺失。当检查如同这些的基因座处的数据时，通常观察到质量非常低的读取段(通常在均聚物的一侧有质量分解)。因此，这些差异很可能是由于组装误差所致。

这种比较还显示组装体中的两个捕获的空位，一个大小为46个碱基(由通过完成序列所测量)并且由读取对捕获，且另一个大小为1765个碱基并且未由读取对捕获。短空位邻接低复杂度序列。对于长空位，存在大小为1225个碱基的单独“独立”重叠群，所述重叠群适合空位并且完美匹配完成序列，并且表明所述算法的改进版本可能至少将此序列置于所述空位内。

实施例9–组装保真度

此实施例考虑用于评估人基因组组装保真度的两种方法。第一种方法是通过与从完全相同的样品获得的参考序列进行比较来测量给定样品的组装体的性质。对于第一种方法，有必要建立真实的二倍体组装体。第二种方法是通过与人参考序列进行比较来测量组装体，了解一些差异将归因于原始样品之间的真实差异。

亲本序列数据也可用于评估组装体。具体地说，这可提供关于二倍体组装体中的相位区块的准确度的直接读出。对于人基因组以前没有这样做，因为两种对于现存的二倍体人组装体，未对亲本进行测序。此实施例具有Supernova组装体中的四个(表1中的C、E和G)。对亲本进行测序，并可获得定相的VCF。此实施例允许估计这些组装体的定相精确度。

要做到这一点，对于每个巨大气泡，只要在交替分支上找到可映射到GRCh37上的相同位置的两个位置，GRCh37代表不同的碱基(杂合SNP)并且在VCF中定相，记录0或1，这取决于巨大气泡的“顶部”分支是分配给母本还是父本等位基因。全部0或全部1的序列表示完美定相。对所有“投票”(0或1)进行评估计数并对所有“错误投票”(如果大多数＝0则为1，如果大多数＝1则为0)进行计数，并且对所有大小≥100kb的巨大气泡进行求和。用于定相给定组装体的全局错误率将是(错误的投票)/投票，注意即使关于单个巨大气泡的“长切换”错误也可能导致这种比率上升。此实施例未筛选出“错误的染色体”事件，因此这些事件也将导致错误率(平均50％的时间)。

所观察到的错误率(显示在表1中)：组装体C(HG00733，波多黎各人)0.089％(1368个错误)；组装体E(NA24385，德系犹太人)0.053％(640个错误)；组装体G(NA12878，欧洲人)0.018％＝(270个错误)。在组装体G的270个错误中，178个是在单个2Mb巨大气泡中，并且表示“长切换”错误。类似地，在组装体E的640个错误中，556个在两个事件中。对于组装体G，97％的巨大气泡没有检测到的相位误差，并且对于组装体E为96％，而对于组装体C这个数字仅为66％，从而表明波多黎各人样品的定相真实数据的不准确性。总的来说，所述数据表明，定相误差包括非常罕见的长切换事件(每个组装体可能1-2个)，以及一些百分比的巨大气泡中发生的孤立的短切换事件。

参考样品比较在下文进行了描述。组装体完整性的测量高度依赖于所使用的大小场地。此实施例选择了10kb的任意截止值，从而忽略了比这一大小更短的支架。为了测量不同组装体的相对完整性，此实施例选择计数k-聚体，因为虽然这种方法不完善，但它简单且因此解释相对简单明了。此外，所述方法将正确地惩罚具有非常高的错误率的组装体中的区域。此实施例使用K＝100，从而在两种考虑因素之间平衡。首先，认为重复k-聚体的分数很小是特别重要的，因为分析对它们来说是盲目的。GRCh37中重复k-聚体的比例是2.3％。其次，此实施例不想丢失过多的k-聚体到多态性。假设多态性率为1/1000，可预期由于样品与样品间的差异，约10％的k-聚体将缺失。

然后，此实施例将人组装体的完整性定义为GRCh37中在组装体中出现的非重复k-聚体的分数。单倍体组装体的覆盖率如此标记(表1)。对于Supernova组装体，此实施例可计算其单倍体覆盖率(使用输出类型pseudohap)或其二倍体覆盖率(使用输出类型pseudohap2)。此实施例在原始图中未使用k-聚体，但是这将产生在某种程度上更高的覆盖率。对于YH组装体，因为没有直接的方式来将组装体分成单倍型，此实施例使用了整个组装体并将覆盖率统计报告为二倍体。

然后，此实施例评估了错误组装体。为此，对于给定组装体和固定大小(1Mb、10Mb)，所述研究选择了组装体中给定大小的所有支架区段，其末端k-聚体在参考序列中恰好出现一次。此实施例报告了此类区段的末端k-聚体位置一致的分数，具体意味着它们以正确的顺序和取向位于同一染色体上，并定义长度在固定大小的10％范围内的片段。此实施例排除了在参考中桥接大小为100或更大的空位的情况，因为这些空位大小可能是不准确的或多态的。

实施例10–计算益处

前述实施例示出了本文公开的技术的实施方案。与现有技术(如由PacBio提供的技术)相比，本文的实施例以从潜在条形码技术产生的不同数据类型开始。因此，这些实施例考虑了较少的噪声数据，从而产生较低的错误率和较高的精确度。

本文公开的技术包括初步滤波步骤。滤波步骤包括利用来自序列分析仪的碱基质量得分。此外，所述步骤考虑出现多于一次的k-聚体。所述步骤还包括利用条形码，其中必须观察到每个k-聚体来自两个不同的条形码。滤波步骤的较大优点是能够将起始数据的量减少至少两倍至一个数量级。

本文公开的技术利用简单的数据结构：向量的向量。向量化的计算允许更快的计算时间。当在一些应用程序中出现稀疏向量/矩阵时，向量化的计算更容易被操纵以大大减少计算时间。

本文公开的技术利用环路来采用CPU而不是GPU来进行大规模并行计算。在一些应用中，使用GPU。某些实现方式包括使用CUP和GUP两者。并行计算的优点允许减少的计算时间。

本文公开的技术利用应用于质量得分的每个记录和通过图的路径(包括序列和边缘)的无损随机存取压缩。压缩的优点使得分析所需的内存更少，并且保存数据或分析结果所需的存储更少。

与来自PacBio的FALCON汇编器相比，这些实施例将计算时间缩短180倍，并将内存利用降低21倍。

实施例11–计算体系结构

图9示出如本文所述的从头组装系统901的非限制性框图。所述系统可包括至少一个CPU 902、存储器903和存储器904。计算体系结构的功能如下。将一组序列数据911提供给从头组装系统901。初步滤波器921利用来自用于生成短读取序列数据的序列分析仪的碱基质量得分，并利用k-聚体进行预处理。然后，汇编器922创建初始组装图。这种初始组装体相当于“草图”组装体并且暂时忽略未解析的复杂性区域，例如，在第一眼看上去可能是模糊的区域，从而保持计算能力。

将初始汇编器922的输出送到模糊性汇编器923。然后可通过使用条形码化的测序数据912来进一步处理模糊性区域，以创建模糊性区域的精确组装体。模糊性处理器923的输出包括从在组装过程期间创建的测序读取段导出的待寻址到某一染色体、细胞、群体、单倍型等的k-聚体。汇编器924基于图2中所示的步骤用于组装真实二倍体。将条形码化的读取段放回到所述组装体上，并且鉴定其确切序列未确定已知的基因座并且如此标记。最终汇编器925用于将全局组装图与参考序列进行比对。对边缘进行单独比对。当存在不一致比对时，通过比对这些边缘的拼接来解析不一致性。

所述系统还可包括无损随机存取压缩器926，所述压缩器压缩质量得分和通过图的路径的一个或多个记录。

在各种应用中，滤波器(921)、汇编器(922、923、924和925)以及压缩器(926)可用硬件或软件或其组合来实现。滤波器(921)、汇编器(922、923、924和925)以及压缩器(926)可单独地或一起配置用于执行本文公开的一种或多种功能。一些实现方式可交换滤波器(921)、汇编器(922、923、924和925)以及压缩器(926)的执行顺序，或者可将它们中的两个或更多个集成到单个执行模块中。

尽管本文已示出和描述了本发明的优选实施方案，但对于本领域技术人员来说将显而易见，此类实施方案仅作为举例提供。本领域技术人员现在将想到许多变化、改变和替换而不偏离本发明。应当理解的是，可在实践本发明时采用在本文中描述的本发明的实施方案的各种替代方案。

Claims (75)

1.一种用于从生物体的核酸样品生成的核酸序列数据的从头基因组组装的计算机实现的方法，所述方法包括：

a)由一台或多台计算机生成基于短读取序列数据的初始组装体，其中所述初始组装体鉴定(i)多个k-聚体和(ii)一个或多个未解析的序列模糊性区域，其中所述短读取序列数据是从来自所述核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，使得从共同起始序列导出的所述短读取序列数据的子集共享一个或多个共同标签；

b)由所述一台或多台计算机构建基于所述初始组装体的多个局部组装体和全局组装体，其中所述多个局部组装体和全局组装体通过下述构建：

(i)解析所述初始组装体以从所述多个k-聚体鉴定多个z-聚体，其中z>k；

(ii)鉴定明确序列的边缘；

(iii)鉴定共享具有明确序列的多个所述一个或多个共享标签的相邻边缘，其中所述一个或多个共享标签的数目高于阈值；和

(iv)将所述明确序列的所述边缘与(iii)中鉴定的所述相邻边缘汇集在一起；

c)通过移除与由所述一个或多个共享标签指示的所述长程序列环境不一致的序列数据，由所述一台或多台计算机清除所述全局组装体；以及

d)通过利用所述一个或多个共享标签来分离定相的核苷酸序列，由所述一台或多台计算机生成基于所述全局组装体的定相的基因组组装体；

其中在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。

2.如权利要求1所述的方法，其中所述基因组是二倍体。

3.如权利要求1所述的方法，其中从单个文库生成所述短读取序列数据。

4.如权利要求1所述的方法，其中所述短读取序列数据产生所述生物体的所述基因组的50x或更低覆盖率。

5.如权利要求1所述的方法，其中对所述短读取序列数据进行标记以保留在比读取段长2x–1000x的起始序列内的环境。

6.如权利要求1所述的方法，其中对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。

7.如权利要求1所述的方法，其中所述初始组装体是初始组装图。

8.如权利要求7所述的方法，其中通过以下方式来生成所述初始组装图：

a)鉴定所述多个k-聚体，其中所述多个k-聚体在所述生物体的所述基因组中以高概率存在；

b)使用所述一个或多个共同标签来基于每个k-聚体出现于其中的起始序列的数量来过滤所述多个k-聚体；以及

c)将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。

9.如权利要求8所述的方法，还包括：在生成所述初始组装体之前，由所述一台或多台计算机应用初步滤波器，其中所述初步滤波器包括：

a)利用来自用于生成所述短读取序列数据的序列分析仪的碱基质量得分，以及

b)利用出现超过一次的k-聚体和所述一个或多个共享标签，使得必须观察到每个k-聚体由两个不同的共同标签产生。

10.如权利要求9所述的方法，还包括由所述一台或多台计算机向所述质量得分和通过所述图的路径的每个记录应用无损随机存取压缩。

11.如权利要求8所述的方法，其中方法还包括通过以下方式由所述一台或多台计算机修订所述初始组装图：

a)基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；以及

b)通过咨询原始短读取序列数据来填充所述初始组装图中的空位。

12.如权利要求8所述的方法，其中k是介于24与96之间。

13.如权利要求8所述的方法，其中通过以下方式来生成所述全局组装体：

a)鉴定所述初始组装体中在所述生物体的所述基因组中存在的概率高的多个z-聚体，其中z>k；以及

b)将所述初始组装体中的所述z-聚体汇集在一起。

14.如权利要求13所述的方法，其中z是介于100与300之间。

15.如权利要求1所述的方法，其中从少于10ng的DNA输入材料生成所述短读取序列数据。

16.如权利要求15所述的方法，其中从少于2ng的DNA输入材料生成所述短读取序列数据。

17.如权利要求1所述的方法，其中所述组装在不到60分钟内完成。

18.如权利要求17所述的方法，其中所述一台或多台计算机包括小于512GB的存储。

19.如权利要求18所述的方法，其中所述一台或多台计算机包括小于60GB的存储。

20.如权利要求1所述的方法，其中所述组装在不到20分钟内完成。

21.如权利要求20所述的方法，其中所述一台或多台计算机包括小于512GB的存储。

22.如权利要求21所述的方法，其中所述一台或多台计算机包括小于60GB的存储。

23.如权利要求1所述的方法，其中所述生物体是人类。

24.如权利要求1所述的方法，其中DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。

25.如权利要求1所述的方法，其中所述一台或多台计算机占用一立方英尺或更小的物理空间。

26.一种计算机实现的系统，所述系统包括：数字处理装置，所述数字处理装置包括：至少一个处理器；操作系统，所述操作系统被配置用于执行可执行指令；存储器；以及计算机程序，所述计算机程序包括由所述数字处理装置可执行以创建从生物体的核酸样品生成的核酸序列数据的从头基因组组装应用程序的指令，所述应用程序包括：

a)第一软件模块，所述第一软件模块生成基于短读取序列数据的初始组装体，其中所述初始组装体鉴定(i)多个k-聚体和(ii)一个或多个未解析的序列模糊性区域，其中所述短读取序列数据是从来自所述核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，使得从共同起始序列导出的所述短读取序列数据的子集共享一个或多个共同标签；

b)第二软件模块和第三软件模块，所述第二软件模块和第三软件模块用于构建基于所述初始组装体的多个局部组装体和全局组装体，其中所述多个局部组装体和全局组装体通过下述构建：

(i)解析所述初始组装体以从所述多个k-聚体鉴定多个z-聚体，其中z>k；

(ii)鉴定明确序列的边缘；

(iii)鉴定共享具有明确序列的多个所述一个或多个共同标签的相邻边缘，其中所述一个或多个共同标签的数目高于阈值；和

(iv)将所述明确序列的所述边缘与(iii)中鉴定的所述相邻边缘汇集在一起；

c)第四软件模块，所述第四软件模块通过移除与由所述一个或多个共同标签指示的长程序列环境不一致的序列数据而清除所述全局组装体；以及

d)第五软件模块，所述第五软件模块通过利用所述一个或多个共同标签来分离同源定相的核苷酸序列而生成基于所述全局组装体的定相的基因组组装体；

其中在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。

27.如权利要求26所述的系统，其中所述基因组是二倍体。

28.如权利要求26所述的系统，其中从单个文库生成所述短读取序列数据。

29.如权利要求26所述的系统，其中所述短读取序列数据产生所述生物体的所述基因组的50x或更低覆盖率。

30.如权利要求26所述的系统，其中对所述短读取序列数据进行标记以保留在比读取段长2x–1000x的起始序列内的环境。

31.如权利要求26所述的系统，其中对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。

32.如权利要求26所述的系统，其中所述初始组装体是初始组装图。

33.如权利要求32所述的系统，其中生成初始组装图的所述软件模块通过以下方式来生成所述初始组装图：

a)鉴定多个所述k-聚体，其中所述多个k-聚体在所述生物体的所述基因组中以高概率存在；

b)使用所述一个或多个共同标签来基于每个k-聚体出现于其中的起始序列的数量来过滤所述多个k-聚体；以及

c)将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。

34.如权利要求32所述的系统，其中所述应用程序还包括在生成所述初始组装体之前，应用初步滤波器的软件模块，其中所述初步滤波器包括：

a)利用来自用于生成所述短读取序列数据的序列分析仪的碱基质量得分，以及

b)利用出现超过一次的k-聚体和所述一个或多个共同标签，使得必须观察到每个k-聚体由两个不同的共同标签产生。

35.如权利要求34所述的系统，其中所述应用程序还包括向所述质量得分和通过所述图的路径的每个记录应用无损随机存取压缩的软件模块。

36.如权利要求33所述的系统，其中生成初始组装图的所述软件模块通过以下方式来修订所述初始组装图：

a)基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；以及

b)通过咨询原始短读取序列数据来填充所述初始组装图中的空位。

37.如权利要求33所述的系统，其中k是介于24与96之间。

38.如权利要求34所述的系统，其中生成全局组装体的所述软件模块通过以下方式来生成所述全局组装体：

a)鉴定所述初始组装体中在所述生物体的所述基因组中存在的概率高的多个z-聚体，其中z>k；以及

b)将所述初始组装体中的所述z-聚体汇集在一起。

39.如权利要求38所述的系统，其中z是介于100与300之间。

40.如权利要求26所述的系统，其中从少于10ng的DNA输入材料生成所述短读取序列数据。

41.如权利要求40所述的系统，其中从少于2ng的DNA输入材料生成所述短读取序列数据。

42.如权利要求26所述的系统，其中所述组装在不到60分钟内完成。

43.如权利要求42所述的系统，其中所述存储器包括小于512GB的存储。

44.如权利要求43所述的系统，其中所述存储器包括小于60GB的存储。

45.如权利要求26所述的系统，其中所述组装在不到20分钟内完成。

46.如权利要求45所述的系统，其中所述存储器包括小于512GB的存储。

47.如权利要求46所述的系统，其中所述存储器包括小于60GB的存储。

48.如权利要求26所述的系统，其中所述生物体是人类。

49.如权利要求26所述的系统，其中DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。

50.如权利要求26所述的系统，其中所述数字处理装置占用一立方英尺或更小的物理空间。

51.一种用计算机程序编码的非暂时性计算机可读存储介质，所述计算机程序包括由处理装置可执行以创建从生物体的核酸样品生成的核酸序列数据的从头基因组组装应用程序的指令，所述应用程序包括：

a)第一软件模块，所述第一软件模块生成基于短读取序列数据的初始组装体，其中鉴定(i)多个k-聚体和(ii)所述初始组装体包括一个或多个未解析的序列模糊性区域，其中所述短读取序列数据是从来自所述核酸序列数据的较长起始序列导出并被标记以保留所述生物体的长程序列环境，使得从共同起始序列导出的所述短读取序列数据的子集共享一个或多个共同标签；

b)第二软件模块和第三软件模块，所述第二软件模块和第三软件模块用于构建基于所述初始组装体的多个局部组装体和全局组装体，其中所述多个局部组装体和全局组装体通过下述构建：

(i)解析所述初始组装体以从所述多个k-聚体鉴定多个z-聚体，其中z>k；

(ii)鉴定明确序列的边缘；

(iii)鉴定共享具有明确序列的多个所述一个或多个共同标签的相邻边缘，其中所述多个一个或多个共同标签的数目高于阈值；和

(iv)将所述明确序列的所述边缘与(iii)中鉴定的所述相邻边缘汇集在一起；

c)第四软件模块，所述第四软件模块通过移除与由所述一个或多个共同标签指示的长程序列环境不一致的序列数据而清除所述全局组装体；以及

d)第五软件模块，所述第五软件模块通过利用所述一个或多个共同标签来分离同源定相的核苷酸序列而生成基于所述全局组装体的定相的基因组组装体；

其中在不与参考序列或任何独立生成的基因组序列比对的情况下实现所述定相的基因组组装体。

52.如权利要求51所述的介质，其中所述基因组是二倍体。

53.如权利要求51所述的介质，其中从单个文库生成所述短读取序列数据。

54.如权利要求51所述的介质，其中所述短读取序列数据产生所述生物体的所述基因组的50x或更低覆盖率。

55.如权利要求51所述的介质，其中对所述短读取序列数据进行标记以保留在比读取段长2x–1000x的起始序列内的环境。

56.如权利要求51所述的介质，其中对所述短读取序列数据进行标记以保留在10kb–5Mb的起始序列内的环境。

57.如权利要求51所述的介质，其中所述初始组装体是初始组装图。

58.如权利要求57所述的介质，其中生成初始组装图的所述软件模块通过以下方式来生成所述初始组装图：

a)鉴定所述多个k-聚体，其中所述多个k-聚体在所述生物体的所述基因组中以高概率存在；

b)使用所述一个或多个共同标签来基于每个k-聚体出现于其中的起始序列的数量来过滤所述多个k-聚体；以及

c)将所述多个k-聚体中共享共同l-聚体的k-聚体汇集在一起以形成初始组装体，其中l<k。

59.如权利要求58所述的介质，其中所述应用程序还包括在生成所述初始组装体之前，应用初步滤波器的软件模块，其中所述初步滤波器包括：

a)利用来自用于生成所述短读取序列数据的序列分析仪的碱基质量得分，以及

b)利用出现超过一次的k-聚体和所述一个或多个共同标签，使得必须观察到每个k-聚体由两个不同的共同标签产生。

60.如权利要求59所述的介质，其中所述应用程序还包括向所述质量得分和通过所述图的路径的每个记录应用无损随机存取压缩的软件模块。

61.如权利要求58所述的介质，其中生成初始组装图的所述软件模块通过以下方式来修订所述初始组装图：

a)基于序列模糊性区域内可供用于每种选项的多个读取段，消除一个或多个序列模糊性区域；以及

b)通过咨询原始短读取序列数据来填充所述初始组装图中的空位。

62.如权利要求58所述的介质，其中k是介于24与96之间。

63.如权利要求60所述的介质，其中生成全局组装体的所述软件模块通过以下方式来生成所述全局组装体：

a)鉴定所述初始组装体中在所述生物体的所述基因组中存在的概率高的多个z-聚体，其中z>k；以及

b)将所述初始组装体中的所述z-聚体汇集在一起。

64.如权利要求63所述的介质，其中z是介于100与300之间。

65.如权利要求51所述的介质，其中从少于10ng的DNA输入材料生成所述短读取序列数据。

66.如权利要求65所述的介质，其中从少于2ng的DNA输入材料生成所述短读取序列数据。

67.如权利要求51所述的介质，其中所述组装在不到60分钟内完成。

68.如权利要求67所述的介质，其中所述处理装置包括小于512 GB的存储。

69.如权利要求68所述的介质，其中所述处理装置包括小于60GB的存储。

70.如权利要求51所述的介质，其中所述组装在不到20分钟内完成。

71.如权利要求70所述的介质，其中所述处理装置包括小于512GB的存储。

72.如权利要求71所述的介质，其中所述处理装置包括小于60GB的存储。

73.如权利要求51所述的介质，其中所述生物体是人类。

74.如权利要求51所述的介质，其中DNA序列数据是全基因组序列数据，并且所述定相的基因组组装体是全基因组组装体。

75.如权利要求51所述的介质，其中所述处理装置占用一立方英尺或更小的物理空间。

Images