Figure 3. MetaMapp of the metabolic modules that were altered in E. coli grown in galactose.
估计阅读时长: < 1 分钟

在工作之中可能会遇到需要进行两个网络图对象之间的相似度计算的情形:例如在质谱数据分析的化学信息学计算工作之中,我们在解析SMILES字符串得到分子图之后,可以基于图相似度比较计算方法来比较计算两个代谢物分子图之间的结构上的相似度。

在计算相似度方法上,存在有两种经典的相似度计算方法:我们一般是以cos相似度计算或者杰卡德相似度计算来评价两个向量之间的相似度。其实很多的相似度计算问题最终都会被转换为向量间的cos/jaccard相似度计算问题。今天所要讨论的图相似度计算同样也可以进行相应的问题转换。

问题一:图对象降维为向量

因为cos/jaccard相似度都是基于向量进行计算的,但是图对象是一种复杂的网状数据结构,没有办法比较有效的通过一维数据进行表示。所以问题来了,如果我们需要将所需要进行比较计算的两个图对象转换为两个向量,那应该怎样进行向量的转换操作呢。

在进行向量转换问题上,我们首先需要先来回顾一下图对象的数据结构基础。对于一个图对象是由两部分的数据所构成的:

  1. vertex:数据对象实体,里面会记录有数据对象的一些属性值等元数据
  2. edge:数据对象实体间的关联关系

假设对于图数据中的任意一个节点对象而言,在其元数据之中存在有节点类型这一种属性的话,那么我们就可以依据节点类型以及网络的边连接拓扑结构来进行问题转换了。

很幸运的是,在工作中所遇到的图对象中的节点数据都是属于具有节点类型属性的数据,例如:

  1. 微生物网络图:节点类型可以为微生物的某一个层级上的物种分类
  2. 代谢物分子图:节点类型可以为原子的标签,例如碳原子,氢原子,氧原子等
  3. 代谢通路图:节点类型可能为代谢物,蛋白酶

基于上面具有节点类型标签的图对象,我们就可以进行两个图对象之间的jaccard相似度计算。在这里根据杰卡德相似度计算公式,我们可以定义:

jaccard(g1, g2) = similar / (similar + distinct)
  • similar: 两个图对象中,网络连接拓扑结构相似的节点数量
  • distinct:两个图对象中,没有找到在所比较的另一个图中具有网络连接拓扑结构相似的节点数量

那现在问题转换为:我们只需要计算出上面的jaccard公式中所需要的两个数据集合,就可以完成两个图对象之间的杰卡德相似度计算了。可以看得见,在上面的公式中,计算的集合都是以节点间的拓扑结构相似度计算为基础的。那下面我们就继续往下深入,来了解任意两个节点之间的拓扑结构相似度计算问题。

节点拓扑结构相似度计算

Figure 3. MetaMapp of the metabolic modules that were altered in E. coli grown in galactose.

https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0078360

Latest posts by 谢桂纲 (see all)

Attachments

  • pone.0078360.g003 • 2 MB • 2 click
    06.08.2022

    https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0078360

No responses yet

Leave a Reply

Your email address will not be published.