蛋白質(zhì)序列二級結(jié)構(gòu)的搜索.ppt

1、蛋白質(zhì)序列二級結(jié)構(gòu)的搜索,Abstract,生命科學(xué)家使用的生物數(shù)據(jù)集的查詢工具效率低下 在基于二級結(jié)構(gòu)的大型數(shù)據(jù)集上搜索的問題 定義了直觀的二級結(jié)構(gòu)的查詢語言 評估查詢的算法 在Periscope、ORDBMS上實(shí)現(xiàn)算法 框架：優(yōu)化查詢、評估各種查詢估計(jì)計(jì)劃的開銷 高效、交互式的二級結(jié)構(gòu)查詢（大型蛋白質(zhì)數(shù)據(jù)集）,1.Introduction,人類基因組工程： 從蛋白質(zhì)和DNA序列中得出有意義的生物信息、知識（bioinformatics）。 確定基因的位置和功能，觀察蛋白質(zhì)之間的反應(yīng)，蛋白質(zhì)保持時(shí)蛋白質(zhì)的功能結(jié)構(gòu)。 提出問題： 與大型生物數(shù)據(jù)集的分析密切相關(guān) 存儲和查詢大型基因、蛋白質(zhì)數(shù)據(jù)庫

2、,1.1生物背景知識,蛋白質(zhì)的結(jié)構(gòu)組織：四層 主結(jié)構(gòu)：氨基酸的線性序列，蛋白質(zhì)識別 二級結(jié)構(gòu)：氨基酸的線性序列折疊成三維結(jié)構(gòu)：-螺旋（helix）， -片（sheet），翻轉(zhuǎn)（loop） 三維結(jié)構(gòu)決定蛋白質(zhì)的功能 模式和排列：變革性的關(guān)系 二級結(jié)構(gòu)折疊的類型、長度、開始位置：功能,1.2科學(xué)動力,發(fā)現(xiàn)新的蛋白質(zhì)、新的功能：確定蛋白質(zhì)的功能和類型 已有方法 搜索已知的蛋白質(zhì)數(shù)據(jù)庫，和未知的蛋白質(zhì)相匹配 分析相似蛋白質(zhì)的功能和分類，得出共同點(diǎn) 簡單基礎(chǔ)：定義了蛋白質(zhì)相似性 蛋白質(zhì)結(jié)構(gòu)和搜索目標(biāo)的不同，相似性的定義不同：匹配主結(jié)構(gòu)；匹配二級結(jié)構(gòu)（預(yù)測生物分子反應(yīng)）； 同樣的級別上也有不同：一部分；整

3、個(gè)序列 Flexible；efficient BLAST 服務(wù)器負(fù)載重；查詢估計(jì)算法的效率 交互式的結(jié)果：驗(yàn)證、否定一些假設(shè) 高效的查詢估計(jì)技術(shù),1.3內(nèi)容,定義了簡單、直觀的查詢語言：基于分區(qū)的二級結(jié)構(gòu)查詢 識別不同的算法，有效地估計(jì)查詢。 由于查詢和分區(qū)選擇，算法選擇對查詢的執(zhí)行有突出的影響 查詢優(yōu)化框架： 基于查詢和數(shù)據(jù)特征選擇最優(yōu)查詢計(jì)劃 直方圖：精確、空間小 在Periscope、ORDBMS上實(shí)現(xiàn)： 現(xiàn)實(shí)數(shù)據(jù)集、檢驗(yàn)算法 高效,2.蛋白質(zhì)格式（format),依賴于預(yù)測工具 大部分已知蛋白質(zhì)的二級結(jié)構(gòu)都是預(yù)測度量 準(zhǔn)確率：60%70% Predator：單氨基酸序列的殘余氫的識別

4、65%；本機(jī)運(yùn)行 蛋白質(zhì)名，氨基酸長度，主結(jié)構(gòu)，預(yù)測的二級結(jié)構(gòu),3.查詢語言和例子,3類原子查詢 3類二級結(jié)構(gòu)（h、e、l）；成組出現(xiàn)；按類型和長度表示二級結(jié)構(gòu)序列 查詢：分區(qū)謂詞序列,4.查詢估計(jì)技術(shù),Complex Scan of Protein Table（CSP） 普通分區(qū)技術(shù) Simple Scan of Segment Table(SSS) 掃描整個(gè)分區(qū)，利用INLJ得到蛋白質(zhì)，F(xiàn)SM Index Scan of Segment Table（ISS） 掃描索引，INLJ Multiple Index Scans of Segment Table(MISS n) ISS的概化，掃描B

