發(fā)布時(shí)間：2020-11-14 17:06

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10 趙巾金;張?chǎng)┚?陳曉麗;曹芳婷;車琳琳;;心電信號(hào)數(shù)據(jù)壓縮算法的研究[J];中國(guó)科技信息;2012年04期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2883722