dna序列的k-merindex問題-基于hash算法快速檢索(編輯修改稿)
2025-07-09 04:40 本頁面
【文章內(nèi)容簡(jiǎn)介】 直接 關(guān)鍵碼值 尋址 輸出 ，所以 索引 查詢速度非常快 。 針對(duì) 問題六： 按照重要性 首先考慮 索引查詢速度， 其次 動(dòng)態(tài) 內(nèi)存分配盡量減少索引對(duì)內(nèi)存的 消耗 ， 在 8G內(nèi)存限制下， 使 k 值支持 1~14， 最后 優(yōu)化添加 計(jì)數(shù)器記錄已經(jīng) 存在 地址的 kmer 個(gè)數(shù)，倘若達(dá)到所有 kmer 種類數(shù)，則停止建立索引， 索引 成功建立。 三、符號(hào)說明 符號(hào) 符號(hào)說明 H(x) 關(guān)鍵碼值 生成 函數(shù) ， 其中 x 代表一個(gè) kmer 代表 A， T， C， G 中的 任意一個(gè) 與 相對(duì)應(yīng) 的四進(jìn)制數(shù) k 一個(gè) kmer 的長(zhǎng)度 M 內(nèi)存 空間占用（單位： GB） 四 、算法設(shè)計(jì)思路及 性能 分析 （ 代碼見附錄一 ） (一 ) 哈希表設(shè)計(jì)： kmer 關(guān)鍵碼值 生成 函數(shù) H(x) 由于 DNA序列 由 4個(gè) 字母 排列 而成，所以每個(gè) kmer 都是一個(gè)四進(jìn)制數(shù)，H(x)函數(shù)根據(jù) 這個(gè) 特征將 四進(jìn)制 數(shù) 轉(zhuǎn)為十進(jìn)制 數(shù) 作為 哈希表 關(guān)鍵碼值 。 x= “ CTGTA” 如上圖 為每個(gè)字母代表的 四進(jìn)制數(shù)字 ， 例如 一個(gè) 5mer “ CTGTA” 可以 表示為四進(jìn)制數(shù) 21310， 其十進(jìn)制表示為 628， 628 即為 5mer “ CTGTA” 在哈希表中的 關(guān)鍵碼 值。 關(guān)鍵碼 值 計(jì)算 的 一般 公式為 : （ 1） 哈希表 結(jié)構(gòu) 將 kmer通過公式 （ 1） 轉(zhuǎn)換 為 十進(jìn)制的關(guān)鍵碼值 存入哈希表 中的關(guān)鍵碼值 一列，并將關(guān)鍵碼值與此 kmer 所在位置建立對(duì)應(yīng)關(guān)系， 從而 便于索引尋址 。這里 采用的方法是： 桶定址法。 桶：一片足夠大的存儲(chǔ)空間。桶定址：為表中的每個(gè)地址關(guān)聯(lián)一個(gè)桶。如果桶已經(jīng)滿了，可以使用開放定址法來處理。如圖。 沖突 處理方法 開放地址法有一個(gè)公式： Hi=(H(key)+di) MOD m i=1,2,...,k(k=m1） 其中， m 為哈希表的表長(zhǎng)。 di 是產(chǎn)生沖突的時(shí)候的增量序列。如果 di 值可能為 1,2,3,...m1，稱線性探測(cè)再散列。 如果 di取 1，則每次沖突之后，向后移動(dòng) 1個(gè)位置 .如果 di 取值可能為1,1,4,4,9,9,16,16,...k*k,k*k(k=m/2） 稱二次探測(cè)再散列。 (二 ) 建立 索引的 算法 、計(jì)算復(fù)雜度及空間復(fù)雜度分析 算法分析 hash 表初始化時(shí) ，根據(jù) 用戶輸入的 k 值， 計(jì)算出 存儲(chǔ)哈希表需要的空間，利用 內(nèi)存 動(dòng)態(tài)分配 函數(shù) 動(dòng)態(tài)分配內(nèi)存， kmer 所在行數(shù)為 100 0000 以內(nèi)所以我們采用 int 型（ 占用 4字節(jié) ）存儲(chǔ)，而其在行的 第幾個(gè) 位置
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1