Graph animals, subgraph sampling, and motif search in large networks.
Graph animals, subgraph sampling, and motif search in large networks.
复制标题
大型网络中的图动物、子图采样和主题搜索。
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Paczuski
中科院分区：
文献类型：
--
作者：
Kim Baskerville;P. Grassberger;M. Paczuski
我们将格子动物（规则格子上的连接簇）的采样算法概括为“图动物”（即任意网络中的连接子图）的蒙特卡罗算法。与[N. Kashtan et al., Bioinformatics 20, 1746 (2004)]，它提供了加权样本，但权重的计算要快得多（子图大小呈线性，而不是超指数）。这允许从任意大的网络中以非常高的统计数据对具有多达十个或更多节点的子图进行采样。将其与快速分类同构图的启发式算法结合使用，我们展示了使用串联亲和纯化 (TAP) 方法获得的两种蛋白质相互作用网络的结果：一种是大肠杆菌，具有 230 个节点和 695 个链接，另一种是酵母（酿酒酵母），其节点和链接数量大约是其十倍。我们发现，在这两种情况下，当空模型是具有固定度数序列的网络集合时，大多数连接的子图都是强基序（Z 分数 >10）或反基序（Z 分数 <-10）。这两个网络之间出现了很大的差异，大肠杆菌中的主导基序是（几乎）二分图，并且具有许多连接到相同邻居的节点对，而酵母中的主导基序倾向于完整性或包含大派系。我们还探索了许多不依赖于 Z 分数测量或与空模型比较的方法。例如，我们讨论了酵母中 26S 蛋白酶体等特定复合物的影响，其中少数复合物主导了具有大 k 的 k 核心，并对具有 6-8 个节点的最强基序具有决定性影响。我们还展示了计数与排名的 Zipf 图。与包含不连续子图的情况相反，它们显示出不属于幂律的广泛分布。
We generalize a sampling algorithm for lattice animals (connected clusters on a regular lattice) to a Monte Carlo algorithm for "graph animals," i.e., connected subgraphs in arbitrary networks. As with the algorithm in [N. Kashtan et al., Bioinformatics 20, 1746 (2004)], it provides a weighted sample, but the computation of the weights is much faster (linear in the size of subgraphs, instead of superexponential). This allows subgraphs with up to ten or more nodes to be sampled with very high statistics, from arbitrarily large networks. Using this together with a heuristic algorithm for rapidly classifying isomorphic graphs, we present results for two protein interaction networks obtained using the tandem affinity purification (TAP) method: one of Escherichia coli with 230 nodes and 695 links, and one for yeast (Saccharomyces cerevisiae) with roughly ten times more nodes and links. We find in both cases that most connected subgraphs are strong motifs (Z scores >10) or antimotifs (Z scores <-10) when the null model is the ensemble of networks with fixed degree sequence. Strong differences appear between the two networks, with dominant motifs in E. coli being (nearly) bipartite graphs and having many pairs of nodes that connect to the same neighbors, while dominant motifs in yeast tend towards completeness or contain large cliques. We also explore a number of methods that do not rely on measurements of Z scores or comparisons with null models. For instance, we discuss the influence of specific complexes like the 26S proteasome in yeast, where a small number of complexes dominate the k cores with large k and have a decisive effect on the strongest motifs with 6-8 nodes. We also present Zipf plots of counts versus rank. They show broad distributions that are not power laws, in contrast to the case when disconnected subgraphs are included.
DOI：
10.1073/pnas.0409515102
发表时间：
2005-03-01
影响因子：
11.1
作者：
Middendorf, M;Ziv, E;Wiggins, CH
通讯作者：
Wiggins, CH
DOI：
10.1103/physreve.71.046117
发表时间：
2004-11
期刊：
Physical review. E, Statistical, nonlinear, and soft matter physics
影响因子：
--
作者：
E. Ziv;Manuel Middendorf;C. Wiggins
通讯作者：
E. Ziv;Manuel Middendorf;C. Wiggins