LFQC：FASTQ文件的一种无损压缩算法外文翻译资料

 2022-10-31 14:44:34

英语原文共 6 页，剩余内容已隐藏，支付完成后下载完整资料

LFQC：FASTQ文件的一种无损压缩算法

摘要

动机：通过减少全基因组测序的花费，下一代测序（NGS）技术已经彻底改革了基因组的研究。现代测序技术带来的最大挑战之一就是下一代测序数据的经济性存储。由于其庞大的尺寸和高度的冗余，存储原始数据是不可行的。本文中，我们使用创新的压缩技术解决存储和大型FASTQ文件的传输问题。

结果：我们基于无损FASTQ压缩器，提出了一个新的无损非参考压缩算法。我们比较了我们的算法和其他先进的大数据压缩算法gzip，fastqz（Bonfield和Mahoney，2013），fqzcomp（Bonfield和Mahoney，2013），Quip（Jones 等人，2012），DSRC2（Roguski和Deorowicz，2014）。比较证明在LS454和SOLiD数据集上，我们的算法达到了更好的压缩率。

可用性和实现：非商业性目的的实现是免费可用的，可以从http://engr.uconn.edu/rajasek/lfqc-v1.1.zip下载到。

联系方式：rajasek@engr.uconn.edu。

1 介绍

由于下一代测序（NGS）的先进性，研究者开始面临存储巨大数量数据的问题。现代测序技术产生的Pb级的数据需要庞大的设施来将其存储到硬盘上以供当前和未来的分析。下一代测序数据容量的增长速率已经远超了硬盘花费的下降速率，因此，科学家们认识到需要新的更加精致的软件来对原始数据进行经济的存储。并且，测序技术产生的庞大文件的传输会耗费大量的时间，导致研究和分析的严重延期。科学家们发现的另一个事实是下一代测序数据包含大量的冗余，可以在传输之前进行有效地压缩。可以在文献中找到大量的通用压缩算法。但是，这些算法已被证实对测序数据表现不佳。因此，我们投入了时间和精力来研发新的特定领域的压缩算法用于大型生物数据文件的压缩。正如Giancarlo 等人（2009）提到的，FASTQ文件的压缩是计算机生物学中一个重要的研究领域。下一代测序数据一般以FASTQ格式进行存储。FASTQ文件包含数百万到数十亿条记录，每条记录包含以下四行：

  • 第一行保存一个标识符。以 @ 开始，后面跟序列标识符和可选的描述。
  • 第二行表示读序列。其本质就是字母的序列。
  • 第三行以 开始，后面有时跟与第一行相同的序列标识符。
  • 第四行表示质量评分。这是一串字符。第二行和第四行的长度必须相同。

测序仪器为序列中的每个碱基生成DNA序列和一个概率值P。P值是碱基出错的概率。后来这些错误概率被量化为整数。在Ewing和Green（1998）的算法中，错误概率被转换为PHRED质量评分后存储。转换给出Q = -10 。那么质量评分Q被截断并过滤在范围0到93之间。每个整数都增加了33，因此值的范围是33到126。该实现能够将评分以可输出的ASCII字符的形式输出。这种格式被称为SANGER格式（Cock 等人，2010）。

核苷酸序列的压缩一直是一个有趣的问题。Cox 等人（2012）应用Burrows-Wheeler变换（BWT）进行基因组序列的压缩。GReEn（Pinho 等人，2012）是一个基于参考的序列压缩方法，能够达到一个很好的压缩率。（压缩率是指原始数据大小与压缩数据大小的比率）。压缩序列以及质量分数和标识符一个非常不同的问题。Temble 等人（2010）已经将Qscores与相应的DNA碱基连接以从基础Q评分对产生新的符号。他们使用哈夫曼编码（Huffman，1952）对每个这样不同的符号进行编码。Deorowicz和Grabowski将质量评分划分为三种质量流：

  1. 准随机性，轻度依赖质量评分位置。
  2. 准随机质量评分，以几个#字符结束的字符串。
  3. 质量评分，个别记录中具有强烈局部相关性。

