分子图模型
通常使用一种模型,在该模型中,化合物以原子为节点,键为边的图形表示,通常省略氢。节点存储信息(标签),例如原子类型、电荷、多重性和质量,而边存储键合顺序。每个都可以具有关于芳族和立体异构的信息。至于键序,最好以π电子而不是边缘的形式给出节点,以反映实际的原子轨道和三维结构
分子图通常表示为无边的无向图。具有边缘方向(存在单向路径)的图称为有向图。
分子图通常是简单图。简单图没有自环(连接相同节点的边,自环),也没有多边(两个节点之间的多边)。
有机化合物分子图的特征
程度是与节点相邻的边数。对于有机化合物,与一个原子键合的原子数很少超过4。对于过渡金属配位或高价分子,可能超过4。
平面图至少有一个节点排列,当该图放置在平面上时,其边缘不相交。外平面图是其中所有节点都位于图的外边缘的图,尤其是在平面图中。四面体和富勒烯是三维的,但它们是平面图,分子图是相对低阶的图(稀疏图)很重要。与矩阵(邻接矩阵)相比,通过映射实现稀疏图效率更高。一些通用图算法在稀疏图中特别有效。类似地,即使对于非平面图中的计算时间随节点数的增加而呈指数增长的问题,对于平面图和外平面图,也可能存在可以更快地计算出的算法。
环结构检测
化学结构中的环对应于图论中的一个循环(更确切地说,这是一个简单的循环,因为它是一个循环不多次通过同一节点的循环)。可以通过跟随某个节点中的相邻节点来判断图是否具有循环。如果您可以从其他路线到达已经到达的节点,则该图将具有一个循环。当执行这样的搜索时,生成上面所示的路线。这称为生成树。这是原始图的最大子图,没有周期。
图中的循环数等于生成树中未包括的边数(此数称为电路等级)。
Smallest set of smallest rings(SSSR)
现在已经确定了环的数量,可以有任意数量的路径和环尺寸。这种情况下,经常选择最小化环数和环大小的组合。可以使用确定图表最小权重循环基础的算法来确定SSSR。
无论选择哪种循环组合,上一个生成树中未包含的四个边始终会包含在每个循环中。换句话说,这些边缘可以对应于四个周期中的每个周期。此edge-> cycle组合称为基本循环基础,并表示为一组向量(每个循环是与边的总数相同维的向量,1是构成循环的边,而0是另一个)一点串)。这些向量具有以下特征:当它们彼此互斥或时,它们成为组合各个循环的循环。SSSR决策算法利用了封闭向量空间的这一特性。
稠环的检测
从生物活性和易于合成的角度出发,在药物发现中经常注意到被称为Bemis-Murcko骨架的稠合环结构。这种局部结构称为2边连接的组件,因为当以图形形式查看时,所有节点都由两个或更多边连接。可以说这是一个子图,仅通过切割一个边就不能将其分解为两个或更多部分。相反,如果切割一个边缘分解为两个或多个组件,则该边缘称为桥。可以通过应用Hopcroft-Tarjan算法来检测桥梁。通过从原始图形中删除桥,可以保留2边连接的组件。
子图同构与结构搜索
用词很难解释子图的同构,但是如果您处理了复合数据,那么我认为如果说子结构匹配很容易理解。VF2算法被称为确定子图同构的代表性算法。这是一种相对简单的基于深度优先搜索(DFS)的算法,如果不是子图同构,我们可以回到上一个阶段并探索其他可能性。根据其生成方式,某些子图称为节点诱导子图或边诱导子图。节点派生的子图是从原始图的节点集的子集唯一确定的子图,而边缘派生的子图是从原始图的边集的子集唯一确定的子图。
由于VF2算法是一种确定节点诱导子图的同构性的技术,因此当应用于边缘诱导子图时,它会生成分子图的线图,并确定该线图的节点诱导子图的同构性。在这种情况下,有必要确认通过转换为折线图不会产生delta-Y交换。
由于确定子图同构的问题是NP问题,因此随着分子图大小的增加,计算时间可能呈指数增长。但是,如果是类似药物的大小,则计算时间不太可能成为问题。在实际的库搜索中,在应用VF2之前,可以通过预先过滤与子图不明显相同的那些来加快速度,例如节点数,边数,原子种类,环数和大小。
最大公共子结构(Maximum common substructure)
即使查询分子与数据库分子不完全匹配,也可能想知道其中有多少个通用结构。程度是最大公共子结构(MCS),可以使用与子图同构相同的方法来计算。也可以按原样使用公共键(边)的数量作为阈值,或将其转换为相似性指标,例如Jaccard / Tanimoto系数。
部分结构匹配的情况下,可以在结构匹配时(或确定它们不匹配时)中止搜索,但是在MCS的情况下,可以输出最优解,直到搜索到所有可能性为止。有必要设计诸如确定计算时间的上限,当公共边缘的数量超过阈值时中止搜索或者使用高速近似解算法的手段。
尽管即使使用VF2算法也可以计算MCS,但已经开发了许多更高效且针对特定应用的算法。作为开源的MCS实现,RDKit具有基于DFS的算法FMCS和VF2。
作者丨王建民
单位丨超级计算长沙中心,湖南大学
研究方向丨药物设计、生物医药大数据
参考资料
DrugAI
本文为DrugAI原创编译整理,如需转载,请在公众号后台留言。