一种面向多条序列的基因序列数据压缩方法

摘要

本发明提出一种面向多条序列的基因序列数据压缩方法，主要用于解决基因数据量过大，减小基因数据存储和传输成本问题。首先从待压缩基因序列中选取参考序列，其次，将非参考序列和参考序列采用不同的压缩方式进行压缩。对于非参考序列，通过与参考序列异或，然后进行矩阵划分和矩阵编码，最终将基因序列编码成二元组形式进行存储；对于参考序列，采用k‑mer算法进行单独压缩。采用本压缩方法的压缩比高，压缩速度快，而且二元组编码与基因次序无关，有利于分布式存储和分析基因序列。

权利要求

1.一种面向多条序列的基因序列数据压缩方法，其特征在于，包括步骤：

(1)参考序列选取：记待压缩基因序列共n条，将待压缩基因序列通过数字化映射为欧氏空间的高维数字向量，然后对每一条待压缩基因序列，计算其与其他n-1条待压缩序列之间的欧式距离的和，并将欧式距离的和的值最小的待压缩基因序列作为参考序列；

(2)将待压缩基因序列与参考序列进行对齐：按照从头到尾的顺序遍历待压缩基因序列，将待压缩基因序列中的每一位与参考序列中的相应位比较；当遇到待压缩基因序列相对于参考序列多出的部分，则将多出的部分内容从待压缩基因序列中删除，将删除的内容以四元组的形式单独挂接在待压缩基因序列尾部，四元组的形式为：(T,P,L,C)，其中，T表示挂接类型，挂接类型分为删除或增加，P表示删除的内容在待压缩基因序列中的位置，L表示删除的内容的长度，C表示删除的内容；当遇到待压缩基因序列相对于参考序列缺少的部分，则在待压缩基因序列中相应位置处补齐缺少的部分，然后将补充的内容以三元组的形式挂接在待压缩基因序列尾部，三元组的形式为：(T,P,L)；

(3)采用基于k-mer算法的分段编码方法将参考序列进行单独压缩；

(4)对包含参考序列在内的所有基因序列进行二进制编码，将所有基因序列转换成二进制比特序列；

(5)将待压缩基因序列与参考序列进行异或，异或处理后，待压缩基因序列中与参考序列相同的部分均为0，而不同的部分为1；

(6)将与参考序列异或后的待压缩基因序列进行矩阵化：记参考序列的二进制长度为l，选取适当的w，把每一条待压缩基因序列划分成w宽的等份，放入一个二维矩阵中；其中，第一条待压缩基因序列的第一段作为二维矩阵的第一行，第二条待压缩基因序列的第一段作为二维矩阵的第二行，以此类推，直至第n-1条待压缩基因序列的第一段作为二维矩阵的第n-1行；然后，将第一条待压缩基因序列的第二段作为二维矩阵的第n行，将第二条待压缩基因序列的第二段作为二维矩阵的第n+1行，以此类推，直到n-1个序列全部输入二维矩阵；

至此，所有待压缩基因序列转换成一个宽为w，长为(n-1)*l/w的二维矩阵；

(7)对步骤(6)得到的二维矩阵进行编码：将二维矩阵划分成若干个子矩阵，子矩阵中元素全为1；对每个子矩阵进行以下编码：对于只有一个元素的子矩阵，将该元素编码设置为-1；而对于具有2个及以上元素的子矩阵，将其左上角元素设置为1，右下角元素设置为2，其余元素设置为0；

(8)对经过步骤(7)处理后的待测基因序列进行存储：以二元组的形式按次序记录二维矩阵中值为1、2、-1的元素的行号和列号，将待压缩基因序列的信息转换成一个二元组信息；对二元组中的元素实行熵编码，即使用变长编码的方式对于小于255的元素以一个字节长度存储，对于大于255小于65535的元素以两个字节存储，对于大于65535的元素以三个字节存储。

2.根据权利要求1所述的一种面向多条序列的基因序列数据压缩方法，其特征在于，所述步骤(3)中采用基于k-mer算法的分段编码方法将参考序列进行单独压缩的具体步骤为：首先将参考序列分成长度为m的等长片断，再选取适当的k值，搜索每个片断中重复率最高的k-mer序列，并记录其重复的总次数及每一次重复在该片断中的位置，然后进行分段编码，以替代序列中重复出现的k-mer子序列。

说明书

一种面向多条序列的基因序列数据压缩方法

技术领域

