陳慧

摘? 要：該文通過將生物學(xué)特征和生物學(xué)含義引入DNA序列數(shù)據(jù)的壓縮處理中， 提出了基于生物信息學(xué)特征的基因組序列的Context建模熵編碼技術(shù)，擬結(jié)合基因組序列特點(diǎn)，研究針對基因組序列的Context建模熵編碼技術(shù)。在算法中DNA序列根據(jù)組成部分生物學(xué)含義的不同切分重組為4個集合：編碼序列CDS集合、內(nèi)含子序列集合、RNA序列集合以及剩余序列的集合。根據(jù)各集合中序列的具體生物學(xué)特征分別進(jìn)行預(yù)處理， 并通過熵編碼算法進(jìn)行壓縮。實(shí)驗(yàn)結(jié)果表明，該算法在基準(zhǔn)測試序列上的壓縮性能優(yōu)于原有的DNA序列壓縮方法，特別是對于生物信息學(xué)特征清晰的長序列，算法能夠在較短的時間內(nèi)獲得較高的壓縮率。

關(guān)鍵詞：基因組序列? Context建模? 熵編碼? 集合

中圖分類號：G64? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A文章編號：1672-3791（2021）03（c）-0025-03

Application of Entropy Coding Genome Sequence Based on Context Modeling

CHEN Hui

（Dianchi College of Yunnan University， Kunming， Yunnan Province， 650228? China）

Abstract： In this paper， by introducing biological characteristics and biological meaning into the compression processing of DNA sequence data， Context modeling entropy coding technology of genome sequence based on bioinformatics features was proposed. It is intended to combine the characteristics of genome sequence to study the context modeling entropy coding technology of genome sequence. In the algorithm， DNA sequences are reorganized into four sets according to the different slices of the biological meaning of the constituent parts： the CDS set of the coding sequence， the intron sequence set， the RNA sequence set and the remaining sequence set. According to the specific biological characteristics of the sequences in each set， the sequences were preprocessed and compressed by entropy coding algorithm. The experimental results show that the compression performance of the proposed algorithm is better than that of the original DNA sequence compression method， especially for long sequences with clear bioinformatics features， the algorithm can obtain a higher compression rate in a relatively short time.

Key Words： Genome sequence; Context modeling; Entropy coding; Congregation

基因組序列要保持盡可能多的遺傳特性，則注定其基因組序列中要維持最低的重復(fù)片段。重復(fù)序列片段過短導(dǎo)致在Context建模過程中，直接選取近鄰堿基來構(gòu)建條件概率分布未必能夠保證堿基間的相關(guān)性得以最大限度發(fā)揮。而文獻(xiàn)[1]中指出，基因組中堿基間存在長程相關(guān)性。這就意味著，與當(dāng)前堿基相關(guān)的那些堿基未必在其附近。因此，在對基因組序列進(jìn)行壓縮時，不能簡單地按照堿基在序列中的順序進(jìn)行建模和編碼。一種對基因組序列進(jìn)行重新排序，使得排序后相鄰堿基間的相關(guān)性得以增強(qiáng)，然后再對重排序后的序列進(jìn)行編碼以充分發(fā)揮熵編碼性能。雖然重新排序有可能造成接收端由于不知道編碼順序而無法解碼，但只要找到合適的方法，使得收發(fā)雙方能夠事先確定重新排序后的堿基順序，則可避免上述問題的出現(xiàn)。而對于重排序方法，對基因組序列進(jìn)行重新排序預(yù)處理，以充分利用堿基間的相關(guān)性從而提高壓縮效率。

1? 研究針對基因組序列的Context建模

