[發(fā)明專利]一種基于參考序列的基因壓縮方法

有效

• 申請?zhí)枺?/td>: 201910598102.0
• 申請日: 2019-07-04
• 公開（公告）號: CN110310709B
• 公開（公告）日: 2022-08-16
• 發(fā)明（設(shè)計(jì)）人: 季一木;陳帥;堯海昌;李奎;劉尚東;方厚之;劉強(qiáng)
• 申請（專利權(quán)）人: 南京郵電大學(xué)
• 主分類號: G16B50/50
• 分類號: G16B50/50
• 代理公司: 南京瑞弘專利商標(biāo)事務(wù)所(普通合伙) 32249
• 代理人: 彭雄

本發(fā)明公開了一種基于參考序列的基因壓縮方法，首先任意選取一個(gè)基因序列作為參考序列。其次，獲取參考序列的小寫字符和ACGT，并以二元組表示小寫字符。然后，讀取參考文件，獲得參考文件的頭部、換行信息、小寫字符、N字符、堿基信息和其他字符，并將換行長度、小寫字符、N字符和其他字符表示成二元組。接著，匹配參考序列和待壓縮序列的小寫字符二元組。最后匹配Hash值。解壓縮過種采用壓縮過程相反的步驟。采用本壓縮方法的壓縮比高，壓縮速度快，而且二元組編碼與基因次序無關(guān)，有利于分布式存儲(chǔ)和分析基因序列。

技術(shù)領(lǐng)域

本發(fā)明涉及一種基因序列壓縮的方案，主要用于解決基因序列數(shù)據(jù)過大，存儲(chǔ)和傳輸成本高等問題，屬于壓縮算法領(lǐng)域。

背景技術(shù)

基因是DNA上有遺傳效應(yīng)的片段，人類的生老病死等都與基因有關(guān)。基因數(shù)據(jù)研究可以獲得對生命運(yùn)行機(jī)制和疾病機(jī)理等的深入研究，在生物醫(yī)藥學(xué)和相關(guān)生物技術(shù)產(chǎn)業(yè)，如制藥、農(nóng)、林、牧、漁、環(huán)保等的發(fā)展發(fā)揮越來越重要的作用，對于推動(dòng)精準(zhǔn)醫(yī)療，助力解決三大民生問題之一的醫(yī)療問題，具有重要的作用。因此，基因數(shù)據(jù)因其重要的社會(huì)價(jià)值和科研價(jià)值受到國際社會(huì)的廣泛重視。自1990年正式啟動(dòng)的國際人類基因組計(jì)劃以來，隨著基因測序技術(shù)的不斷進(jìn)步，基因測序成本的不斷降低，測序速度不斷提高，眾多國家和組織紛紛啟動(dòng)基因工程計(jì)劃。2017年12月28日，我國啟動(dòng)“中國十萬人基因組計(jì)劃”，這是我國在人類基因組研究領(lǐng)域?qū)嵤┑氖讉€(gè)重大國家計(jì)劃，也是目前世界最大規(guī)模的人類基因組計(jì)劃。隨著各種測序項(xiàng)目的展開，產(chǎn)生的序列數(shù)據(jù)量呈指數(shù)規(guī)模增長，而且未來增長速度會(huì)更快。基因數(shù)據(jù)增長的速度大大超過了存儲(chǔ)和傳輸帶寬增長的速度，給存儲(chǔ)和傳輸帶來了很大的壓力。如何以更高的效率存儲(chǔ)基因數(shù)據(jù)，減輕存儲(chǔ)和傳輸壓力，在基因研究和應(yīng)用中著十分重要的作用。

DNA序列數(shù)據(jù)具有與其他數(shù)據(jù)截然不同的特性，DNA序列是僅由A、G、C、T四個(gè)符號構(gòu)成的超長序列，構(gòu)成種類簡單但是序列長度巨大。很大一部分DNA序列至今無法確定其用途，如果數(shù)據(jù)壓縮過程中出現(xiàn)丟失，可能造成不可估量的損失，所以DNA序列必須保證無損壓縮。另外，DNA序列中堿基對的排列并不是隨機(jī)的，具有特定的概率分布和規(guī)律性。而且，DNA序列具有高度的相似性。首先，不同物種間的DNA序列相似度很高，同一物種間的DNA序列相似性更為明顯。其次，同一個(gè)體內(nèi)的不同片段的DNA序列也存在著許多精確重復(fù)。利用DNA這些信息特點(diǎn)，工業(yè)界和學(xué)術(shù)界提出了眾多利用DNA序列特征的DNA序列壓縮方法。經(jīng)過對現(xiàn)在技術(shù)的文獻(xiàn)檢索發(fā)現(xiàn)，2000年T Matsumoto和K Sadakane在Genome Informatics上的“Biological sequence compression algorithms”提出了CTW+LZ方法，將上下文樹加權(quán)(Context Tree Weighting,CTW)方法和LZ壓縮方法相結(jié)合，使用多個(gè)編碼模型對DNA序列的不同片段進(jìn)行壓縮。2002年，X Chen和M Li在Bioinformatics上的“DNACompress:fastand effective DNA sequence compression”提出了DNACompress壓縮方法，使用了Pattern Hunter工具搜索DNA序列的重復(fù)與近似重復(fù)片段，提高了方法的整體速度。2005年，G Korodi和I Tabus在ACM Transactions on Information Systems上的“AnEffective Normalized Maximum Likelihood Algorithm for DNA SequenceCompression”提出了GeNML方法，對具有不同數(shù)據(jù)特點(diǎn)的DNA片段使用不同的編碼策略和概率模型進(jìn)行壓縮。2013年，Sebastian Wandelt and Uif Leser在IEEE/ACM Transactionson Computational Biology and Bioinformatics的“FRESCO:Referential Compressionof Highly Similar Sequences”提出了一種叫FRESCO的快速基因壓縮方法，它采用了一種用參考基因來表示被壓縮基因的方法。2015年，Xiaojing Xie,Shuigeng Zhou和JihongGuan在IEEE/ACM Transactions on Computational Biology and Bioinformatics的“CoGI：Towards Compressing Genomes as an Image”上提出了一種用圖模型來表示基因數(shù)據(jù)，從而可以利用圖壓縮技術(shù)來壓縮基因模型的方法。總結(jié)這些DNA序列壓縮方法可以分為兩大類：基于非參考序列的DNA序列壓縮方法和基于參考序列的DNA序列壓縮方法，這些方法都有效的提高了壓縮比和壓縮效率。但總體而言，DNA序列的壓縮技術(shù)仍處于起步階段，組成基因片段的生物信息特征及片段內(nèi)部的細(xì)節(jié)重復(fù)特性并沒有被充分發(fā)揮利用。基因序列之間的特征也還沒有被充分挖掘。