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

1、结构生成w 二维结构自动生成w 三维结构自动生成w 化合物命名自动生成Morgan算法13233321112223 different values 1, 2, 3 标记所有节点的度找到所有不同的度值Morgan算法3. 将每个节点的邻接点的度相加作为节点的新值4. 找到所有不同的度值5. 重复3,4步至不再有新的节点值出现35565653335563 different values 3, 5, 6 Morgan算法51310161214115561011128 different values 5, 6, 10, 11, 12, 13, 14, 16 1325243424182612121

2、42426309 different values 12, 13, 14, 18, 24, 25, 26, 30, 34 256151824268482424185148429 different values 18, 24, 25, 42, 48 51, 61, 68, 82 Morgan算法256151824268482424185148429 different values 18, 24, 25, 42, 48 51, 61, 68, 82 6112710913811610213342426810913315010 different values 42, 61, 68, 102, 1

3、09, 116, 127, 133, 138, 150 6112710913811610213342426810913315010 different values 42, 61, 68, 102, 109, 116, 127, 133, 138, 150 Morgan算法6112710913811610213342426810913315010 different values 42, 61, 68, 102, 109, 116, 127, 133, 138, 150 12361127109138116102133424268109133150123456789101112136. 将最高序

4、号标为17. 将其邻接点按顺序标号8. 如果邻接点的值相同按某种规则判断其顺序9. 将所有节点标号完全结构匹配和子结构匹配w 完全匹配 (Q = M)w 查询条件是整个分子w 查询某一分子是否数据库中?w 不能识别共振式，不能区分立体异构 w 子结构匹配 (Q M)w 查询条件式结构片断，或原子及键的某种连接模式w 查询分子中是否包含这一子结构模式，或数据库中包含多少具有该子结构的分子?w 超结构匹配与子结构匹配相对比）(Q M)w 查询条件是整个分子完全结构匹配w 对于大型数据库库来说搜索速度非常关键。w 简单方法式使用正则命名的字符串，如：U-SMILESw 按字典顺序查询w 使用哈希表

5、(hash table) 提高检索速度w 使用SMILES计算哈希值w 使用连接表计算哈希值完全结构匹配的应用之一化合物登记管理系统w 许多制药公司都拥有化合物登记管理系统 (Compound Registration System)w 内部化合物数据库法人数据库/企业数据库）w 与其它信息，如筛选数据、实物存储号码等，相关联w 与其它实验室信息系统相连w 登记系统的基本功能w 检查化合物结构和分子式的一致性w 查重w 信息关联结构的图表示 Graph1323332111222图同构Isomorphism在图论中，两个图同构的条件G1 = (V1, E1), G2 = (V2, E2) f :

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

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

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

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

10、据库搜索的速度w 使用分子指纹法筛选法Screeningw 步骤w 计算查询结构的指纹位串w 与数据库中的指纹相比较，只有包含相应的位的结构需要进行匹配w 查询结构:00000100010101000001010011010100w 目标结构1:00010100010101000101010011110100 匹配w 目标结构2:00000000100101001001000011100000 不匹配w 位串比较的速度非常快筛选法Screeningw 一种改进的算法w 为每一子结构生成所有结构的位串w AND操作查询结构中包含的每一子结构的串将得到所有需要查询的结构筛选法的效率w 理想情况下，

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

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

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

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

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

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

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

18、C w ， 是用户定义的参数非对称的相似性(Tversky)T = C (A C) + (B C) + C 假如 = = 1, 退化为Tanimoto 因子假如 = = , 退化为Dice因子假如 , T 变成非对称假如 = 1 且 = 0, T = C / Ai.e. the fraction of A which it is has in common with B假如 T = 1.0, 表明A 是B的“子结构”ABC相似性和距离w 距离与相似性相反w D = 1 Sw 与相似性因子对应的距离因子名:w Tanimoto 因子 = Soergel 间隔w 简单匹配因子 = 规一化的Hamming距离距离因子w 与多维空间的距离类似，但不局限于此w 某些距离因子成为距离标度distance metricsw DA,B = 0w DA,A = 0w DA,B当A != Bw DA,B = DB,A w DA,B = DA,C + DB,C描述符的选择w 相似性的值严重依赖所选择的相似性指标w 多个指标之间的多重相关结构多样性w 化合物组合库的一个重要特征w 思想w 尽可能的覆盖化学结构空间 (chemical structure space)w 避免出现过多相似性的结构多样性的度量w 计算化合物集合多样性的数值指标w 目前还没有所谓最好的指标w 存在很多指标，通常基于