針對基因組序列的Context建模不僅要使用傳統(tǒng)建模方法，還要考慮使用基因組序列的生物學(xué)特征幫助建模。換言之，那些已經(jīng)被生物學(xué)界確定的具有一定遺傳特性的片段也應(yīng)當(dāng)作為條件來構(gòu)建相應(yīng)條件概率分布，從而對Context模型進(jìn)行補(bǔ)充。另外，在前期研究中發(fā)現(xiàn)，當(dāng)給定充足的微生物基因組訓(xùn)練序列時，不論模型階數(shù)如何變化，得到的某些條件概率分布總是趨于均勻分布。此時，由于訓(xùn)練數(shù)據(jù)充足，表面上看“模型稀釋”問題不存在，但其實(shí)均勻化本身也應(yīng)當(dāng)被看作是一種特殊的“稀釋”問題。但對此問題，直接進(jìn)行合并操作并不能夠緩解“均勻化”，也就是說傳統(tǒng)的Context量化方法并不適合。一種可緩解“均勻化”的思想是對計(jì)數(shù)向量進(jìn)行分裂而不是合并。分裂其實(shí)是增加條件的過程，從理論上說可以降低熵值。

針對基因組序列Context建模中出現(xiàn)的“均勻化”問題，擬采用Context模型分裂的方法進(jìn)行處理。Context模型分裂其實(shí)等價于增加條件。然而，要從低階模型進(jìn)行分裂得到高階模型是不可行的。一種想法是在給定訓(xùn)練數(shù)據(jù)的前提下，先建立一個足夠大階數(shù)的模型，然后自底向上逐步合并，從而找到一個描述長度最短的編碼模型。在合并過程中，模型的階數(shù)實(shí)際上是在減少的，但如果事先給定的階數(shù)足夠大，則相對目前的建模方法，可以近似看作是一種分裂操作。在“分裂”過程中，一旦出現(xiàn)“均勻化”則合并停止，甚至回朔到上一級模型，從而可以避免整個Context模型的“均勻化”問題。

2? 基因組序列的混合壓縮算法

一方面，基于字典的壓縮算法（基于Lz77的基因組壓縮算法）對大量包含重復(fù)序列的物種的基因組序列具有較好的壓縮效果，而單純地使用字典類壓縮算法對基因組序列進(jìn)行壓縮效果并不明顯。但這并不意味著基于字典的壓縮方法不能應(yīng)用于基因組序列壓縮。另一方面，Context建模熵編碼技術(shù)對于非重復(fù)序列以及那些較少包含重復(fù)序列的基因組進(jìn)行壓縮的效果較好。因此，一種直觀的想法是將兩大類壓縮算法進(jìn)行綜合。對于微生物基因組而言，應(yīng)當(dāng)是以Context建模熵編碼為主，而使用基于字典的壓縮算法對重復(fù)序列進(jìn)行壓縮，從而提高壓縮效果。結(jié)合字典壓縮算法和Context建模熵編碼的微生物基因組序列壓縮算法進(jìn)行研究。

設(shè)Lm為計(jì)數(shù)向量Cm對應(yīng)的描述長度，Lk為計(jì)數(shù)向量Ck對應(yīng)的描述長度，Lmk為上述兩個計(jì)數(shù)集合并后的計(jì)數(shù)集Cmk={n1（mk），…，nI（mk）}={n1（m）+n1（k），…，nI（m）+nI（k）}對應(yīng)的描述長度。若nm，nk分別為Cm和Ck的總計(jì)數(shù)值，則Cmk的總計(jì)數(shù)值為nmk=nm+ nk。由此可以得到描述長度增量?Lmk的近似表達(dá)式：

（1）

從式（1）中可知，描述長度增量實(shí)際上等價于兩個相對熵的平均，且滿足對稱性。然而，描述長度增量并不滿足三角不等式。這是因?yàn)槊枋鲩L度增量選取了一個共有的參考點(diǎn)（參考計(jì)數(shù)向量）來實(shí)現(xiàn)相似性的表達(dá)，即合并后的計(jì)數(shù)向量Cmk（式中計(jì)算相對熵的Cmk）由此計(jì)數(shù)向量估計(jì)得到）。這個參考點(diǎn)跟兩個計(jì)數(shù)向量Cm和Ck是相關(guān)的，是動態(tài)的。而在物理學(xué)中，一個距離測度（相似測度）是一個相對量，而且參考點(diǎn)往往是靜態(tài)的，例如空間坐標(biāo)系中的原點(diǎn)（全零坐標(biāo)點(diǎn)）。因此，在研究計(jì)數(shù)向量相似測度時同樣需要考慮使用一個靜態(tài)參考點(diǎn)。

