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

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

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

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

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

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

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

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

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

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

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

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

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

节点拓扑结构相似度计算

首先我们会需要从两个图之间的节点与节点之间的拓扑结构相似度开始学习两个图对象之间的相似度计算。

现在我们假设某一个节点类型为A,其在图1之中的网络连接拓扑结构为:A-B,A-C,A-D,A-B;而在图2之中,相同类型的A节点,其在图2之中的网络连接拓扑结构为:A-B,A-C,A-D,A-B,A-E。可以看得见,A节点的网络连接在两个图对象之间差别是在图2之中多了一个E节点连接,那我们怎么才能计算出A节点在两个图对象之间的相似度呢?其实,我们可以先对A节点所连接的邻接节点进行统计,例如,统计结果如下:

邻接节点 图1 图2
B 2 2
C 1 1
D 1 1
E 0 1

那现在这样子我们是不是就可以将两图之间的A节点的拓扑结构给转换为两个等长的向量了呢。那现在既然拥有了两个等长向量了,那我们就可以很方便的进行cos相似度计算或者杰卡德相似度计算了。基于上面的两个向量,我们可以计算出两个相似度得分值:cos=0.92582, jaccard=0.66667。

图对象拓扑结构相似度计算

基于上面的一个小结的学习,我们可以了解到是如何计算出两个节点之间的相似度的。那现在假设我们有一个阈值,例如0.8,只要两个节点之间的相似度大于这个阈值,就认为两个节点是一样的,这个时候我们就可以认为两个图对象之间具有一个交集节点。

现在,假设我们针对图1中的所有节点进行遍历。同时,针对图2中的节点也进行遍历,计算出图1与图二之中是否存在相同的交集节点。假设存在有,则交集大小增加1。则通过这样子的计算步骤,直到我们遍历完图1之中的所有节点,这个时候我们就拥有了两个图对象之间的交集大小intersect_size。接着我们可以将图1的节点数量加上图2的节点数量的总和减掉交集大小intersect_size即可得到两个图对象之间的并集大小union_size。

既然现在已经有了两个图对象之间的交集大小和并集大小了,那我们实际上就可以计算出两个图对象之间的杰卡德相似度了,下面是一段实现上面所描述的计算流程代码:

Public Function GraphSimilarity(x As NetworkGraph, y As NetworkGraph,
                                Optional cutoff# = 0.85,
                                Optional classEquivalent As Func(Of String, String, Double) = Nothing,
                                Optional topologyCos As Boolean = False) As Double

    ' JaccardIndex (intersects / union) -> highly similar / (dis-similar + highly similar)
    Dim similar%, top#, cos#

    If classEquivalent Is Nothing Then
        classEquivalent = Function(a, b) If(a <> b, 0, 1)
    End If

    ' 20191231
    ' X should always greater than Y in graph size
    ' or vertex count - similar may be negative value
    ' the negative value will cause union value smaller 
    ' than similar count, result an invalid cos similar
    ' value which is greater than 1
    If x.size.vertex > y.size.vertex Then
        Dim tmp = x

        x = y
        y = tmp
    End If

    For Each a As Node In x.vertex
        top = -99999

        For Each b As Node In y.vertex
            cos = Similarity.NodeSimilarity(a, b, classEquivalent, topologyCos)

            If cos > top Then
                top = cos
            End If
        Next

        If top >= cutoff Then
            similar += 1
        End If
    Next

    Dim union As Integer = (similar + (x.vertex.Count - similar) + (y.vertex.Count - similar))
    Dim jaccardIndex As Double = similar / union

    Return jaccardIndex
End Function
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 • 37 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. Required fields are marked *