[0001] 本发明涉及大数据领域中的基因序列压缩技术领域，尤其是一种面向多条序列的基因序列数据压缩方法。

背景技术

[0002] 基因是DNA上有遗传效应的片断，和生命息息相关。对基因数据的研究可以获得对生命运行机制和疾病机理等的深入研究，在生物医药学和相关生物技术产业发挥着越来越重要的作用，研究人类基因对于推动精准医疗，助力解决三大民生问题之一的医疗问题，具有重要的作用。因此，基因数据因其重要的社会价值和科研价值受到国际社会的广泛重视。自1990年正式启动的国际人类基因组计划以来，随着基因测序技术的不断进步，基因测序成本的不断降低，测序速度不断提高，众多国家和组织纷纷启动基因工程计划。2017年12月
28日，我国启动“中国十万人基因组计划”，这是我国在人类基因组研究领域实施的首个重大国家计划，也是目前世界最大规模的人类基因组计划。随着各种测序项目的展开，产生的序列数据量呈指数规模增长，而且未来增长速度会更快。基因数据增长的速度大大超过了存储和传输带宽增长的速度，给存储和传输带来了很大的压力。如何以更高的效率存储基因数据，减轻存储和传输压力，在基因研究和应用中有着十分重要的作用。

[0003] DNA序列数据具有与其他数据截然不同的特性，DNA序列是仅由A、G、C、T四个符号构成的超长序列，构成种类简单但是序列长度巨大。很大一部分DNA序列至今无法确定其用途，如果数据压缩过程中出现丢失，可能造成不可估量的损失，所以DNA序列必须保证无损压缩。另外，DNA序列中碱基对的排列并不是随机的，具有特定的概率分布和规律性。而且，DNA序列具有高度的相似性。首先，不同物种间的DNA序列相似度很高，同一物种间的DNA序列相似性更为明显。其次，同一个体内的不同片断的DNA序列也存在着许多精确重复。利用DNA这些信息特点，工业界和学术界提出了众多利用DNA序列特征的DNA序列压缩方法。经过对现在技术的文献检索发现，2000年T Matsumoto和K Sadakane在Genome Informatics上的“Biological sequence compression algorithms”提出了CTW+LZ方法，将上下文树加权(Context Tree Weighting，CTW)方法和LZ压缩方法相结合，使用多个编码模型对DNA序列的不同片断进行压缩。2002年，X Chen和M Li在Bioinformatics上的“DNACompress：fast and effective DNA sequence compression”提出了DNACompress压缩方法，使用了Pattern Hunter工具搜索DNA序列的重复与近似重复片断，提高了方法的整体速度。2005年，G Korodi和I Tabus在ACM Transactions on Information Systems上的“An Effective Normalized Maximum Likelihood Algorithm for DNA Sequence Compression”提出了GeNML方法，对具有不同数据特点的DNA片断使用不同的编码策略和概率模型进行压缩。2013年，Sebastian Wandelt and Uif Leser在IEEE/ACM Transactions on Computational Biology and Bioinformatics的“FRESCO：Referential Compression of Highly Similar Sequences”提出了一种叫FRESCO的快速基因压缩方法，它采用了一种用参考基因来表示被压缩基因的方法。2015年，Xiaojing Xie，Shuigeng Zhou和Jihong Guan在IEEE/ACM Transactions on Computational Biology and Bioinformatics的“CoGI：Towards Compressing Genomes as an Image”上提出了一种用图模型来表示基因数据，从而可以利用图压缩技术来压缩基因模型的方法。总结这些DNA序列压缩方法，可以将这些压缩方法分为两大类：基于非参考序列的DNA序列压缩方法和基于参考序列的DNA序列压缩方法，这些方法都有效的提高了压缩比和压缩效率。但这些方法中，组成基因片断的生物信息特征及片断内部的细节重复特性并没有被充分发挥利用，基因序列之间的特征也还没有被充分挖掘，导致DNA序列的压缩比和压缩效率较低。

发明内容

[0004] 发明目的：为弥补现有技术的不足，本发明提出一种面向多条序列的基因序列数据压缩方法，该方法能显著提高压缩效率，实现高效存储。

[0005] 技术方案：为实现上述技术效果，本发明提出以下技术方案：

[0006] 一种面向多条序列的基因序列数据压缩方法，包括步骤：

[0007] (1)参考序列选取：记待压缩基因序列共n条，将待压缩基因序列通过数字化映射为欧氏空间的高维数字向量，然后对每一条待压缩基因序列，计算其与其他n-1条待压缩序列之间的欧式距离的和，并将欧式距离的和的值最小的待压缩基因序列作为参考序列；