为了表示案例2，他们使用了一个位标志。任何具有特定位标志的字符串都被进行删除所有尾部的#字符的处理。他们划分质量评分得到单独的块，并应用哈夫曼编码。Tembe 等人（2010）和Deorowicz和Grabowski（2011）同样证实了通用压缩算法效果不好，急需特定领域算法来对FASTQ文件进行高效压缩。在他们的论文中证明相比于bzip2和gzip，使用特定领域算法可以在压缩率上有重大改进。FASTQ压缩的文献可以分为两类，无损压缩和有损压缩。无损压缩的机制是我们在压缩后的文件中保留所有的数据。相反，有损压缩技术允许在压缩过程中丢失一些不重要的数据组成。Kozanitis 等人（2011）执行随机舍入来进行有损编码。Asnani等人（2012）针对质量评分编码提出了一种有损压缩技术。Wan等人（2012）针对序列压缩和编码提出了有损和无损转换。Hack等人（2012）提出了一个“推进”方案，该方案重组读长以便实现更高的压缩速度和压缩率，而与使用的压缩算法无关。当涉及到医疗数据压缩时，很难确定哪些部分是不重要的。因此，许多研究人员认为生物/医学数据特别需要无损压缩技术。Quip（Jones等人，2012）就是这样一个无损压缩工具。它单独压缩标识符，序列和质量评分。Quip利用马尔科夫链编码序列和质量评分。我们在本文中与我们的算法进行比较的DSRC（Deorowic和Grabowski，2011）也被认为是一个最新技术的无损压缩算法。Bonfield和Mahoney（2013）最近提出了一套算法（名为Fqzcomp和Fastqz）来压缩FASTQ文件。他们通过存储当前标志位和之前的标志位之间的差异来执行标志位压缩。序列压缩通过使用一组技术进行，其中包括碱基对压实，编码和阶数k模型。除了哈希，他们还使用通过预测对质量值进行编码的技术。

Kozanitis等人（2011）和Fritz等人在基于参考的压缩技术上做出贡献。这个想法是使用参考基因组对齐读长。这种方法存储基因组的位置和所有的不匹配，而不是存储序列。基于参考的压缩的一个主要优点是随着读取长度的增加，相比于基于非参考算法，它产生更好的压缩率。尽管提供了优秀的序列压缩率，基于参考的压缩技术有很多缺点。这些算法的成功完全取决于可用的好的参考基因组数据库，但这并不能总是被保证。创建这样的数据库本身是一个具有挑战性的问题。而且，基于参考的压缩技术不是自包含的。解压缩技术需要精确的参考基因组来匹配基因组位置并提取读数。因此，保存参考基因组是很重要的。

在本文中，我们提出了一个基于非参考的FASTQ压缩算法称为LFQC（无损FASTQ压缩器），可以优雅地在商品机器上运行。该算法可以在内核以及外核设置中运行。本文的余下部分组织如下：第二节描述FASTQ结构并提供有关所涉步骤中关于FASTQ文件压缩的详细信息。第三节提供解压算法的详细信息。在第四节，我们比较LFQC和其他先进的算法并提供性能结果。在第五节和第六节，我们分别提供未来的指导和结论。

2 FASTQ文件压缩

FASTQ文件由每个有四行的记录组成。示例记录如下所示：

@SRR013951.81530PT5AAXX : 8 : 1 : 14 : 518

AGTTGATCCACCTGAAGAATTAGGA

I1IFI0IEI [dollar]II5IIICBC(1B)0

