北京大学化学信息学curse-12.ppt

Morgan算法 Morgan算法 Morgan算法 Morgan算法 Morgan算法 6. 将最高序号标为1 7. 将其邻接点按顺序标号 8. 如果邻接点的值相同 按某种规则判断其顺序 9. 将所有节点标号 完全结构匹配和子结构匹配 完全匹配 (Q = M) 查询条件是整个分子 查询某一分子是否数据库中? 不能识别共振式，不能区分立体异构 子结构匹配 (Q ? M) 查询条件式结构片断，或原子及键的某种连接模式 查询分子中是否包含这一子结构模式，或数据库中包含多少具有该子结构的分子? 超结构匹配（与子结构匹配相对比）(Q ? M) 查询条件是整个分子 完全结构匹配 对于大型数据库库来说有哪些信誉好的足球投注网站速度非常关键。 简单方法式使用正则命名的字符串，如：U-SMILES 按字典顺序查询 使用哈希表 (hash table) 提高检索速度 使用SMILES计算哈希值 使用连接表计算哈希值 完全结构匹配的应用之一化合物登记管理系统 许多制药公司都拥有化合物登记管理系统 (Compound Registration System) 内部化合物数据库（法人数据库/企业数据库） 与其它信息，如筛选数据、实物存储号码等，相关联 与其它实验室信息系统相连 登记系统的基本功能 检查化合物结构和分子式的一致性 查重 信息关联 结构的图表示 － Graph 图同构－Isomorphism 在图论中，两个图同构的条件 G1 = (V1, E1), G2 = (V2, E2) f : V1 ? V2 {f(x), f(y)} ? E2 当且仅当 {x, y} ? E1 暴力法 (brutal-force) 对G1中的每一个节点 寻找G2中未映射的节点 检查两个图中的节点邻接的一致性 计算复杂度 n × (n-1) × (n-2) × (n-3) … × 3 × 2 × 1 9! = 362 880 10! = 3 628 800 计算复杂度 时间复杂度 如果输入的数据增加一倍，计算时间增加多少? 空间复杂度 例如：比较一个化合物是否在给定的n个化合物集合中 O(n) [“order-n”] 比较两个各拥有n个化合物集合是否相同 O(n2) [“order-n-squared”] 计算复杂度 多项式复杂度 O(n3), O(n4), O(log n), O(n log n) 等. 指数复杂度 O(2n) 图同构的暴力算法复杂度 O(n!) 计算复杂度 对于某些问题可以找到有效的算法来降低计算复杂度 有哪些信誉好的足球投注网站排序的串 顺序有哪些信誉好的足球投注网站： O(n) 二分法：O(log n) NP问题 结构匹配的计算复杂度 图同构多数情况下是NP完全问题 子图同构是图同构的推广 子图同构被证明是NP完全问题 子图同构的NP问题是指最坏情况，不是平均情况 子结构匹配算法效率的提高 分子结构的特点 节点的连接度很低 节点的不同着色 舍去氢原子 提高效率的方法 使用高速计算机或使用并行/分布计算 使用技巧避免那些肯定是错误的匹配分支 预处理数据库中的结构 回溯法 暴力法的一种改进 在有哪些信誉好的足球投注网站解空间过程中，放弃肯定是错误的部分 最坏情况仍然与暴力法相同 首先选择任意一对节点进行对比 如果成功，继续比较其邻接的节点 否则，返回到前一次的节点，再开始比较 回溯法 进一步提高效率的方法 仅比较具有相同元素类型、电荷和键型等的节点（相当于节点的着色） 从非常见原子类型或具有更多邻接节点的节点开始。 划分和驰豫法 Partitioning and Relaxation 通常与回溯算法结合使用 划分的目的是减少需要尝试的映射 算法的步骤包括划分和驰豫两步 首先根据原子类型等信息进行初步划分 划分过程逐步细化（驰豫） 如果某个查询节点的可能匹配节点表为空，则说明目标结构中没有查询的子结构 一些发表的算法时间表 Ray and Kirsch算法 (1957) 基本的回溯法 Sussenguth’s 划分算法 (1965) 将驰豫技术称为“连接性质”, 使用回溯作为最后的手段 Figueras’s 削减集算法 (1972) Ullmann’s 算法 (1976) von Scholley’s 驰豫算法 (1984) 筛选法－Screening 子结构匹配算法在数据库有哪些信誉好的足球投注网站中面临的问题 数据库中每个结构必须顺序比较 由于目标结构中不包括查询分子中的子结构，因此很多目标分子肯定是不匹配的 筛选法可以用于提高数据库有哪些信誉好的足球投注网站的速度 使用分子指纹法 筛选法－Screening 步骤 计算查询结构的指纹位串 与数据库中的指纹相比较，只有包含相应的位的结构需要进行匹配 查询结构: 00000100010101000001010011010100 目标结构1: 00010100010101000101010011