[0008] (2)将待压缩基因序列与参考序列进行对齐：按照从头到尾的顺序遍历待压缩基因序列，将待压缩基因序列中的每一位与参考序列中的相应位比较；当遇到待压缩基因序列相对于参考序列多出的部分，则将多出的部分内容从待压缩基因序列中删除，将删除的内容以四元组的形式单独挂接在待压缩基因序列尾部，四元组的形式为：(T，P，L，C)，其中，T表示挂接类型，挂接类型分为删除或增加，P表示删除的内容在待压缩基因序列中的位置，L表示删除的内容的长度，C表示删除的内容；当遇到待压缩基因序列相对于参考序列缺少的部分，则在待压缩基因序列中相应位置处补齐缺少的部分，然后将补充的内容以三元组的形式挂接在待压缩基因序列尾部，三元组的形式为：(T，P，L)；

[0009] (3)采用基于k-mer算法的分段编码方法将参考序列进行单独压缩；

[0010] (4)对包含参考序列在内的所有基因序列进行二进制编码，将所有基因序列转换成二进制比特序列；

[0011] (5)将待压缩基因序列与参考序列进行异或，异或处理后，待压缩基因序列中与参考序列相同的部分均为0，而不同的部分为1；

[0012] (6)将与参考序列异或后的待压缩基因序列进行矩阵化：记参考序列的二进制长度为1，选取适当的w，把每一条待压缩基因序列划分成w宽的等份，放入一个二维矩阵中；其中，第一条待压缩基因序列的第一段作为二维矩阵的第一行，第二条待压缩基因序列的第一段作为二维矩阵的第二行，以此类推，直至第n-1条待压缩基因序列的第一段作为二维矩阵的第n-1行；然后，将第一条待压缩基因序列的第二段作为二维矩阵的第n行，将第二条待压缩基因序列的第二段作为二维矩阵的第n+1行，以此类推，直到n-1个序列全部输入二维矩阵；至此，所有待压缩基因序列转换成一个宽为w，长为(n-1)*l/w的二维矩阵；

[0013] (7)对步骤(6)得到的二维矩阵进行编码：将二维矩阵中为1的元素划分成若干元素全为1的子矩阵；对每个子矩阵进行以下编码：对于只有一个元素的子矩阵，将该元素编码设置为-1；而对于具有2个及以上元素的子矩阵，将其左上角元素设置为1，右下角元素设置为2，其余元素设置为0；

[0014] (8)对经过步骤(7)处理后的待测基因序列进行存储：以二元组的形式按次序记录二维矩阵中值为1、2、-1的元素的行号和列号，将待压缩基因序列的信息转换成一个个二元组信息；对二元组中的元素实行熵编码，即使用变长编码的方式对于小于255的元素以一个字节长度存储，对于大于255小于65535的元素以两个字节存储，对于大于65535的元素以三个字节存储。

[0015] 进一步的，所述步骤(3)中采用基于k-mer算法的分段编码方法将参考序列进行单独压缩的具体步骤为：首先将参考序列分成长度为m的等长片断，再选取适当的k值，搜索每个片断中重复率最高的k-mer序列，并记录其重复的总次数及每一次重复在该片断中的位置，然后进行分段编码，以替代序列中重复出现的k-mer子序列。

[0016] 有益效果：与现有技术相比，本发明具有以下优势：

[0017] 本发明所提出的一种面向多条序列的基因序列数据压缩方法，将基因序列转换成二元组形式后，使一个对顺序有严格要求的基因序列变成与顺序无关的序列，有利于利用分布式存储和计算提升基因压缩和分析的效率。

附图说明

[0018] 图1为本发明所提出的面向多条序列的基因序列数据压缩方法的流程图；

[0019] 图2为参考序列选取流程图

[0020] 图3为非参考序列与参考序列对齐方案示意图；

[0021] 图4为基因序列矩阵化方案示意图

[0022] 图5为k-mer算法流程图。

具体实施方式

[0023] 下面结合附图对本发明作更进一步的说明。

[0024] 本发明提出面向多条序列的基因序列数据压缩方法，主要用于解决基因序列数据过大，存储和传输成本高等问题，首先从众多待压缩基因序列中选取参考序列，然后将待压缩基因与压缩基因进行运算，达到存储中去除冗余数据的目的。最后对参考序列等进行单独压缩。图1为本发明所提出的面向多条序列的基因序列数据压缩方法的流程图，本发明的流程包括以下步骤：

