这是用户在 2024-5-7 16:02 为 https://app.immersivetranslate.com/pdf-pro/049cfd9f-8bce-4c91-80e9-e7a7692045a3 保存的双语快照页面,由 沉浸式翻译 提供双语支持。了解如何保存?
2024_05_07_194688a8a007543a820eg


ACO:基于自适应编码顺序的无损质量分数压缩

Xidian University

 马光明

Xidian University

Li Fu

Xidian University

 刘先明

 鹏程实验室

 石光明

Xidian University

 研究文章


关键词高通量测序、质量分数压缩、无损压缩、自适应编码顺序

发布日期2021 年 4 月 22 日

授权许可:@ (1) 本作品采用知识共享 署名 4.0 国际许可协议进行许可。
 阅读完整许可证


ACO:基于自适应编码顺序的无损质量分数压缩

Yi Niu , Mingming Ma , Xianming and Guangming Shi

 摘要


背景:随着高通量测序技术的快速发展,全基因组测序的成本迅速下降,导致基因组数据呈指数级增长。虽然近年来 DNA 碱基的压缩技术取得了显著的进步,但质量分数的压缩仍然是一项挑战。


结果本文通过重新研究质量分数与排序过程之间的内在关联性,提出了一种基于自适应编码顺序(ACO)的新型无损质量分数压缩器。自适应编码顺序的主要目的是根据排序过程,以最相关的轨迹自适应地遍历质量分数。通过自适应算术编码和上下文建模的配合,ACO 以中等的复杂度实现了最先进的质量分数压缩性能。


结论ACO 已被 AVS(中国音视频编码标准工作组)采用,并可在 https://github.com/Yoniming/code 免费获取。


关键词高通量测序;质量分数压缩;无损压缩;自适应编码顺序

Background


测序技术已逐渐成为生物研究中广泛应用的基础技术[1]。获取不同生物的遗传信息可以帮助我们增进对有机世界的了解。在过去的几十年里,人类全基因组测序(WGS)的价格已经降到了 以下,其下降速度超过了摩尔定律的预期[2]。在这种情况下,下一代测序(NGS)数据的数量呈指数级增长,甚至超过了天文数据[3]。如何有效压缩大规模基因组项目产生的 DNA 数据,已成为制约 DNA 测序行业进一步发展的重要因素。

DNA 数据压缩有两个主要问题:核苷酸压缩和质量分数压缩。质量值占压缩数据的一半以上,而且已被证明比核苷酸数据更难压缩 。尤其是随着组装技术的发展 ,核苷酸压缩的难度更大。

已取得重大改进,这使得质量分数压缩问题成为当前 DNA 数据存储和传输应用中的主要瓶颈之一。

质量得分(QS)代表测序过程中每个碱基字符的置信度,但其字母表更大(41-46 个不同等级)。文献[7]揭示了相邻质量得分之间存在很强的相关性,这可以被视为当前无损质量得分压缩流水线的基础:1)使用马尔可夫模型估计质量得分的条件概率;2)通过光栅扫描顺序遍历读数的每个位置;3)通过算术或范围编码对质量得分进行编码。

在上述管道的基础上,提出了 GTZ[8]、Quip[9] 和 FQZcomp [5]三种不同的无损压缩器。这三种压缩器的区别仅在于马尔可夫模型阶数和上下文量化策略,因此压缩率在 左右,具体取决于数据分布。这就不可避免地提出了一个负面观点,即无损压缩率的进一步提高空间不大。

本文通过对测序过程的重新研究,揭示了现有基于光栅扫描的质量分数压缩策略的两个主要缺点。首先,光栅扫描顺序是一种 "深度优先 "的读取遍历策略。然而,正如文献[7]所指出的,质量得分沿着单个读数呈下降趋势。这使得马尔可夫模型的片断静止假设站不住脚。其次,考虑到测序过程是由 多光谱成像 ,但 FASTQ 文件只是将质量得分存储到一维信号的堆栈中。基于光栅扫描的技术对每个读数进行独立压缩,无法探索空间相邻读数(而非 FASTQ 文件中的相邻读数)之间潜在的二维相关性。

为了克服上述两个缺点,我们提出了一种基于自适应编码顺序(ACO)的新型质量分数压缩技术。 的主要目标是沿着最相关的方向遍历质量分数,这可以被视为将独立的一维质量分数向量堆重组为高度相关的二维矩阵。与现有技术相比,拟议 ACO 技术的另一项改进是复合上下文建模策略。我们将在 "方法 "部分详细说明,ACO 上下文模型由两个额外方面组成,而不是相邻的 QS 值:1) 每个读数的全局平均值;2) DNA 碱基的变异。复合上下文模型不仅有利于概率估计和算术编码,更重要的是,在实现过程中,它避免了 ACO 对输入 FASTQ 文件的多次随机访问:压缩过程只需一条路径即可完成,但代价是一些上下文稀释和副信息。

