最新北京大学化学信息学course-12ppt课件.ppt

《最新北京大学化学信息学course-12ppt课件.ppt》由会员分享，可在线阅读，更多相关《最新北京大学化学信息学course-12ppt课件.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2Morgan算法13233321112223 different values 1, 2, 3 标记所有节点的度找到所有不同的度值9完全结构匹配的应用之一化合物登记管理系统w 许多制药公司都拥有化合物登记管理系统 (Compound Registration System)n内部化合物数据库（法人数据库/企业数据库）n与其它信息，如筛选数据、实物存储号码等，相关联n与其它实验室信息系统相连w 登记系统的基本功能n检查化合物结构和分子式的一致性n查重n信息关联10结构的图表示 Graph132333211122211图同构Isomorphism在图论中，两个图同构的条件G1 = (V1, E1

2、), G2 = (V2, E2) f : V1 V2f(x), f(y) E2当且仅当x, y E112暴力法 (brutal-force)w 对G1中的每一个节点 n寻找G2中未映射的节点w 检查两个图中的节点邻接的一致性w 计算复杂度nn (n-1) (n-2) (n-3) 3 2 1n9! = 362 880n10! = 3 628 80013计算复杂度w 时间复杂度n如果输入的数据增加一倍，计算时间增加多少?w 空间复杂度w 例如：比较一个化合物是否在给定的n个化合物集合中nO(n) “order-n”w 比较两个各拥有n个化合物集合是否相同nO(n2) “order-n-square

3、d”14计算复杂度w 多项式复杂度nO(n3), O(n4), O(log n), O(n log n) 等.w 指数复杂度nO(2n)w 图同构的暴力算法复杂度nO(n!)15计算复杂度w 对于某些问题可以找到有效的算法来降低计算复杂度n搜索排序的串l顺序搜索： O(n)l二分法：O(log n)w NP问题16结构匹配的计算复杂度w 图同构多数情况下是NP完全问题w 子图同构是图同构的推广w 子图同构被证明是NP完全问题w 子图同构的NP问题是指最坏情况，不是平均情况17子结构匹配算法效率的提高分子结构的特点节点的连接度很低节点的不同着色舍去氢原子提高效率的方法使用高速计算机或使用并行/分

4、布计算使用技巧避免那些肯定是错误的匹配分支预处理数据库中的结构18回溯法w 暴力法的一种改进w 在搜索解空间过程中，放弃肯定是错误的部分w 最坏情况仍然与暴力法相同n首先选择任意一对节点进行对比n如果成功，继续比较其邻接的节点n否则，返回到前一次的节点，再开始比较19回溯法w 进一步提高效率的方法n仅比较具有相同元素类型、电荷和键型等的节点（相当于节点的着色）n从非常见原子类型或具有更多邻接节点的节点开始。20划分和驰豫法 Partitioning and Relaxationw 通常与回溯算法结合使用w 划分的目的是减少需要尝试的映射w 算法的步骤包括划分和驰豫两步n首先根据原子类型等信息进

5、行初步划分n划分过程逐步细化（驰豫）n如果某个查询节点的可能匹配节点表为空，则说明目标结构中没有查询的子结构21一些发表的算法时间表w Ray and Kirsch算法 (1957)n基本的回溯法w Sussenguths 划分算法 (1965)n将驰豫技术称为“连接性质”, 使用回溯作为最后的手段w Figuerass 削减集算法 (1972)w Ullmanns 算法 (1976)w von Scholleys 驰豫算法 (1984)22筛选法Screeningw 子结构匹配算法在数据库搜索中面临的问题n数据库中每个结构必须顺序比较n由于目标结构中不包括查询分子中的子结构，因此很多目标分子

6、肯定是不匹配的w 筛选法可以用于提高数据库搜索的速度w 使用分子指纹法23筛选法Screeningw 步骤n计算查询结构的指纹位串n与数据库中的指纹相比较，只有包含相应的位的结构需要进行匹配l查询结构:00000100010101000001010011010100l目标结构1:00010100010101000101010011110100 匹配l目标结构2:00000000100101001001000011100000 不匹配w 位串比较的速度非常快24筛选法Screeningw 一种改进的算法n为每一子结构生成所有结构的位串nAND操作查询结构中包含的每一子结构的串将得到所有需要查询的

7、结构25筛选法的效率w 理想情况下，期望在筛选步过滤掉尽可能多的结构 （99%） w 需要好的指纹构建方法n对数据库中的所有化合物的子结构模式进行统计n使用统计分布中具有中等程度分布的结构模式作为指纹26筛选法的效率w 理想情况下，期望在筛选步过滤掉尽可能多的结构 （99%） w 需要好的指纹构建方法n对数据库中的所有化合物的子结构模式进行统计n使用统计分布中具有中等程度分布的结构模式作为指纹n各种指纹模式要求相对独立27某些分子指纹方法的特殊处理w 计算子结构的哈希值，不同的子结构模式具有不同的位长w 将整个位串折叠0010 0100 0101 0010 1001 1010 1101 010