[0025] 步骤一、参考序列选取：参考序列选取过程如图2所示，面向多条待压缩基因序列，首先需要在多条待压缩序列中选取一条参考序列，参考序列的选取优劣是提升基因压缩比的重要条件。记待压缩基因序列共n条，将待压缩基因序列通过数字化映射为欧氏空间的高维数字向量，然后对每一条待压缩基因序列，计算其与其他n-1条待压缩序列之间的欧式距离的和，并将欧式距离的和的值最小的待压缩基因序列作为参考序列。

[0026] 步骤二、将待压缩序列与参考序列进行对齐：对齐过程如图3所示，对于待压缩序列相对于参考序列增加的部分，需要进行临时删减。将删减的信息以四元组的形式单独挂接在序列尾部，挂接四元组形式为<挂接类型Type(增加还是删除)，在序列中的位置Position，长度Length，内容Content>。对于待压缩序列相对于参考序列缺少的部分，需要进行临时补充，补充的内容为参考序列中的内容，并将补充的内容以三元组的形式挂接在序列尾部，挂接三元组形式为<挂接类型(增加还是删除)，在序列中的位置Position，长度Length>。

[0027] 步骤三、对参考序列进行单独压缩存储：采用基于k-mer算法的分段编码方法进行单独压缩。k-mer是DNA序列中由k个相邻碱基组成的短序列片段，当k取合适值时，DNA序列中k-mer频数分布包含了基因组的全部信息，从而构成序列的一个等价表示。首先将DNA序列分成长度为m的等长片断，再选取适当的k值，搜索每个片断中重复率最高的k-mer序列，并记录其重复的总次数及每一次重复在该片断中的位置等，然后进行分段编码，以替代序列中重复出现的k-mer子序列。本实施方式中将DNA序列分成长度为64的等长片断，再设置k值为3，即在每64个碱基子片断中搜索重复率最高的3-mer序列，并记录其重复的总次数及每一次重复在该片断中的位置等，然后以三元组的形式进行编码，三元组形式为<子序列编号No.，3-mer类型Type，所有3-mer在子序列中的距离增量向量d＝(d1，d2，d3，...，dn)>，以替代序列中重复出现的k-mer子序列，如图5所示。

[0028] 步骤四、对包含参考序列在内的所有基因序列进行编码。基因序列由A、G、C、T四种碱基组成，所以每个碱基可以用两个二进行制比特表示。这样，所以基因序列转换成二进制比特序列。

[0029] 步骤五、将待压缩基因序列与参考序列进行异或。经过异或后，待压缩基因序列与参考序列相同部分全部变成0，只有与参考序列不相同部分变成1。

[0030] 步骤六、如图4所示，将与参考序列异或后的待压缩基因序列进行矩阵化：记参考序列的二进制长度为l，选取适当的w，把每一条待压缩基因序列划分成w宽的等份，放入一个二维矩阵中；其中，第一条待压缩基因序列的第一段作为二维矩阵的第一行，第二条待压缩基因序列的第一段作为二维矩阵的第二行，以此类推，直至第n-1条待压缩基因序列的第一段作为二维矩阵的第n-1行；然后，将第一条待压缩基因序列的第二段作为二维矩阵的第n行，将第二条待压缩基因序列的第二段作为二维矩阵的第n+1行，以此类推，直到n-1个序列全部输入二维矩阵；至此，所有待压缩基因序列转换成一个宽为w，长为(n-1)*l/w的二维矩阵。

[0031] 步骤七、对步骤六得到的二维矩阵进行编码：将二维矩阵中为1的元素划分成若干元素全为1的子矩阵；对每个子矩阵进行以下编码：对于只有一个元素的子矩阵，将该元素编码设置为-1；而对于具有2个及以上元素的子矩阵，将其左上角元素设置为1，右下角元素设置为2，其余元素设置为0；

[0032] 步骤八、对经过步骤七处理后的待测基因序列进行存储：以二元组的形式按次序记录二维矩阵中值为1、2、-1的元素的行号和列号，将待压缩基因序列的信息转换成一个个二元组信息；对二元组中的元素实行熵编码，即使用变长编码的方式对于小于255的元素以一个字节长度存储，对于大于255小于65535的元素以两个字节存储，对于大于65535的元素以三个字节存储。

[0033] 以上所述仅是本发明的优选实施方式，应当指出：对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。