蛋自质序列三级结构的搜索
蛋白质序列二级结构的搜索
Abstract 生命科学家使用的生物数据集的查询工具效率 低下 在基于级结构的大型数据集上搜索的问题 定义了直观的二级结构的查询语言 平估查询的算法 在 Periscope、 ORDBMS上实现算法 框架优化查询、平估各种查询估计计划的开销 高效、交互式的二级结构查询、(犬型蛋白质数据集
Abstract • 生命科学家使用的生物数据集的查询工具效率 低下 • 在基于二级结构的大型数据集上搜索的问题 – 定义了直观的二级结构的查询语言 – 评估查询的算法 – 在Periscope、ORDBMS上实现算法 • 框架：优化查询、评估各种查询估计计划的开销 • 高效、交互式的二级结构查询（大型蛋白质数据集）
1 Introduction 人类基因组工程: 从蛋自庚和DNA序列中得出有意义的生物信 息、知识( bioinformatics 确定基因的位置和功能,观察蛋白质之间的 反应,蛋白质保持时蛋白质的功能结构 提出间题: 与大型生物数据集的分析密切相关 存储和查询大型基因、蛋白质数据库
1. Introduction • 人类基因组工程： – 从蛋白质和DNA序列中得出有意义的生物信 息、知识（bioinformatics）。 – 确定基因的位置和功能，观察蛋白质之间的 反应，蛋白质保持时蛋白质的功能结构。 • 提出问题： – 与大型生物数据集的分析密切相关 – 存储和查询大型基因、蛋白质数据库
1生物背景知 蛋自质的结构组织:四层 主结构:氢基酸的线性序列,蛋质识别 级结构:氨基酸的线性序列折叠成三维结构 螺旋(eix),p片(ske),了翻转(o 三维结构决定蛋自质的功能 模式和排列:变革性的关系 级结构折叠的类型、长度、开始位置:功能
1.1 生物背景知识 • 蛋白质的结构组织：四层 – 主结构：氨基酸的线性序列，蛋白质识别 – 二级结构：氨基酸的线性序列折叠成三维结构：- 螺旋（helix）， -片（sheet），翻转（loop） – 三维结构决定蛋白质的功能 – 模式和排列：变革性的关系 • 二级结构折叠的类型、长度、开始位置：功能
2科学动力 发现新的蛋白质、新的功能:确定蛋白质的功能和类 型 已有方法 搜索已知的蛋自质数据库,和未知的蛋白质相匹配 分析相似蛋自质的功能和分类,得出共同点 简单基础:定义了蛋白质相似性 蛋自质结构和搜索目标的不同,相似性的定义不同:匹配主结构 匹配二级结构预测生物分子反应 同样的级别上也有不同:部分整个序列 Flexible: efficient BLAST 服务器负载重;查询估计算法的效率 互式的结果:验证、否定一些假设 高效的查询估计技术
1.2 科学动力 • 发现新的蛋白质、新的功能：确定蛋白质的功能和类 型 • 已有方法 – 搜索已知的蛋白质数据库，和未知的蛋白质相匹配 – 分析相似蛋白质的功能和分类，得出共同点 – 简单基础：定义了蛋白质相似性 • 蛋白质结构和搜索目标的不同，相似性的定义不同：匹配主结构； 匹配二级结构（预测生物分子反应）； • 同样的级别上也有不同：一部分；整个序列 – Flexible；efficient – BLAST • 服务器负载重；查询估计算法的效率 • 交互式的结果：验证、否定一些假设 • 高效的查询估计技术
L3容 定义了简单、直观的查询话言:基于分区的 级结构查询 识别不同的算法,有效地估计查询 由于查询和分区选择,算法选择对查询的执行有突 出的影响 查询优化框 架 基于查询和数据特征选择最优查询计划 直方图:精确、空间小 在 Periscope、 ORDBMS上实现: 现实数据集。检验算法 高效
1.3 内容 • 定义了简单、直观的查询语言：基于分区的二 级结构查询 • 识别不同的算法，有效地估计查询。 – 由于查询和分区选择，算法选择对查询的执行有突 出的影响 • 查询优化框架： – 基于查询和数据特征选择最优查询计划 – 直方图：精确、空间小 • 在Periscope、ORDBMS上实现： – 现实数据集、检验算法 – 高效
2.)蛋白质格式( format 依赖于预测工具 大部分已知蛋自质的二级结构都是预测度量 准确率:60%70% Predator:单氨基酸序列的残杀氢的识别 65%;机运行 蛋白质名,氨基酸长度,主结构,预测的三级结构 name: t2 1296 id: 1 ⊥ ength:554 primary structure: GQI SDSIEEKRGFFSTKR secondary structure: HLLLLLLLLLLHHHEEEE probability: 855577763445449476. Figure 1: Sample protein
2. 蛋白质格式（format) 依赖于预测工具 – 大部分已知蛋白质的二级结构都是预测度量 – 准确率：60%－70% – Predator：单氨基酸序列的残余氢的识别 • 65%；本机运行 – 蛋白质名，氨基酸长度，主结构，预测的二级结构 –
3.查询语言和例子 3类原子查询 3类二级结构(he1:成组出现;极类 型和长度表示三级结构序列 查询:分区谓词序列 Query ->(Segments) Segments - Segment* Segment 1p{h35>} lb any integer >=0 ub - any integer > 0 Segment Constraint: lb <= ub Figure 2: Query Language Definition
3. 查询语言和例子 • 3类原子查询 – 3类二级结构（h、e、l）；成组出现；按类 型和长度表示二级结构序列 – 查询：分区谓词序列
4.查询估计技术 Complex Scan of Protein Table(CSP 通分区技术 Simple Scan of Segment Table(sss) 扫描整个分区,利用NJ得到蛋白质,FSM Index Scan of Segment Table (ISS) 扫描索引,INLJ Multiple Index Scans of Segment Table(MISS n IS的概化,扫描B树索引N次,2n谓词数 way-sort-merge -join INI
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树索引N次，2<n<谓词数，nway-sort-merge-join,INLJ
4.1 Complex Scan of Protein Table(CSP) 扫描蛋白质表,找到蛋白质,逐个对比 蛋白质的二级结构,返回信息 non-deterministic finite state machine(FSM) 级结构每次输入FSM一个字符,直到输入 个最终匹配)状态,或确定不匹配 每个qu对应个FSM 个蛋白质可能匹配多次:在蛋白质的每个 位置都运行FSM匹配测试
4.1 Complex Scan of Protein Table（CSP） • 扫描蛋白质表，找到蛋白质，逐个对比 蛋白质的二级结构，返回信息 • non-deterministic finite state machine(FSM) – 二级结构每次输入FSM一个字符，直到输入 一个最终（匹配）状态，或确定不匹配 – 每个query对应一个FSM – 一个蛋白质可能匹配多次：在蛋白质的每个 位置都运行FSM匹配测试