欢迎光临
我们一直在努力
您的位置:首页>资讯 >

绝望的基因组压缩算法探索

你有基因组测序吗?全世界已有数百万人拥有,到2025年,这一数字可达到10亿。研究人员获得的基因组学数据越多,个人和公共卫生的前景就越好。产前DNA检测已经筛查出发育异常。很快,患者将对他们的血液进行测序,以发现任何可能发出传染病信号的非人类DNA 。将来,处理癌症的人将能够通过每天对来自多个组织的单个细胞的DNA和RNA进行测序来追踪疾病的进展。

整个人群的DNA测序将使我们更全面地了解整个社会的健康状况。这就是英国生物银行的野心,该目标旨在对50万名志愿者的基因组进行测序,并追踪他们数十年。人群范围内的基因组研究已经常规用于鉴定与特定疾病相关的突变。对空气,土壤和水中的生物进行定期测序将有助于追踪流行病,食物病原体,毒素等等。

该愿景将需要存储和分析几乎难以想象的数据量。通常,处理人类整个基因组的DNA测序仪将产生数十至数百千兆字节的数据。存储时,数百万基因组的累积数据将占据数十亿字节。

而这仅仅是个开始。发现基因组数据有用的科学家,医生和其他人不会停止对每个人进行一次测序 [PDF] - 在同一个体中,他们会想要随着时间的推移重复测序多个组织中的多个细胞。随着测序速度的提高和成本的下降,他们还希望对其他动物,植物,微生物和整个生态系统的DNA进行测序 - 现在每个人类基因组仅需1000美元,而且迅速下降。新应用程序 - 甚至是新行业 - 的出现将迫使更多的排序。

虽然很难预测基因组数据的所有未来益处,但我们已经看到了一个不可避免的挑战:涉及到几乎不可思议的数字存储量。目前,存储基因组数据的成本仍然只是实验室总体预算的一小部分。但是这种成本正在急剧增长,远远超过存储硬件价格的下降。在未来五年内,存储数十亿人类,动物,植物和微生物的基因组的成本每年将轻易达到数十亿美元。这些数据需要保留几十年,如果不是更长的话。

压缩数据显然有帮助。生物信息学专家已经使用像gzip这样的标准压缩工具将文件大小缩小了20倍。一些研究人员还使用针对基因组数据优化的更专业的压缩工具,但这些工具都没有被广泛采用。我们两个人都在研究数据压缩算法,我们认为现在是时候提出一种新的压缩方案 - 一种效率更高,速度更快,更适合基因组数据独特特性的压缩方案。正如专用视频和音频压缩对于YouTube和Netflix等流媒体服务至关重要,因此有必要进行有针对性的基因组数据压缩,以获得基因组数据爆炸带来的好处。

在我们解释如何更好地压缩基因组数据之前,让我们仔细研究一下数据本身。“基因组”在这里指的是四个碱基核苷酸的序列 - 腺嘌呤,胞嘧啶,鸟嘌呤和胸腺嘧啶 - 组成熟悉的DNA的A,C,G,T字母表。这些核苷酸存在于AT和CG对的链中,构成人类基因组中的23对染色体。这些染色体在大多数人类细胞中包含约60亿个核苷酸,包括编码基因,非编码元件(如染色体末端的端粒),调节元件和线粒体DNA。DNA测序仪,如Illumina,Oxford Nanopore Technologies和Pacific Biosciences 能够在数小时内从DNA样本中自动测序人类基因组。

这些商业DNA测序仪不产生单个基因组长的ACGT串,而是产生大量子串或“读数”。读数部分重叠,需要序列组装软件从它们重建全基因组。通常,当进行全基因组测序时,每个基因组片段出现不超过约100个读数。

根据所使用的测序技术,读数的长度可以从大约100到100,000个碱基对变化,并且读取的总数可以从数百万到数百亿不等。短读取可以发现单个碱基对突变,而较长的读取可以更好地检测复杂的变异,如删除或插入数千个碱基对。

DNA测序是一个嘈杂的过程,并且读取包含错误是很常见的。因此,除了ACGT核苷酸串之外,每个读数包括质量分数,表明测序机器对每个DNA核苷酸的置信度。排序器将其质量分数表示为错误概率的对数。他们使用的算法是专有的,但事后可以检查。如果质量得分为20-对应于1%的错误概率 - 用户可以确认在已知DNA序列中约1%的碱基对是不正确的。使用这些文件的程序依赖于质量分数来区分测序错误,例如突变。真正的突变会显示出更高的平均质量得分 - 也就是说,错误概率低于测序错误。

定序器将字符串和质量分数以及一些其他元数据(通过读取)粘贴在一起,形成所谓的FASTQ文件。整个基因组的FASTQ文件通常包含数十到数百千兆字节。

这些文件也非常多余,这源于任何两个人类基因组几乎相同的事实。平均而言,它们的差异在于每1,000个核苷酸约一个核苷酸,通常这些遗传差异是有意义的。一些DNA测序针对特定的差异区域 - 例如,像23andMe这样的DNA基因分型应用只能查找特定的变异,而刑事调查中的DNA分析则会查找某些标记重复次数的变化。

但是,如果您不知道有趣的东西在哪里 - 当您尝试诊断未知遗传起源的疾病时,您需要对整个基因组进行测序,并且这意味着获得更大量的测序数据。

测序数据的重复也来自于多次读取基因组的相同部分以清除错误。有时,单个样本包含序列的多个变体,因此您需要重复排序以捕获这些变体。假设您正在尝试检测组织样本中的一些癌细胞或孕妇血液中的胎儿DNA痕迹。这可能意味着对每个DNA碱基对进行多次测序,通常超过100次,以区分罕见的变异与更常见的差异以及与测序错误的真正差异。

到目前为止,您应该更好地了解为什么DNA测序会产生如此多的冗余数据。事实证明,这种冗余是数据压缩的理想选择。您可以只存储一个副本,而不是存储同一块基因组数据的多个副本。

要压缩基因组数据,您可以先将每个读取的DNA序列分成较小的块,然后为每个块分配一个数字索引。最终,索引的总和构成字典,其中每个条目不是单词而是短序列的DNA碱基对。

文本压缩器以这种方式工作。例如,GitHub拥有一个广泛使用的单词列表,人们可以用它来为每个单词分配自己的数字索引。因此,要将文本段编码为二进制,您将用其数字索引替换每个单词 - GitHub上的列表将数字64,872分配给单词compression - 然后以二进制格式呈现。要压缩二进制表示,您可以按字使用频率而不是字母顺序对字典进行排序,这样更常见的字会获得更小的数字,因此需要更少的位进行编码。

另一个常见的策略 - Lempel-Ziv算法系列 -构建了一个逐渐变长的短语而不是单个单词的字典。例如,如果您的文本通常包含基因组后跟数据,则将为短语基因组数据分配单个数字索引。

许多通用压缩工具,如gzip,bzip2,Facebook的Zstandard和Google的Brotli都使用这两种方法。但是虽然这些工具适用于压缩通用文本,但是为某些类型的数据利用模式而构建的专用压缩器可以大大超越它们。

考虑流视频的情况。视频的单帧及其运动方向使视频压缩软件能够预测下一帧,因此压缩文件将不包括每帧的每个像素的数据。此外,观众可以容忍一些几乎不可察觉的视频信息或失真的丢失,这与基于文本的数据不同。为了利用这一事实,一个国际联盟花了数年时间开发H.264视频压缩标准(现在由Blu-ray Disc,YouTube,iTunes商店,Adobe Flash Player和Microsoft的Silverlight等等)使用。

研究人员同样也在设计用于压缩基因组数据的专用工具,学术文献中每月出现一次新的数据。许多人使用所谓的基于参考的压缩,它以一个人类基因组序列作为参考。任何短的人类DNA序列 - 即一个由100个碱基对或更少组成的序列 - 很可能出现在该参考文献的某处,尽管有测序错误和突变。因此,不是将所有碱基对列在100的字符串中,而是专门的压缩器仅记录字符串在参考中开始的位置(例如,“染色体5中的第1,000个碱基对”)并描述与参考序列的任何偏差(对于例如,“删除第10个碱基对”)。基于参考的方法要求用户拥有大约1千兆字节的参考人类基因组的拷贝,

如上所述,FASTQ文件不仅包含DNA序列,还包含表明潜在错误的质量分数。遗憾的是,基于参考的压缩不能用于压缩FASTQ质量分数,因为质量分数没有参考序列。相反,这些工具会查看质量得分中的模式 - 例如,低质量得分可能会跟随另一个低质量得分,或者在DNA读取开始时质量得分往往高于结束。就像按使用频率降低顺序对所有单词进行编号一样,我们可以压缩文本,按照预测可能性的顺序对可能的质量分数进行编号,这样我们就可以压缩这些数据。研究人员有时会丢弃它,而不是存储和压缩低质量的数据,

这些新型压缩机是一个良好的开端,但它们远非完美。随着我们对数据的理解的发展,我们压缩数据的能力也随之提高。数据压缩迫使我们在数据中寻找非显而易见的模式和冗余; 当我们深入压缩数据时,我们就会知道我们终于明白了。基因组数据压缩器会影响数据中的细微模式,从而缩小文件大小并降低存储成本。

在我们在斯坦福大学进行的研究中,我们做了一个可能有用的观察结果:连续DNA变异之间沿着基因组的距离遵循“双幂定律”分布。您可能熟悉“幂律”分布的概念,其中结果的概率与该结果的反向幅度成比例,可能会提升到某种幂。城市人口通常遵循这样的分布:大约有一半的城市拥有200万人口,而城市拥有100万人口。这项法律也适用于一个国家的财富分配,其中20%的人口拥有80%的财富。

双幂定律包括两种不同的幂律,它们在相同类型的数据上运行但覆盖不同的范围。例如,80/20规则可以通过财富适用于人口的下半部分,而90/10规则适用于上半部分。双电源法则可用于描述Facebook上的朋友数量,电话呼叫持续时间和硬盘驱动器上的文件大小的分布。

事实证明,在DNA碱基对中测量的相邻遗传变异之间的距离直方图看起来像双幂定律,两个幂定律之间的交叉点发生在大约1,000个DNA碱基对[见图,“双权法“]。关于什么进化过程创造了这种分布,这是一个悬而未决的问题,但它的存在可能有助于改进压缩。克劳德·香农在信息理论中的一个基本成就表明,数据不能压缩到香农熵之下 - 香蕉熵的分布随机性的度量。双幂定律分布证明随机性较小 - 也就是说,它具有较低的熵 - 比假设基因组中的每个位置同样可能包含变异的模型。

基因组数据压缩器今天使用的是无损的 - 也就是说,它们允许您恢复未压缩的文件位,就像压缩前一样。但有一种情况是允许一定量的损失,不是在DNA序列中,而是在质量分数中表示测序仪对数据的信心。虽然只有四个DNA核苷酸(A,C,G,T),但通常有大约40种可能的质量得分,因此无损压缩FASTQ文件中的大多数位构成质量得分而不是DNA序列。这种精确度是浪费的,因为使用基因组数据的应用程序倾向于忽略质量分数的微小变化或者可能完全丢弃质量分数。实际上,某些任务的表现,例如在两个基因组之间找到变异,实际上会在质量得分以有损方式压缩时得到改善,

我们还可以通过丢弃其他基因组测序信息来节省存储空间。DNA读取在FASTQ文件中出现的确切顺序对于后续分析通常并不重要:在许多情况下,您可以在识别遗传变异时,以随机顺序对读取进行随机播放,并期望几乎相同的输出。因此,您可以按字母顺序对DNA读取进行排序,然后利用排序列表可以比未排序列表压缩更多的事实。文本压缩中的类似情况是对单词列表进行排序并说明相邻单词之间的距离。词语解压缩和解压缩,例如,是在词典相邻,和它们的最后一个字母(d和小号)在字母表中相隔15个字母,因此您可以使用整数15对整个第二个单词进行编码。

作为这种方法如何在DNA上工作的一个例子,让我们按字母顺序对序列ACGAAA,ACGAAG和ACGAAT进行排序。前五个字母都是一样的,所以我们只对第六个字母之间的差异感兴趣。然后将第二个序列编码为整数2(因为最后一个字母G是核苷酸字母表ACGT中A之后的两个字母),第三个序列编码为1(因为它的最后一个字母T是一个字母)在G)之后。相对于以原始顺序存储DNA读数,该方法可以导致两倍或更多的节省。

当然,压缩比只是压缩工具功能的一个衡量标准。速度是另一个因素。一些专用的FASTQ压缩机并行运行,节省了单CPU实现的时间; 其他人则利用GPU和现场可编程门阵列处理器,这些硬件更常用于加速视频处理和机器学习。另一个有用的功能是能够搜索压缩数据。您不希望必须解压缩整个文件,以便快速搜索其中特定DNA序列的出现。

虽然许多基因组压缩选项正在出现,但现在需要的是标准化。正如视频压缩技术无法起飞直到行业的很大一部分同意标准,基因组压缩技术将不得不转向一个标准或至少一小部分标准。

幸运的是,已开始研究基因组测序数据的压缩标准。该运动图像专家组(MPEG)所开发的MP3音频格式,并-the同体的几个流行的视频格式,几年来一直在开发用于压缩基因组数据标准,名为努力MPEG-G 。该规范预计将于今年晚些时候完成。该标准将随着技术的改进而发展,就像视频压缩标准一样。

我们开发高效,健全和标准化的基因组数据压缩的速度仅仅是经济问题。随着存储数据量的急剧增加以及存储成本变得繁重,降低成本将推动行业采用更好的压缩方法。

目前,随着序列数据总量的累积,基因组研究可能会获得意想不到的好处; 今天,该领域大约是十年前的人工智能领域。最近AI的巨大进步在很大程度上得益于大量数据集的可用性; 在使用大量数据集时,对中等数据量表现不佳的深度学习算法变得非常强大。基因组研究人员已经开始对他们的数据应用深度学习,但他们可能不得不等待大量的基因组信息积累才能实现类似的收益。但有一件事是清楚的:如果没有基因组数据压缩技术的重大进展,它们将无法实现。

免责声明:本网站图片,文字之类版权申明,因为网站可以由注册用户自行上传图片或文字,本网站无法鉴别所上传图片或文字的知识版权,如果侵犯,请及时通知我们,本网站将在第一时间及时删除。