[發明專利]基因組測序數據的Leon-RC壓縮方法

有效

• 申請號: 201810834127.1
• 申請日: 2018-07-26
• 公開（公告）號: CN109256178B
• 公開（公告）日: 2022-03-29
• 發明（設計）人: 雷志強;李偉忠
• 申請（專利權）人: 中山大學
• 主分類號: G16B20/30
• 分類號: G16B20/30
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

本發明涉及一種基因組測序數據的Leon?RC壓縮方法，其主要對LEON算法構造錨點字典的步驟進行改進，包括以下步驟：（1）將短讀劃分為多個Kmer；（2）選擇一個Kmer，計算其直接重復、鏡像重復、反轉重復、互補回文的Kmer值，比較這四個值，獲得最小的Kmer值；（3）將最小的Kmer值放入布隆過濾器中進行匹配查找，布隆過濾器中存放有Solid Kmer，判斷Solid Kmer中是否存在最小的Kmer值；若存在，則向錨點字典中添加該最小的Kmer值，并結束查找；若不存在，則獲取下一個Kmer，重復步驟（2）、（3）；（4）若所有Kmer的最小的Kmer值都不存在于Solid Kmer中，則說明該短讀不存在錨點；（5）通過步驟（1）~（4）構造錨點字典。

技術領域

本發明涉及生物信息領域，更具體地，涉及一種基因組測序數據的Leon-RC壓縮方法。

背景技術

現有的二代測序數據壓縮方法主要有兩種：一種是基于參考基因組的壓縮算法，如QUIP、CRAM、PATHENC和FASTQZ等，壓縮后的文件存儲的是短讀與參考基因組之間的映射信息。同源物種基因組之間具有高度相似性，以人類為例，任何兩個人的基因組相同部分的內容高達99%，因此，在獲得參考基因組的情況下，如果能夠存儲這1%的額外信息，就能夠存儲目標基因組。

基于參考基因組的二代測序數據壓縮流程如下：

（1）選取合適的參考基因組，同源物種序列由于具有高度相似性作為參考基因組具有優勢；

（2）將原始短讀映射（mapping）到參考基因組，并記錄原始數據的匹配位置、差異位置、差異內容和差異類型；

（3）對步驟（2）記錄的差異結果進行高效編碼壓縮。

另一種是無參考基因組的壓縮算法，如：SCALCE、DSRC、ORCOM、BEETL、MINCE等，它利用了短讀之間的相似性對數據進行壓縮，通常而言，基于拼接的無參考基因組的壓縮方法分為以下兩個步驟：

（1）將一部分短讀使用拼接算法拼成一個臨時參考基因組；

（2）使用基于參考基因組的壓縮方法，將原始短讀映射到臨時參考基因組，并將映射結果進行編碼。

Leon是目前比較高效的無參考基因組壓縮算法，它能夠同時兼顧壓縮率和壓縮速率，圖1為Leon算法壓縮的過程的總體流程。其主要分為以下幾個步驟：

（1）讀取Fasta文件或Fastq文件中的短讀，并統計短讀中的Kmer在整個文件中出現的次數，設置一個閾值，出現次數大于該閾值的Kmer為solid Kmer；

（2）用所得的solid Kmer構建一個錨點字典并拼接成一個德布魯因圖，并存儲在布隆過濾器中，以便后續快速匹配；

（3）將原始文件中的每一條短讀映射至德布魯因圖，映射的結果存儲在映射表中；

（4）用算術編碼對德布魯因圖、錨點字典以及映射表進行壓縮，壓縮后合并的結果即為壓縮后的文件。

不同于傳統的非參考基因組壓縮算法，Leon定義了自己的一套映射規則。在它的映射表中包含了以下三項：錨點下標、左路徑（left path）、右路徑（right path）。錨點下標指的是初始Kmer的位置，左路徑包含了從錨點開始短讀左邊的Kmer與參考基因組的映射關系，右路徑則包含了從錨點開始短讀右邊的Kmer與參考基因組的映射關系。