基于Context建模熵編碼的基因組序列應用

陳慧

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

關鍵詞：基因組序列? Context建模? 熵編碼? 集合

中圖分類號：G64? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：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

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

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

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

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

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

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

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

（1）

從式（1）中可知，描述長度增量實際上等價于兩個相對熵的平均，且滿足對稱性。然而，描述長度增量并不滿足三角不等式。這是因為描述長度增量選取了一個共有的參考點（參考計數向量）來實現相似性的表達，即合并后的計數向量Cmk（式中計算相對熵的Cmk）由此計數向量估計得到）。這個參考點跟兩個計數向量Cm和Ck是相關的，是動態的。而在物理學中，一個距離測度（相似測度）是一個相對量，而且參考點往往是靜態的，例如空間坐標系中的原點（全零坐標點）。因此，在研究計數向量相似測度時同樣需要考慮使用一個靜態參考點。

3? 仿真實驗

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

由熵編碼算法與原有DNA序列壓縮算法的結果對比可以發現， 該算法在大多數基準測試序列上的壓縮率要好于原有方法。特別當序列包含生物信息學特征清晰時， 算法壓縮效果的提升更為明顯。對于含義劃分不清， 或是未包含注釋信息的DNA序列數據， 依賴于生物信息學特征的熵編碼算法效果并不十分理想。另外， 當DNA序列長度較大時算法性能提升更為明顯，這是由于數據較長時， 其包含的重復片斷也較多， 能夠尋找到更多的隱含模式， 從而可有效地進行壓縮編碼。由結果看出，對DNA序列的生物信息學特征的序列數據進行了預處理后，產生的二進制數據流比原始序列數據更具有規律性，從而能夠更為有效地進行壓縮。

4? 結語

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

參考文獻

[1] 王燦燦.具有固定長度碼字的Context自適應二進制算術碼[D].云南大學，2019.

[2] 羅迪.基于最短碼長的Context加權編碼[D].云南大學，2015.

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

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

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

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