perl - 计算图中子图的出现次数

Question

我有一个 3 维数据集，它描述了可以用图表表示的基因相互作用。数据集样本为:

a + b  
b + c  
c - f  
b - d  
a + c  
f + g  
g + h  
f + h  

'+'表示左侧的基因正向调节右侧的基因。在这些数据中，我想计算一个基因(例如，x)正向调节另一个基因(例如，y)，y 反过来正向调节另一个基因(例如，z)的子图。此外，z也受到x的正向调节。上图中有两种这样的情况。我想最好使用 awk 来执行此搜索，但任何脚本语言都可以。对于这个过于具体的问题，我深表歉意，并提前感谢您的帮助。

Answer 1

注意:请参阅下面有关 Graphviz 的信息。

这应该给你一个起点:

编辑:这一版本处理由多个字符描述的基因。

awk '
    BEGIN { regdelim = "|" }
    {
        delim=""
        if ($2 == "+") {
            if (plus[$1]) delim=regdelim
            plus[$1]=plus[$1] delim $3
        }
        else
            if ($2 == "-") {
            if (minus[$1]) delim=regdelim
                minus[$1]=minus[$1] delim $3
            }
    }
    END {
        for (root in plus) {
            split(plus[root],regs,regdelim)
            for (reg in regs) {
                if (plus[regs[reg]] && plus[root] ~ plus[regs[reg]]) {
                    print "Match: ", root, "+", regs[reg], "+", plus[regs[reg]]
                }
            }
        }
    }
' inputfile

在 BEGIN 子句中，将 regdelim 设置为数据中未出现的字符。

我省略了负数据的处理代码。

输出:

Match:  a + b + c
Match:  f + g + h

编辑2:

下面的版本允许您搜索任意组合。它概括了原始版本中使用的技术，因此不需要重复代码。它还修复了其他一些错误限制。

#!/bin/bash
# written by Dennis Williamson - 2010-11-12
# for http://stackoverflow.com/questions/4161001/counting-the-occurrence-of-a-sub-graph-in-a-graph
# A (AB) B, A (AC) C, B (BC) C - where "(XY)" represents a + or a - 
# provided by the positional parameters $1, $2 and $3
# $4 carries the data file name and is referenced at the end of the script
awk -v AB=$1 -v AC=$2 -v BC=$3 '
    BEGIN { regdelim = "|" }
    {
        if ($2 == AB) {
            if (regAB[$1]) delim=regdelim; else delim=""
            regAB[$1]=regAB[$1] delim $3
        }
        if ($2 == AC) {
            if (regAC[$1]) delim=regdelim; else delim=""
            regAC[$1]=regAC[$1] delim $3
        }
        if ($2 == BC) {
            if (regBC[$1]) delim=regdelim; else delim=""
            regBC[$1]=regBC[$1] delim $3
        }
    }
    END {
        for (root in regAB) {
            split(regAB[root],ABarray,regdelim)
            for (ABindex in ABarray) {
                split(regAC[root],ACarray,regdelim)
                for (ACindex in ACarray) {
                    split(regBC[ABarray[ABindex]],BCarray,regdelim)
                    for (BCindex in BCarray) {
                        if (ACarray[ACindex] == BCarray[BCindex]) {
                            print "    Match:", root, AB, ABarray[ABindex] ",", root, AC, ACarray[ACindex] ",", ABarray[ABindex], BC, BCarray[BCindex]
                        }
                    }
                }
            }
        }
    }
' "$4"

可以这样调用它来进行详尽的搜索:

for ab in + -; do for ac in + -; do for bc in + -; do echo "Searching: $ab$ac$bc"; ./searchgraph $ab $ac $bc inputfile; done; done; done

对于此数据:

a - e
a + b
b + c
c - f
m - n
b - d
a + c
b - e
l - n
f + g
b + i
g + h
l + m
f + h
a + i
a - j
k - j
a - k

调用新版本脚本的 shell 循环的输出如下所示:

Searching: +++
    Match: a + b, a + c, b + c
    Match: a + b, a + i, b + i
    Match: f + g, f + h, g + h
Searching: ++-
Searching: +-+
Searching: +--
    Match: l + m, l - n, m - n
    Match: a + b, a - e, b - e
Searching: -++
Searching: -+-
Searching: --+
Searching: ---
    Match: a - k, a - j, k - j

编辑3:

图形可视化

另一种方法是使用 Graphviz 。 DOT language可以描述图形和 gvpr ，这是一种“类似 AWK”¹ 编程语言，可以分析和操作 DOT 文件。

鉴于输入数据的格式如问题所示，您可以使用以下 AWK 程序将其转换为 DOT:

#!/usr/bin/awk -f
BEGIN {
    print "digraph G {"
    print "    size=\"5,5\""
    print "    ratio=.85"
    print "    node [fontsize=24 color=blue penwidth=3]"
    print "    edge [fontsize=18 labeldistance=5 labelangle=-8 minlen=2 penwidth=3]"
    print "    {rank=same; f l}"
    m  = "-"    # ASCII minus/hyphen as in the source data
    um = "−"    # u2212 minus: − which looks better on the output graphic
    p  = "+"
}

{
    if ($2 == m) { $2 = um; c = lbf = "red"; arr=" arrowhead = empty" }
    if ($2 == p) { c = lbf = "green3"; arr="" }
    print "    " $1, "->", $3, "[taillabel = \"" $2 "\" color = \"" c "\" labelfontcolor = \"" lbf "\"" arr "]"
}
END {
    print "}"
}

运行的命令如下所示:

$ ./dat2dot data.dat > data.dot

然后您可以使用以下方法创建上面的图形:

$ dot -Tpng -o data.png data.dot

我在这个答案中使用了上面给出的扩展数据。

要对指定的子图类型进行详尽搜索，您可以使用以下 gvpr 程序:

BEGIN {
    edge_t AB, BC, AC;
}

E {
    AB = $;
    BC = fstedge(AB.head);
    while (BC && BC.head.name != AB.head.name) {
        AC = isEdge(AB.tail,BC.head,"");
        if (AC) {
            printf("%s %s %s, ", AB.tail.name, AB.taillabel, AB.head.name);
            printf("%s %s %s, ", AC.tail.name, AC.taillabel, AC.head.name);
            printf("%s %s %s\n", BC.tail.name, BC.taillabel, BC.head.name);
        }
        BC = nxtedge(BC, AB.head);
    }
}

要运行它，您可以使用:

$ gvpr -f groups.g data.dot | sort -k 2,2 -k 5,5 -k 8,8

输出将与上面的 AWK/shell 组合的输出类似(在“编辑 2”下):

a + b, a + c, b + c
a + b, a + i, b + i
f + g, f + h, g + h
a + b, a − e, b − e
l + m, l − n, m − n
a − k, a − j, k − j

---

¹ _{宽松地说。}