实验结果表明,所提出的 ACO 技术在无损质量分数压缩方面达到了最先进的水平,与 FQZcomp 相比,其压缩率提高了 [5]。ACO 的唯一缺点是内存成本,与 FQZcomp 相比,ACO 需要分别增加 内存来缓冲 质量得分矩阵和存储复合上下文模型,这对于目前的 PC 机来说应该不再是一个大问题。

 声明


本节首先分析质量得分的数据特征,通过具体实例说明编码序列会对质量得分压缩产生一定影响,从而推动我们沿着数据相关性最强的方向压缩质量得分。其次,通过分析 FASTQ 文件的测序原理和生成过程,挖掘质量得分数据中的额外相关性,从而建立一个新颖的复合上下文量化模型。

编码顺序的影响

质量得分是对读数中相应核苷酸错误概率的估计,也是对碱基特征可靠性的评估。这些信息既可用于原始数据的质量控制,也可用于下游分析。我们在图 1 中给出了ERR2438054 四个读数的质量得分分布情况,可以看出,由于受到噪声的影响,质量得分是一个随机的、不稳定的信号,相邻质量得分之间存在很强的相关性。因此,我们可以利用质量分数的这些特点来改变编码顺序,从而提高压缩比。改变顺序听起来并不像改变熵值,因为根据信息论,信源的信息量是概率的函数,用信源的信息熵来表示。但是,由于在编码中使用了自适应算术编码器,编码器会定期更新符号概率,因此改变阶次可以减小比特流的大小。关于算术编码器原理的讨论不是本文的主要内容,因此我们只给出一个测试实验来说明编码顺序对压缩结果的影响。首先,我们创建两个随机信号 ,并让 。然后,随机扰乱 的分布并将其记录为 ,按大小排序 的分布并将其记录为 Z3。最后,三组不同的信号通过 0 阶算术编码器进行编码,比特流的结果为 。这是因为排序过程相当于把分布相似、相关性强的数据放在一起。改变顺序后的编码能更好地配合自适应算术编码器的概率更新机制。

图 1:图 1


挖掘更多相关信息


以目前广泛使用的 Hiseq 测序平台为例,测序过程包括三个步骤:1)构建 DNA 文库;2)通过桥式 PCR 扩增生成 DNA 簇;3)测序。本文对测序步骤进行了重新研究,以挖掘更多质量得分之间的内在联系,从而帮助完成压缩任务。测序的基本原理基于流式细胞的多光谱成像。流式细胞是测序的载体,每个流式细胞有八个内表面经过化学修饰的泳道。每个泳道包含 96 块瓷砖,每块瓷砖都有一个独特的簇。每个簇对应一个 DNA 片段,因此一个流动池可同时产生 768 个 DNA 读数。

如图 2 所示,测序过程包括五个步骤。第一步,在流动池中加入聚合酶和一种 dNTP,以激活特定簇的荧光。第 2 步,多光谱照相机根据添加的 dNTP 用特定波长拍摄流动池。然后在步骤 3 中,采用化学试剂冲洗流动池,为下一次成像做准备。以上三个步骤重复四次,使用不同的 dNTP 和不同的成像波长,得到四通道多光谱图像。在步骤 4 中,测序仪根据采集到的四通道图像,不仅能估计出每个团簇最可能的类型,还能评估估计结果的可信度,分别存储为碱基和质量得分。步骤 1-4 被视为一个测序周期,对流池中所有 768 个读数的一个位置(深度)进行测序。因此,在步骤 5 中,测序周期会重复多次,重复的周期数与读数的长度相对应。

正如我们在下文中详细讨论的,有三个方面与质量分值相对应:1) 周期数;2) 基数变化;3) 芯片的局部位置。

循环次数会影响质量得分的分布。在合成和测序过程中都会用到 DNA 聚合酶,在测序初期,合成反应不是很稳定,但酶的质量很好,所以会在高质量区域波动。随着测序的进行,反应趋于稳定,但酶的活性和特异性逐渐降低,累积误差逐渐放大。因此,出错概率增加,总体质量得分呈下降趋势。如图 3 所示,随着测序的进展,质量得分的平均值逐渐降低,而方差却在增加。因此,按照传统的光栅扫描顺序将每个读数都假定为静止的随机信号是不妥当的。

碱基变化也会影响质量得分的分布。正如我们之前所讨论的,流式细胞中碱基类型的识别是按照 dNTP 和波长的顺序以四步循环的方式进行的。例如,假设循环顺序为 "A-C-G-T",如果读取的碱基为"...AA......",在第一个 " "成像后,流式细胞将被清洗四次,直到第二个 " "成像。但如果读数为"...TA...",机器在 " "成像前只清洗一次流动池。这样,如果流式细胞簇中含有一些残留物,前一个 "A "碱基就会影响后一个 " "碱基的成像过程,从而可能导致 " "的模糊性,使 " "的质量得分大幅下降。虽然有些机器采用了复合 dNTP 来代替四步循环,但残差仍然会影响质量得分。因此,在压缩质量得分时,应将碱基变化作为一个侧面信息来建立每个质量得分的边际概率模型。

