隨著下一代測序技術(shù)(Next Generation Sequencing,NGS)的發(fā)展和逐步普及,基因測序變得越來越快速,費用也越來越親民�；蚪M序列數(shù)據(jù)正以爆炸性的速度擴增,因而產(chǎn)生了海量基因組序列數(shù)據(jù)。傳輸,存儲,處理和分析這些數(shù)據(jù)的時耗和費用日漸成為制約基因組學(xué)和生物醫(yī)學(xué)發(fā)展的瓶頸。雖然現(xiàn)有許多通用的數(shù)據(jù)壓縮算法和軟件,但由于不能考慮和處理基因組序列數(shù)據(jù)的固有特性,它們不能高效地壓縮基因組序列數(shù)據(jù)。因此研發(fā)有針對性的,快速有效的基因組序列數(shù)據(jù)壓縮技術(shù)已經(jīng)成為了一項重要而緊迫的課題。本文提出了一種高壓縮率的基于參考的無損基因組序列數(shù)據(jù)壓縮算法。利用相同物種間基因組的高度相似性,將待壓縮目標(biāo)基因組序列匹配到參考基因組序列中,以匹配結(jié)果(即兩序列相同子序列的位置及長度)和目標(biāo)序列的不匹配部分,代替目標(biāo)基因組序列。本文創(chuàng)新性地設(shè)計了匹配策略選擇機制,有效地結(jié)合了以有無匹配位置的限制為區(qū)分的兩種主流匹配策略,即基于分段的局部匹配和全局匹配。根據(jù)參考基因組和目標(biāo)基因組序列的相似程度而應(yīng)用不同的匹配策略,借助哈希方法搜索兩序列間相同的子序列,并評估子序列的匹配位置和匹配長度對匹配效率的影響,以確定相同子序列的匹配位置。有效地處理了基因組序列數(shù)據(jù)中的各類字符,以進一步提高匹配效率。最后借助高效的熵編碼壓縮器對保存匹配結(jié)果的中間文件完成壓縮。實驗結(jié)果表明,本文壓縮算法可在至多18分鐘內(nèi)對FASTA格式的約3GB大小的人類完整基因組序列數(shù)據(jù)完成壓縮,56組人類基因組序列測試數(shù)據(jù)壓縮后的大小為4.45MB至40.67MB。本文壓縮算法的平均壓縮率優(yōu)于現(xiàn)有同類型先進的基因組序列數(shù)據(jù)壓縮算法,具有更好的魯棒性,且時空復(fù)雜度與現(xiàn)有先進的算法處于同一數(shù)量級,具有較強的實際應(yīng)用價值。本文還設(shè)計了對應(yīng)的高效解壓縮算法,可由已壓縮文件和參考基因組序列數(shù)據(jù)快速,無損的復(fù)原目標(biāo)基因組數(shù)據(jù)。完整人類基因組數(shù)據(jù)解壓縮的耗時被控制在2分鐘以內(nèi)。
【學(xué)位單位】：云南大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2019
【中圖分類】：Q811.4
【部分圖文】：

后是序列數(shù)據(jù)行，以回車符結(jié)尾。序列信息描述行通過第一列中的大于符（“＞”）??與序列數(shù)據(jù)行進行區(qū)分，并建議所有序列數(shù)據(jù)行的長度小于８０個字符。ＦＡＳＴＡ數(shù)??據(jù)格式的一個示例序列數(shù)據(jù)如圖２－３所示，是某記錄編碼某蝴蛛猴的Ｇ－ｇａｍｍａ－??ｇｌｏｂｉｎ蛋白的ＤＮＡ序列的ＦＡＳＴＡ文件。鑒于ＦＡＳＴＡ數(shù)據(jù)格式的廣泛使用及其適??用性，本文將針對該格式的基因組序列數(shù)據(jù)設(shè)計專用的壓縮算法。??１３??

本文算法的壓縮部分分別按功能設(shè)計了六個模塊，即預(yù)處理模塊，??基于分段的局部匹配模塊，全局匹配模塊，匹配策略選擇模塊，后處理及熵編碼模??塊。本文算法的主要流程如圖３－１所示。??１７??