5、樹索引N次，2n謂詞數(shù)，n-way-sort-merge-join,INLJ,4.1Complex Scan of Protein Table（CSP）,掃描蛋白質(zhì)表，找到蛋白質(zhì)，逐個(gè)對比蛋白質(zhì)的二級結(jié)構(gòu)，返回信息 non-deterministic finite state machine(FSM) 二級結(jié)構(gòu)每次輸入FSM一個(gè)字符，直到輸入一個(gè)最終（匹配）狀態(tài)，或確定不匹配 每個(gè)query對應(yīng)一個(gè)FSM 一個(gè)蛋白質(zhì)可能匹配多次：在蛋白質(zhì)的每個(gè)位置都運(yùn)行FSM匹配測試,4.2普通分區(qū)技術(shù),基于分割結(jié)構(gòu) 把蛋白質(zhì)的二級結(jié)構(gòu)分割為相同類型的部分，分別存入分區(qū)表，多屬性：類型、長度、原始蛋白質(zhì)id、

6、分區(qū)的起始位置 Multi-attribute B+樹索引，基于類型和長度 Clustered B+樹索引 IndexNested Loops Join（INLJ），B+樹：連接蛋白質(zhì)表和分區(qū)表 id進(jìn)行排序 Non-gap的QUERY，一次掃描分區(qū)表、索引就可以得到結(jié)果 （略）,5.1 Query 優(yōu)化和估計(jì),決定使用哪個(gè)plan來估計(jì)query 為4個(gè)plan的CPU，I/O開銷建模(cost function) 兩個(gè)直方圖： 基本直方圖：決定query謂詞的選擇 復(fù)雜直方圖：估計(jì)結(jié)果蛋白質(zhì)的選擇 輸入:每個(gè)query謂詞選擇、結(jié)果選擇的估計(jì) 基本直方圖： k*3矩陣（e h l），k是直

7、方圖桶的數(shù)量 72代表的數(shù)量 最后一個(gè)桶：長度=k的所有分區(qū) k=100:足夠小;足夠大 248,375蛋白質(zhì)、10,288,769分區(qū)，13建立直方圖，query 優(yōu)化器1ms/謂詞，99%的分區(qū)占1.2KB空間,5.2 復(fù)雜直方圖,整個(gè)query結(jié)果的選擇，而不是給定的query謂詞： 尋找同一個(gè)字符串里多屬性以某個(gè)次序出現(xiàn)的概率。 單個(gè)屬性、多個(gè)無序?qū)傩?4維矩陣 Protein id Start position 長度 類型 3472代表第3個(gè)bucket的蛋白質(zhì)的第4個(gè)bucket 的開始位置,5.2.2結(jié)果基數(shù)估計(jì),假設(shè):segment在 protein id和 start pos

8、ition上均勻分布 簡單起見,對應(yīng)于同一個(gè)protein id 結(jié)果基數(shù)=每種情況匹配數(shù)的估計(jì) 結(jié)果選擇=結(jié)果基數(shù)/總的蛋白質(zhì)數(shù) Case 1-3: 結(jié)果選擇=第一個(gè)桶匹配數(shù)/桶內(nèi)蛋白質(zhì)數(shù)*第二個(gè)桶的匹配數(shù)/桶內(nèi)蛋白質(zhì)數(shù) Case 4-6: Np1=1/50*(number of p1) Np2 =40/50*(number of p2) 設(shè)每個(gè)桶有100個(gè)protein id 結(jié)果選擇=np1*np2/100,5.2.3直方圖分析,復(fù)雜直方圖的精確度 與蛋白質(zhì)的實(shí)際數(shù)量相比較，80% 計(jì)算時(shí)間 謂詞的數(shù)目和桶的開始位置 謂詞增加，時(shí)間大幅度上升 謂詞增加，準(zhǔn)確度并沒有明顯增加，只需要2、3

9、個(gè)選擇謂詞 22，5.8M空間,5.3 Cost formula,I/O時(shí)間、CPU資源開銷建模 Basic blocks index 掃描、table retrieve、FSM匹配 優(yōu)化器工作方式 利用簡單直方圖確定所有謂詞的分區(qū)選擇 利用復(fù)雜直方圖確定結(jié)果選擇 將結(jié)果、index、table信息輸入cost formula 優(yōu)化器評估cost formula 返回合適的plan ，做query,6.實(shí)驗(yàn)結(jié)果,ORDBMS，Periscope 分區(qū)和結(jié)果選擇對算法的影響 運(yùn)行優(yōu)化器 Periscope，Wisconsin大學(xué)的SHORE存儲管理器 Periscope ORDBMS WindowsLinux Windows 850MHZ，PIII，W2000 professional，128M，10GB Li