芯片的局部位置会影响质量得分的分布。流式细胞可被视为一个二维阵列,每个簇都对应阵列的一个条目。如果一个条目的荧光振幅较高,就可能向阵列的相邻条目扩散,这就是著名的 "串扰 "现象[11]。换句话说,相邻质量得分之间存在 空间相关性。然而,存储的 FASTQ 文件是所有读数的一维堆栈,忽略了 相关性。因此,质量得分的压缩应该挖掘读数之间潜在的二维空间相关性。

图 3:FASTQ 质量得分的分布情况

Methods


在本节中,我们将讨论所提出的基于自适应编码顺序(ACO)的质量分数压缩技术。ACO 的两个贡献是:1)使用自适应扫描顺序取代传统的光栅扫描顺序,后者形成的信号更加固定。2) 使用复合上下文建模,在探索质量分数之间潜在 相关性的同时,考虑基数变化的影响。


沿着最相对的方向遍历质量得分


从图 3 中可以看出,随着读数长度的增加,列均值减小,但方差变大,这证明列与列之间存在很强的相关性。同时,列均值的减小也与具体测序过程中质量得分沿着单个读数呈下降趋势的实际情况相吻合。由此可以验证,改变扫描顺序可以提高自适应算术编码器的性能,沿着更稳定的信号进行编码可以获得更好的编码效果。

所有基于算术编码器的压缩方法在遍历数据编码时都使用图 4(a)中的扫描方法。在这种扫描方法下,质量分数是逐行编码的,扫描完一行后,下一步从第二行开始。显然,在对前一行的最后一个字符进行编码后,连接下一行的第一个字符会产生很大的跳变,这种跳变会使信号之间的转换不稳定。因此,我们采用自适应扫描顺序来取代传统的光栅扫描顺序,从而实现信号的稳定遍历,如图 4(b)所示。起点从第一个元素开始,向下遍历一列,直到一列结束,然后从下一列结束处向上遍历。与传统的扫描方式不同,ACO 采用的是一种类似蛇形的扫描方式。采用蛇形遍历的原因是为了使列与列之间的过渡更加平滑,一列的末尾符号与下一列的末尾符号更加相关,红绿符号之间的相关性明显强于红蓝符号之间的相关性。因此,在对红色符号进行编码后,选择绿色符号比蓝色符号更适合从第二列开始编码。通过改变扫描顺序,编码可以朝着更稳定的方向进行。在不引入其他因素的情况下,自适应算术编码器的概率更新机制得到了充分利用。
(a)
(b)

图 4:传统扫描与 ACO 扫描的比较:(a)传统遍历方法;(b)自适应扫描顺序复合上下文建模

正如声明部分所述,质量得分的压缩应挖掘读数之间潜在的二维空间相关性,因此我们使用复合上下文建模来表达质量得分数据中的额外相关性。ACO 上下文模型还包含两个方面,第一个方面是获取每个读数的全局平均值。根据《宣言》中的例子可以看出,调整数据顺序,使相似符号聚类在一起,会得到很好的压缩效果。如图 1 所示,四个读数的分布曲线非常相似,只有一些奇异点存在差异。因此,对具有相似行分布的数据进行聚类和编码是一种改进策略,但计算每一行的分布需要很多步骤,而且对相似行进行聚类也会带来时间和空间上的损失。我们计算每一行的平均值信息,以反映其分布情况,并对平均值相同的行进行分类。对于行信息来说,均值是静止性的衡量标准,均值相同的行可以近似地认为整行的分布基本相同,尽管一些奇异点可能会使分布曲线不完全重合。使用行均值可以节省大量的计算量和时间,而不需要计算行间的库尔贝克-莱伯勒离差,同时也不会浪费行均值。


行之间的相关性。行聚类法需要向解码器传输额外的信息来记录行序的变化,面临同样的问题,使用均值法也需要向解码器传输每行的均值信息。在实际应用中,我们会比较行均值带来的额外编码量和实际收益值。当收益大于原值时,我们会选择添加行均值信息作为上下文。

具体来说,在建立上下文模型的过程中,会出现上下文稀释的问题,因此我们需要设计一种合适的均值量化方法,从而解决上下文稀释的问题,这是一个动态编程问题,离散分布随机变量量化的优化目标是使失真最小。目标的表达式为

其中, 是概率不为零的 值, 的量化值, 是特定的失真度。我们可以定义一个条件集 ,表示每个特定的 对应于一个特定的 值。定义一个量化集 ,其中 代表量化变量,所以 ,如果 。因此,每个子集 对应于 的一个分区,该分区有 的表达式如下: