[發(fā)明專利]一種海量DNA數(shù)據(jù)的傳輸方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201710188308.7
• 申請日: 2017-03-27
• 公開（公告）號: CN107169315B
• 公開（公告）日: 2020-08-04
• 發(fā)明（設(shè)計）人: 武文博;徐文濤
• 申請（專利權(quán)）人: 廣東順德中山大學(xué)卡內(nèi)基梅隆大學(xué)國際聯(lián)合研究院;中山大學(xué)
• 主分類號: G16B40/00
• 分類號: G16B40/00
• 代理公司: 廣州粵高專利商標(biāo)代理有限公司 44102
• 代理人: 林麗明

本發(fā)明提供的方法借助后綴數(shù)組求取DNA序列的最長重復(fù)子串，然后將最長重復(fù)子串存入數(shù)組中，并用數(shù)組下標(biāo)替換DNA序列中的最長重復(fù)子串，通過不斷的替換最長重復(fù)子串而達到壓縮傳輸數(shù)據(jù)量的目的。

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

本發(fā)明涉及生物信息學(xué)數(shù)據(jù)壓縮傳輸領(lǐng)域，更具體地，涉及一種海量DNA數(shù)據(jù)的傳輸方法及系統(tǒng)。

背景技術(shù)

目前實施的千人基因組計劃、國際單體型圖計劃和孟德爾遺傳疾病計劃等項目，利用下一代測序技術(shù)產(chǎn)生了海量的DNA測序數(shù)據(jù)，使得生物信息學(xué)數(shù)據(jù)呈現(xiàn)爆炸性增長。這些數(shù)據(jù)含有人類目前尚未了解的生物學(xué)知識，通過對這些數(shù)據(jù)的分析與處理，揭示其生物學(xué)內(nèi)涵，提取出對人類有用的信息，可以給生物學(xué)和醫(yī)學(xué)領(lǐng)域的相關(guān)研究帶來更大的輔助。但是，在促進生物學(xué)和醫(yī)學(xué)發(fā)展的同時，不同研究所之間傳遞數(shù)據(jù)的成本也高的驚人。如何壓縮傳輸量，較少傳輸成本成為了當(dāng)下急需解決的問題。

生物遺傳物質(zhì)的自我復(fù)制操作致使在同一個體的DNA序列中存在著大量完全重復(fù)的片段，另外還存在特殊的鏡像重復(fù)、反轉(zhuǎn)重復(fù)、互補回文結(jié)構(gòu)等重復(fù)片段。人類的不同個體基因的相似程度達99％，而和近親物種間基因序列的近似程度也可高達98％，植物DNA序列中重復(fù)序列含量可達80％以上。因此，DNA序列不僅數(shù)據(jù)量大且含有很多的冗余信息，這些數(shù)據(jù)冗余是DNA壓縮傳輸?shù)幕A(chǔ)。后綴數(shù)組是一種為文本索引設(shè)計的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)由記錄了字符串的各個后綴的字典序索引的數(shù)組構(gòu)成。利用后綴數(shù)組可以快速查找字符串中的最長重復(fù)子串。本發(fā)明利用后綴數(shù)組的這種用途，通過對生物基因序列查找最長重復(fù)子串，將查到的最長重復(fù)子串生成字典索引，刪減重復(fù)子串再查找最長重復(fù)子串，不斷循環(huán)該過程。從而實現(xiàn)了對DNA序列的編碼壓縮過程。

發(fā)明內(nèi)容

本發(fā)明為解決以上現(xiàn)有技術(shù)在傳輸DNA數(shù)據(jù)時傳輸數(shù)據(jù)量過大導(dǎo)致傳輸成本高昂的缺陷，提供了一種海量DNA數(shù)據(jù)的傳輸方法，該方法通過對DNA數(shù)據(jù)進行壓縮從而達到降低傳輸數(shù)據(jù)量的目的。

為實現(xiàn)以上發(fā)明目的，采用的技術(shù)方案是：

一種海量DNA數(shù)據(jù)的傳輸方法，利用發(fā)送客戶端、去重服務(wù)器和接收客戶端進行數(shù)據(jù)的傳輸，傳輸方法具體包括以下步驟：

S1.在發(fā)送客戶端，讀入第一條DNA序列D1；

S2.求取DNA序列D1的后綴數(shù)組SA，使用SA[m]記錄第m位后綴對應(yīng)的首字母位置，即Suffix[SA[m]]在所有后綴中是第m小的后綴；

S3.掃描后綴數(shù)組SA，通過比較相鄰后綴來找出最長的重復(fù)字符串Str[k]；

S4.在去重服務(wù)器上構(gòu)建數(shù)組a，將Str[k]存入數(shù)組a的第t個存儲單元a[t]中，t表示存儲單元的下標(biāo)，其初始值為1；

S5.使用t替換掉DNA序列D1中出現(xiàn)的所有重復(fù)字符串Str[k]，DNA序列D1經(jīng)過替換后形成新的序列D[1]；

S6.令t＝t+1，然后對D[1]重復(fù)執(zhí)行步驟S2～S5直至D[1]中剩余的堿基小于e個或最長重復(fù)子串小于f個，此時在D[1]中剩余的堿基段的開頭和結(jié)尾分別插入分隔符；

S7.對其余的DNA序列依次執(zhí)行步驟S8～S9的處理：

S8.讀入一條DNA序列Di，對其執(zhí)行步驟S2～S3的操作，求取到該DNA序列最長的重復(fù)字符串Str[h]，然后掃描數(shù)組a，判斷數(shù)組a中是否存儲有與Str[h]匹配的匹配項，若是則使用匹配項所在的存儲單元的下標(biāo)g替換DNA序列中出現(xiàn)的所有重復(fù)字符串Str[h]，DNA序列Di經(jīng)過替換后形成新的序列D[i]；否則令t＝t+1，然后將重復(fù)字符串Str[h]存入數(shù)組a的第t個存儲單元a[t]中；并使用t替換掉DNA序列Di中出現(xiàn)的所有重復(fù)字符串Str[h]，DNA序列Di經(jīng)過替換后形成新的序列D[i]；