3? 仿真實(shí)驗(yàn)

實(shí)驗(yàn)中使用美國GenBank數(shù)據(jù)庫的DNA序列文件作為原始數(shù)據(jù)[2-3]，其中包含了對序列的詳細(xì)注釋。在熵編碼算法中， 可直接讀取這些注釋， 根據(jù)其生物學(xué)信息對序列進(jìn)行壓縮。在實(shí)驗(yàn)中， 將熵編碼算法與典型DNA序列壓縮方法：BioCompress、CTW+LZ和Lz77分別作用于5個基準(zhǔn)測試序列[4-6]。使用壓縮后序列中表示每堿基符號所需平均比特數(shù)以及熵編碼算法的壓縮時間作為實(shí)驗(yàn)結(jié)果?；鶞?zhǔn)測試序列包含了不同物種不同功能的DNA數(shù)據(jù)片斷， 能夠有效評估壓縮算法對含有不同數(shù)據(jù)特性的DNA序列的壓縮能力，算法壓縮率見表1。

由熵編碼算法與原有DNA序列壓縮算法的結(jié)果對比可以發(fā)現(xiàn)， 該算法在大多數(shù)基準(zhǔn)測試序列上的壓縮率要好于原有方法。特別當(dāng)序列包含生物信息學(xué)特征清晰時， 算法壓縮效果的提升更為明顯。對于含義劃分不清， 或是未包含注釋信息的DNA序列數(shù)據(jù)， 依賴于生物信息學(xué)特征的熵編碼算法效果并不十分理想。另外， 當(dāng)DNA序列長度較大時算法性能提升更為明顯，這是由于數(shù)據(jù)較長時， 其包含的重復(fù)片斷也較多， 能夠?qū)ふ业礁嗟碾[含模式， 從而可有效地進(jìn)行壓縮編碼。由結(jié)果看出，對DNA序列的生物信息學(xué)特征的序列數(shù)據(jù)進(jìn)行了預(yù)處理后，產(chǎn)生的二進(jìn)制數(shù)據(jù)流比原始序列數(shù)據(jù)更具有規(guī)律性，從而能夠更為有效地進(jìn)行壓縮。

4? 結(jié)語

該文介紹了DNA序列數(shù)據(jù)的常見生物信息學(xué)特征，通過將這些特征引入DNA序列的預(yù)處理， 提出了熵編碼基因壓縮算法。在算法中，含有不同生物學(xué)含義的片斷被切分重組為4個集合， 通過優(yōu)化序列附加信息的表示方式，算法進(jìn)一步提升了壓縮率。熵編碼算法能夠有效壓縮DNA序列數(shù)據(jù)，與原有僅考慮DNA數(shù)據(jù)特點(diǎn)的算法相比， 使用了生物信息學(xué)特征的熵編碼算法壓縮性能有所提升，特別是在生物信息學(xué)特征清晰的長序列上， 其壓縮結(jié)果優(yōu)勢更為明顯。

參考文獻(xiàn)

[1] 王燦燦.具有固定長度碼字的Context自適應(yīng)二進(jìn)制算術(shù)碼[D].云南大學(xué)，2019.

[2] 羅迪.基于最短碼長的Context加權(quán)編碼[D].云南大學(xué)，2015.

[3] 陳建華，王勇，張宏.基于描述長度的Context建模算法[J].電子與信息學(xué)報，2016，38（3）：661-667.

[4] 羅迪，陳旻，王晴晴.基于最短碼長的Context加權(quán)編碼[J].計(jì)算機(jī)光盤軟件與應(yīng)用，2014，17（9）：9-14.

[5] 陳旻，陳建華.優(yōu)化Context建模及其在微生物基因組序列和圖像壓縮中的應(yīng)用[D].云南大學(xué)，2018.

[6] 孔令超，陳建華.基于Context樹建模的基因組序列無損壓縮研究[C]//2020中國信息通信大會論文集.中國通信學(xué)會：人民郵電出版社電信科學(xué)編輯部，2020：5.