蛋白质序列二级结构的搜索.ppt

1、蛋白质序列二级结构的搜索,Abstract,生命科学家使用的生物数据集的查询工具效率低下 在基于二级结构的大型数据集上搜索的问题 定义了直观的二级结构的查询语言 评估查询的算法 在Periscope、ORDBMS上实现算法 框架：优化查询、评估各种查询估计计划的开销 高效、交互式的二级结构查询（大型蛋白质数据集）,1.Introduction,人类基因组工程： 从蛋白质和DNA序列中得出有意义的生物信息、知识（bioinformatics）。 确定基因的位置和功能，观察蛋白质之间的反应，蛋白质保持时蛋白质的功能结构。 提出问题： 与大型生物数据集的分析密切相关 存储和查询大型基因、蛋白质数据库

2、,1.1生物背景知识,蛋白质的结构组织：四层 主结构：氨基酸的线性序列，蛋白质识别 二级结构：氨基酸的线性序列折叠成三维结构：-螺旋（helix）， -片（sheet），翻转（loop） 三维结构决定蛋白质的功能 模式和排列：变革性的关系 二级结构折叠的类型、长度、开始位置：功能,1.2科学动力,发现新的蛋白质、新的功能：确定蛋白质的功能和类型 已有方法 搜索已知的蛋白质数据库，和未知的蛋白质相匹配 分析相似蛋白质的功能和分类，得出共同点 简单基础：定义了蛋白质相似性 蛋白质结构和搜索目标的不同，相似性的定义不同：匹配主结构；匹配二级结构（预测生物分子反应）； 同样的级别上也有不同：一部分；整

3、个序列 Flexible；efficient BLAST 服务器负载重；查询估计算法的效率 交互式的结果：验证、否定一些假设 高效的查询估计技术,1.3内容,定义了简单、直观的查询语言：基于分区的二级结构查询 识别不同的算法，有效地估计查询。 由于查询和分区选择，算法选择对查询的执行有突出的影响 查询优化框架： 基于查询和数据特征选择最优查询计划 直方图：精确、空间小 在Periscope、ORDBMS上实现： 现实数据集、检验算法 高效,2.蛋白质格式（format),依赖于预测工具 大部分已知蛋白质的二级结构都是预测度量 准确率：60%70% Predator：单氨基酸序列的残余氢的识别

4、65%；本机运行 蛋白质名，氨基酸长度，主结构，预测的二级结构,3.查询语言和例子,3类原子查询 3类二级结构（h、e、l）；成组出现；按类型和长度表示二级结构序列 查询：分区谓词序列,4.查询估计技术,Complex Scan of Protein Table（CSP） 普通分区技术 Simple Scan of Segment Table(SSS) 扫描整个分区，利用INLJ得到蛋白质，FSM Index Scan of Segment Table（ISS） 扫描索引，INLJ Multiple Index Scans of Segment Table(MISS n) ISS的概化，扫描B

5、树索引N次，2n谓词数，n-way-sort-merge-join,INLJ,4.1Complex Scan of Protein Table（CSP）,扫描蛋白质表，找到蛋白质，逐个对比蛋白质的二级结构，返回信息 non-deterministic finite state machine(FSM) 二级结构每次输入FSM一个字符，直到输入一个最终（匹配）状态，或确定不匹配 每个query对应一个FSM 一个蛋白质可能匹配多次：在蛋白质的每个位置都运行FSM匹配测试,4.2普通分区技术,基于分割结构 把蛋白质的二级结构分割为相同类型的部分，分别存入分区表，多属性：类型、长度、原始蛋白质id、

6、分区的起始位置 Multi-attribute B+树索引，基于类型和长度 Clustered B+树索引 IndexNested Loops Join（INLJ），B+树：连接蛋白质表和分区表 id进行排序 Non-gap的QUERY，一次扫描分区表、索引就可以得到结果 （略）,5.1 Query 优化和估计,决定使用哪个plan来估计query 为4个plan的CPU，I/O开销建模(cost function) 两个直方图： 基本直方图：决定query谓词的选择 复杂直方图：估计结果蛋白质的选择 输入:每个query谓词选择、结果选择的估计 基本直方图： k*3矩阵（e h l），k是直

7、方图桶的数量 72代表的数量 最后一个桶：长度=k的所有分区 k=100:足够小;足够大 248,375蛋白质、10,288,769分区，13建立直方图，query 优化器1ms/谓词，99%的分区占1.2KB空间,5.2 复杂直方图,整个query结果的选择，而不是给定的query谓词： 寻找同一个字符串里多属性以某个次序出现的概率。 单个属性、多个无序属性 4维矩阵 Protein id Start position 长度 类型 3472代表第3个bucket的蛋白质的第4个bucket 的开始位置,5.2.2结果基数估计,假设:segment在 protein id和 start pos

8、ition上均匀分布 简单起见,对应于同一个protein id 结果基数=每种情况匹配数的估计 结果选择=结果基数/总的蛋白质数 Case 1-3: 结果选择=第一个桶匹配数/桶内蛋白质数*第二个桶的匹配数/桶内蛋白质数 Case 4-6: Np1=1/50*(number of p1) Np2 =40/50*(number of p2) 设每个桶有100个protein id 结果选择=np1*np2/100,5.2.3直方图分析,复杂直方图的精确度 与蛋白质的实际数量相比较，80% 计算时间 谓词的数目和桶的开始位置 谓词增加，时间大幅度上升 谓词增加，准确度并没有明显增加，只需要2、3

9、个选择谓词 22，5.8M空间,5.3 Cost formula,I/O时间、CPU资源开销建模 Basic blocks index 扫描、table retrieve、FSM匹配 优化器工作方式 利用简单直方图确定所有谓词的分区选择 利用复杂直方图确定结果选择 将结果、index、table信息输入cost formula 优化器评估cost formula 返回合适的plan ，做query,6.实验结果,ORDBMS，Periscope 分区和结果选择对算法的影响 运行优化器 Periscope，Wisconsin大学的SHORE存储管理器 Periscope ORDBMS WindowsLinux Windows 850MHZ，PIII，W2000 professional，128M，10GB Li