隨著高通量測序技術的發(fā)展,測序需要的成本急速下降,得到的基因組數(shù)據(jù)呈爆炸式增長,因此有效地存儲和搜索這些基因組數(shù)據(jù)成為了急需解決的問題。壓縮技術可以減少數(shù)據(jù)的存儲空間,所以優(yōu)秀的壓縮索引算法成為了解決這一問題的關鍵技術。研究發(fā)現(xiàn)基因序列與普通文本數(shù)據(jù)的結構不同,序列中包含較多的冗余信息,而且同一物種或者按照生物分類法則劃分的較相近的物種間的序列相似度很高,通用的文本壓縮算法無法有效地壓縮及搜索基因組序列集。所以,需要研究針對高度相似基因組序列數(shù)據(jù)集的壓縮索引算法。本文提出一種新的基于參考序列的壓縮索引算法FMQ,能夠高效地存儲和搜索基因組序列集。主要思路是將序列集劃分為參考序列和非參考序列,然后計算非參考序列與參考序列之間的差異信息,再設計壓縮索引結構存儲這些差異信息,并提出了在壓縮索引結構上的搜索算法（包括子串提取和模式定位算法）。具體工作如下:壓縮索引構建。首先,隨機選取一條序列作為參考序列,順序比較參考序列與非參考序列,得到不匹配的子序列,利用最長公共子序列算法獲得參考序列與每個子序列之間的公共部分,根據(jù)公共部分逆推得到序列間的差異信息。然后,根據(jù)差異信息不同部分的特點,分別對差... 

【文章來源】：西安電子科技大學陜西省 211工程院校 教育部直屬院校

【文章頁數(shù)】：71 頁

【學位級別】：碩士

【部分圖文】：

L串的平衡小波樹表示

西安電子科技大學碩士學位論文三層結構的主要思想是首先將長度為 n 的比特串 B 劃分為長度 s = log2n / 2 的超塊，然后將每個超塊劃分為長度 b=logn/ 2 的塊。利用數(shù)組 Rs 存儲當前超塊起始位置之前 1 的個數(shù)，即 Rs[j] = rank(B, j s)，j [0, n / s]。Rb 存儲當前塊的起始位置與其所在超塊的起始位置之間 1 的個數(shù)，即 Rb[j] = rank(B, j b) rank(B, k s)，j [0n/s]，其中 k 為塊號為 j 的塊所處的超塊號。建立查找表 Rp，其中記錄的是長度為塊大小 b 的所有可能出現(xiàn)的比特串的 rank 值。經(jīng)典的三層結構如圖 2.5 所示。

以及在壓縮結構上的子串提取與模式定位算法進行詳細介紹，并在理論上分析算法的性能。3.1 算法框架本文的主要研究對象是高度相似的基因組序列數(shù)據(jù)集。研究的具體問題是：給定包含 m 條高度相似基因組序列的集合 G={S1, S2, …, Sm}，每條序列取自字符表 ={A,T,C,G,N}，序列 Si的長度用|Si|來表示，1≤i≤m，目標是建立有效的壓縮索引結構，獲得較好的壓縮效率并支持高效的子串提取及模式定位操作，其中子串提取操作是提取某個序列從特定位置開始的子串，即 extract 操作。模式定位操作是得到某個模式在整個基因組序列集中出現(xiàn)的位置，即 locate 操作。任意兩條基因序列之間是高度相似的，因此整個基因組序列集 G 中一定包含很多重復的冗余信息。如果能夠得到盡可能多的冗余信息，采用少量的信息標記這些冗余，那么存儲整個序列集的空間代價將會極大地降低。本文算法 FMQ 采用的算法框架如圖 3.1 所示：

【參考文獻】：
碩士論文
[1]基于FM-index的DNA序列數(shù)據(jù)壓縮算法[D]. 李新娛.西安電子科技大學 2017



本文編號：2951320