３．?５匹配策略選擇機制??本文設(shè)計了有效且復(fù)雜度較低的匹配策略選擇機制，以實現(xiàn)針對相似度不同??的目標(biāo)與參考基因組序列組合采用不同的匹配策略，其簡要示意如圖３－２所示。??輸入目標(biāo)序列片段??＾■和參考序列片段＜??局部匹配操作??否?＾￣—??Ｉ－是一？不匹配數(shù)＋丨？?１??后處理等操作?否?否??是???Ｉ???全局匹配策略??Ｖ??后處理等操作??圖３－２：匹配策略簡要流程示意框圖??如前文所言，當(dāng)目標(biāo)序列與參考序列顯著不同時，就應(yīng)釆用全局匹配策略??２２??
【相似文獻】

相關(guān)期刊論文 前10條

1 馮志全,范平,張少白,王玉茹,成謝鋒;一種無失真圖像數(shù)據(jù)壓縮算法[J];計算機應(yīng)用;2001年S1期

2 包冬梅;;數(shù)據(jù)壓縮算法研究[J];無線互聯(lián)科技;2019年21期

3 李錦明;張文棟;毛海央;李林;林娟;馬游春;;實時無損數(shù)據(jù)壓縮算法硬件實現(xiàn)的研究[J];哈爾濱工業(yè)大學(xué)學(xué)報;2006年02期

4 張楠;幾種處理ECG信號的數(shù)據(jù)壓縮算法的比較[J];醫(yī)療衛(wèi)生裝備;2003年09期

5 曾玲,饒志宏;幾種數(shù)據(jù)壓縮算法的比較[J];通信技術(shù);2002年09期

6 馮志全,成謝鋒,王玉茹;一種無失真多媒體數(shù)據(jù)壓縮算法[J];濟南大學(xué)學(xué)報(自然科學(xué)版);2001年03期

7 尹志喜;甄國涌;;曲線數(shù)據(jù)壓縮算法研究與應(yīng)用[J];計算機系統(tǒng)應(yīng)用;2010年03期

8 郭靜;;海量數(shù)據(jù)歸檔系統(tǒng)數(shù)據(jù)壓縮算法選擇方法研究[J];中國電子科學(xué)研究院學(xué)報;2019年07期

9 季姝;俞靜;;基于冗余數(shù)據(jù)壓縮算法的經(jīng)濟信用風(fēng)險研究[J];電子設(shè)計工程;2017年07期

10 趙巾金;張雯晶;陳曉麗;曹芳婷;車琳琳;;心電信號數(shù)據(jù)壓縮算法的研究[J];中國科技信息;2012年04期

相關(guān)博士學(xué)位論文 前2條

1 潘志剛;低比特率合成孔徑雷達數(shù)據(jù)壓縮算法研究[D];中國科學(xué)院研究生院（電子學(xué)研究所）;2006年

2 曾尚春;SAR數(shù)據(jù)壓縮算法研究[D];南京航空航天大學(xué);2007年

相關(guān)碩士學(xué)位論文 前10條

1 史偉;基于參考的基因組序列數(shù)據(jù)壓縮算法研究[D];云南大學(xué);2019年

2 常曉明;基于無線傳輸?shù)暮附颖O(jiān)測系統(tǒng)設(shè)計與實時數(shù)據(jù)壓縮算法研究[D];天津工業(yè)大學(xué);2019年

3 榮河江;基于自索引結(jié)構(gòu)的高通量基因組重測序數(shù)據(jù)壓縮算法[D];哈爾濱工業(yè)大學(xué);2018年

4 陳耀立;GPS數(shù)據(jù)壓縮算法的研究與應(yīng)用[D];湖南大學(xué);2015年

5 孫超;面向網(wǎng)絡(luò)傳輸數(shù)據(jù)壓縮算法的研究與實現(xiàn)[D];合肥工業(yè)大學(xué);2012年

6 徐慧;實時數(shù)據(jù)庫中數(shù)據(jù)壓縮算法的研究[D];浙江大學(xué);2006年

7 張輝;基于支持列存儲的數(shù)據(jù)壓縮算法研究[D];南京理工大學(xué);2010年

8 白文武;面向云存儲的數(shù)據(jù)壓縮算法研究[D];西安電子科技大學(xué);2017年

9 劉鎖;振動信號無線監(jiān)測的數(shù)據(jù)壓縮算法與能效分析[D];華北電力大學(xué)(北京);2016年

10 曹芳彤;聲波測井?dāng)?shù)據(jù)壓縮算法的嵌入式開發(fā)與實現(xiàn)[D];西安科技大學(xué);2015年

本文編號：2883722