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

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

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

4、65%；本機運行 蛋白質(zhì)名，氨基酸長度，主結構，預測的二級結構,3.查詢語言和例子,3類原子查詢 3類二級結構（h、e、l）；成組出現(xiàn)；按類型和長度表示二級結構序列 查詢：分區(qū)謂詞序列,4.查詢估計技術,Complex Scan of Protein Table（CSP） 普通分區(qū)技術 Simple Scan of Segment Table(SSS) 掃描整個分區(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ì)，逐個對比蛋白質(zhì)的二級結構，返回信息 non-deterministic finite state machine(FSM) 二級結構每次輸入FSM一個字符，直到輸入一個最終（匹配）狀態(tài)，或確定不匹配 每個query對應一個FSM 一個蛋白質(zhì)可能匹配多次：在蛋白質(zhì)的每個位置都運行FSM匹配測試,4.2普通分區(qū)技術,基于分割結構 把蛋白質(zhì)的二級結構分割為相同類型的部分，分別存入分區(qū)表，多屬性：類型、長度、原始蛋白質(zhì)id、

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

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

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

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