文献中发现了集中FASTQ压缩算法分别压缩记录的四个字段。我们在我们的算法LFQC中也使用这种方法。在LFQC中，每个流都通过预处理算法，然后由通用数据压缩器压缩。我们使用的数据压缩器是zpaq v7.02(http://mattmahoney.net/dc/zpaq.html) 和 lpaq8 (http://cs.fit.edu/mtilde; mahoney/compression/#lpaq)。每个流使用哪个压缩器将在下一节讨论。

2.1 压缩标识符字段

标识符字段是非常系统地生成的。这个性质可以应用于压缩该字段。我们下面提供一个Illumina生成的标识符作为例子。

HWUSI_EAS687_61DAJ:8:1:1055:3384/1

标识符由以下几个字段集组成：工具名称，流动单元通道，流动单元通道内的瓦片数，瓦片内群集的“x”坐标，瓦片内群集的“y”坐标，用于复用样本的索引号和指示该序列是否是一组的成员的字段。大多数时候标识符签名的是数据集名称。经过学习大量的FASTQ文件，我们发现标识符可以分为四种类型的标记。

类型1：具有从一个记录到下一个记录不更改的数据的标记。

类型2：在一组连续记录上具有相同数据值的标记。

类型3：具有在连续记录上单调递增或递减的整数值的标记。

类型4：具有不属于上述任何类型的数据的标记。

我们用于压缩标识符的算法如下。首先，我们将每个标识符分成记号。假设I表示任意标识符，表示I的从第i个位置到第j个位置的子字符串。如果发生以下情况，我们扫描每个标识符I并提取作为一个标记：和属于以下字符集：点（.），空格（ ），下划线（_），连字符（-），斜杠（/），等号（=）或冒号（:）。我们把这些符号称为关键符号。下例提供了如何将标识符划分为标记的说明。假设标识符为@SRR007215.1135HWUSI-EAS 687_61DAJ:8:1:1055:3384/1。我们将标识符划分为以下标记：

  • 标记1：@SRR007215
  • 标记2：1135
  • 标记3：HWUSI
  • 标记4：EAS687
  • 标记5：61DAJ
  • 标记6：8
  • 标记7：1
  • 标记8：1055
  • 标记9：3384
  • 标记10：1

分割标志符的过程被称为标记化。标记化还产生由占位符组成的正则表达式，其本质是上述的标记数字和字符集C。这个正则表达式帮助我们在解压缩时重建标识符文件。上述例子的正则表达式为：

，

其中表示第i个标记。解压算法用每个替换相应的值并构建标识符。伪码的标记化算法在算法1中给出。

假设每个标识符中存在的标记的数量为t。标识符中的标记为，，，hellip;hellip;，。所有的输入记录的标识符为，，hellip;hellip;，。表示所有标记符的标志集合中的第i个，1le;ile;t。每个叫做一个标志集（1le;ile;t）。我们首先构造这些标记集。随后，我们必须选择一种适当的技术来压缩每个标记集。我们假设表示压缩后的，1le;ile;t。我们使用的压缩技术如下所示。

  • 游程编码：使用游程编码压缩带有字母数字值的标记集。如果游程编码不能将标记集的大小减小到原始值的90%以下，则标记集保持未压缩状态。注意，对于在整个数据集中具有常量值的标记集，此压缩技术将将集合减少为两个值：常数值后面跟计数。
  • 增量编码：通过存储连续标记之间的差异来压缩具有整数值的标记集。如果该方法不能将标记集的大小减小到原始值的90%以下，则标记集保持未压缩状态。
  • 如果标记集没有被上述任何方法转换，则我们取每个标记集并将其反转（从右到左读取）。我们已经观察到这倾向于提高下游应用的上下文混合算法的压缩率。

算法1

1：标记化步骤

2：C larr; {., ,-, ,:}

3：A是所有所有字符的集合

4：for 输入中的每个标识符I do

5： for 1le;i＜jle;n（n=|I|）do

6： if C 并且 C then

7： larr; 其中 是第k个标记

8： 表示I的从第i个位置到第j个位置

9： 的子字符串。

10： end if

11： end for

12：end for

在对每个标记集应用上述变换之后，将标准上下文混合压缩算法应用于变换后的字符串。特别地，我们使用zpaq，参数为“-method 5 -threads 4”。

如上所述，标识符压缩算法还生成用于在对各个压缩标记集文本解压后重建原始文本的正则表达式。我们分别在算法2和算法3中提供标志符压缩算法和增量编码的伪代码。标识符压缩算法还记录用于每个，1le;ile;t，的压缩的编码算法。标识符压缩算法将压缩后的标记集<a

剩余内容已隐藏，支付完成后下载完整资料</a

资料编号：[141659]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章