[發明專利]基于多參考序列的基因序列分級壓縮方法

有效

• 申請號: 201310433248.2
• 申請日: 2013-09-22
• 公開（公告）號: CN103546160A
• 公開（公告）日: 2014-01-29
• 發明（設計）人: 熊紅凱;李平好
• 申請（專利權）人: 上海交通大學
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 上海漢聲知識產權代理有限公司 31236
• 代理人: 郭國中

1.一種基于多參考序列的基因序列分級壓縮方法，其特征是，首先將BAM格式文件轉化成SAM格式的文件，SAM格式的基因序列由11個強制域和多個可選域構成，將可選域作為第12個域，原文件按域提取成12個獨立文件，然后對12個文件進行并行壓縮：

（1）對‘Sequence’域采用基于多個參考序列逐步減半序列長度的分級壓縮方法；

（2）對于‘Quality?Value’域采用k均值聚類結合上下文建模PPMVC壓縮的方法；

（3）對于剩下的十個域采用基于域內特征和域間相關性的壓縮方法。

2.根據權利要求1所述的基于多參考序列的基因序列分級壓縮方法，其特征是，所述對‘Sequence’域采用基于多個參考序列逐步減半序列長度的分級壓縮方法，具體為：利用快速比對工具SOAP3將SAM/BAM文件的‘Sequence’域中的短序列分線程地與參考序列作比對，對于準確匹配序列高效壓縮，對于非準確匹配和未匹配的短序列，將其序列長度減半，即一個序列分成長度相同的兩個序列，并改變參考序列，再進行第二次比對，得到比對結果，如此重復三至四次結束，剩余的非準確匹配和未匹配的短序列進行PPMVC編碼。

3.根據權利要求2所述的基于多參考序列的基因序列分級壓縮方法，其特征是，所述的對于準確匹配序列高效壓縮，具體為：對于準確比對的子序列Read，使用<Read編號，參考序列上重復發生的染色體號，參考序列上重復發生的偏移位置，重復類型>這四個量來替代目標序列上重復的子序列，分別使用差分編碼+哈弗曼編碼、游程編碼、差分編碼+哈弗曼編碼和游程編碼來壓縮這四個分量。

4.根據權利要求1-3任一項所述的基于多參考序列的基因序列分級壓縮方法，其特征是，所述的對于‘Quality?Value’域采用k均值聚類結合上下文建模PPMVC壓縮的方法，具體為：采用k均值聚類法將n個Q_ASCII值聚成k類，使得聚類后每類內所有Quality?value的值與聚類前的值差值平方最小，然后采用基于上下文建模和統計的自適應文本壓縮方法PPMVC壓縮聚類后的‘Quality?Value’文件。

5.根據權利要求1-3任一項所述的基于多參考序列的基因序列分級壓縮方法，其特征是，所述的對于剩下的十個域采用基于域內特征和域間相關性的壓縮方法，具體為：

對于‘QNAME’域，用‘0’表示之前未出現過的QNAME，用逐漸遞增的數字編號與當前位置只差表示之前已經出現的QNAME，然后采用哈弗曼編碼壓縮這些非均勻分布的小型數值；

對于‘FLAG’域，用一個字節表示1～255之間的數值，用三個字節即0,x/256和x%256表示其它數值，然后采用哈弗曼編碼壓縮變換后的數值；

對于‘RNAME’域，用相同的數字標記整個SAM文件中的相同的參考序列名字，記錄下來所有參考序列，然后用游程編碼進行壓縮；

對于‘POS’域，采用差分編碼+哈弗曼編碼；

對于‘MAPQ’域，采用游程編碼；

對于‘CIGAR’域，采用LZW字典壓縮方法；

對于‘MRNM’域，采用游程編碼；

對于‘MPOS’域，結合‘MRNM’域的字符串，采用差分編碼+哈弗曼編碼；

對于‘TLEN’域，‘TLEN’域的值與‘MPOS’域減去‘POS’域的值的差即TLEN-(MPOS-POS))的絕對值服從于一個有限的字符集，對于該域的壓縮，結合‘POS’,‘MPOS’and‘MRNM’三個域的信息采用Huffman編碼壓縮變換后的值；

對于‘OPTIONAL’域，使用bzip2壓縮工具。