8、00010 0100 0101 00101001 1010 1101 01001011 1110 1101 011028提高效率的硬件方法w 使用高速计算机w 使用海量内存，将位串操作全部在内存中进行w 并行处理 n数据库并行n算法并行 29数据库的预处理w 可以加快完全结构匹配的计算w 正则命名技术 (NP-完全)n将数据库中的结构进行预处理n存储所有结构的正则命名n使用正则命名进行检索，比通常的图同构算法要快w 使用树状层次结构将数据库中的结构作分类索引n原子类型=连接度=邻接原子类型=邻接原子连接度=具体结构30CCBrCCFCCCOCCCBrCCCCCCCF|CCCF|FCentral

9、atom typeNumber ofConnectionsFirstNeighbourSecondNeighbourThirdNeighbour31子结构查询语言SMARTSw Daylight使用SMILES的扩展语言来描述复杂子结构 (SMARTS)n原子类型示例lCX3具有3个连接的碳原子lNr5五元环上氮n组合用的逻辑表达符 l! (NOT)l& (AND 高优先级)l, (OR)l; (AND 低优先级) 32子结构查询语言SMARTSN&X3;H2,H1;!$(NC=*)nitrogen3 connsnitrogenconnected tocarbon with doublebon

10、d to any atomANDANDOR2 attachedhydrogens1 attachedhydrogenANDNOTw 递归的使用SMARTS可以描述非常复杂的结构模式n如一级或二级胺，而不是酰胺33商用软件中的子结构匹配模块nMDL Information Systems Inc.lMACCS, ISISnDaylight Chemical Information Systems Inc.lTHOR, MERLIN, DayCart (Oracle cartridge)nIDBS ActivityBasenAccelrys (Synopsys / Oxford Molecular

11、)lAccord Search Engine / RS334相似性搜索w 相似性原理:“结构相似的分子期望具有相似的性质或生理活性”Mark Johnson and Gerry Maggiora (Eds.) Concepts and Applications of Molecular Similarity. Wiley, New York, 1990199035什么是相似性?“Similarity is in the eye of the beholder”不同的相似性描述方法n等价类n相似度 (0.0 1.0)n距离 (1.0-0.0)36等价类w 如果化合物在某种描述符标度下相等，则可以

12、看作等价类n分子式n相同的图表示n相同环系n相同分子指纹37等价类w 不同的化合物具有相同的图表示NOHONCH3CH338分子指纹相似性w 计算分子中相同的位1w 计算每个分子中的位1A:00010100010101000101010011110100 13 bits 1 (A)B:00000000100101001001000011100000 8 bits 1 (B)A AND B:00000000000101000001000011100000 6 bits 1 (C)n相似性因子可以从A，B，C计算ABC39Tanimoto 因子w 相似性 = CA + B C = 6 / (13

13、+ 8 6) = 0.4w The Tanimoto 是化学信息学中最常用的相似性指标，又称Jaccard因子ABC40什么是相似性?w 是否结构中不具备某种特征就可以认为是相似?CHCHCHCHCHCHCH2CH2CH2CH2CH2CH2CH2CH2CH2CH2CH241简单匹配因子w 考虑共同“缺乏特征”的相似性因子 (D)w 相似性 = C + DN = (6 + 17) / 32 = 0.719w N is 指纹长度nN = A + B C + DABCD42非对称的相似性w 某些因子具有以下特性S(A,B) S(B,A)ne.g. Tversky 相似性相似性= C (A C) +

14、(B C) + C ， 是用户定义的参数43非对称的相似性(Tversky)T = C (A C) + (B C) + C w 如果 = = 1, 退化为Tanimoto 因子w 如果 = = , 退化为Dice因子w 如果 , T 变成非对称n如果 = 1 且 = 0, T = C / Ai.e. the fraction of A which it is has in common with Bl如果 T = 1.0, 表明A 是B的“子结构”ABC44相似性和距离w 距离与相似性相反nD = 1 Sw 与相似性因子对应的距离因子名:nTanimoto 因子 = Soergel 距离n简单

15、匹配因子 = 规一化的Hamming距离45距离因子w 与多维空间的距离类似，但不局限于此w 某些距离因子成为距离标度distance metricsnDA,B = 0nDA,A = 0nDA,B当A != BnDA,B = DB,A nDA,B = DA,C + DB,C46描述符的选择w 相似性的值严重依赖所选择的相似性指标w 多个指标之间的多重相关47结构多样性w 化合物组合库的一个重要特征w 思想n尽可能的覆盖化学结构空间 (chemical structure space)n避免出现过多相似性的结构48多样性的度量w 计算化合物集合多样性的数值指标n目前还没有所谓最好的指标n存在很多

16、指标，通常基于某种相似性或距离指标l所有化合物对距离的平均值，存在O(N)时间的算法l所有化合物对距离的最小值，All-pair计算需要 O(N2)时间复杂度l其它的复杂标度49基于单元的多样性Cell-basedw 通常使用具有连续值的描述符n“化学空间” 被划分称不同的格子l每个描述符对应一个维度l每个格子（单元）具有一定的描述符取值范围n化合物根据描述符取值放入不同的格子n多样性的标度表示为统计占用/未占用格子的比例，以及平均格子的占用度50多样性子集的选择w 在具有大量化合物的库的合成测试时通常使用某种相似性指标选取子集进行合成测试w 对组合库尤为重要n首先设计大的虚拟库n选取子集进行合成51 结束语结束语