• 文献检索
  • 文档翻译
  • 深度研究
  • 学术资讯
  • Suppr Zotero 插件Zotero 插件
  • 邀请有礼
  • 套餐&价格
  • 历史记录
应用&插件
Suppr Zotero 插件Zotero 插件浏览器插件Mac 客户端Windows 客户端微信小程序
定价
高级版会员购买积分包购买API积分包
服务
文献检索文档翻译深度研究API 文档MCP 服务
关于我们
关于 Suppr公司介绍联系我们用户协议隐私条款
关注我们

Suppr 超能文献

核心技术专利：CN118964589B侵权必究
粤ICP备2023148730 号-1Suppr @ 2026

文献检索

告别复杂PubMed语法，用中文像聊天一样搜索，搜遍4000万医学文献。AI智能推荐，让科研检索更轻松。

立即免费搜索

文件翻译

保留排版，准确专业，支持PDF/Word/PPT等文件格式，支持 12+语言互译。

免费翻译文档

深度研究

AI帮你快速写综述，25分钟生成高质量综述，智能提取关键信息，辅助科研写作。

立即免费体验

基于索引的子图匹配算法（ISMA）：使用优化搜索树在大型网络中快速枚举子图。

The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.

机构信息

Department of Information Technology, Ghent University, Ghent, Belgium.

出版信息

PLoS One. 2013 Apr 19;8(4):e61183. doi: 10.1371/journal.pone.0061183. Print 2013.

DOI:10.1371/journal.pone.0061183
PMID:23620730
原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC3631255/
Abstract

Subgraph matching algorithms are designed to find all instances of predefined subgraphs in a large graph or network and play an important role in the discovery and analysis of so-called network motifs, subgraph patterns which occur more often than expected by chance. We present the index-based subgraph matching algorithm (ISMA), a novel tree-based algorithm. ISMA realizes a speedup compared to existing algorithms by carefully selecting the order in which the nodes of a query subgraph are investigated. In order to achieve this, we developed a number of data structures and maximally exploited symmetry characteristics of the subgraph. We compared ISMA to a naive recursive tree-based algorithm and to a number of well-known subgraph matching algorithms. Our algorithm outperforms the other algorithms, especially on large networks and with large query subgraphs. An implementation of ISMA in Java is freely available at http://sourceforge.net/projects/isma/.

摘要

子图匹配算法旨在查找大型图或网络中所有预定义子图的实例，并在发现和分析所谓的网络基元（出现频率高于随机预期的子图模式）方面发挥重要作用。我们提出了基于索引的子图匹配算法（ISMA），这是一种新颖的基于树的算法。ISMA 通过仔细选择查询子图节点的调查顺序，与现有算法相比实现了加速。为了实现这一点，我们开发了许多数据结构，并最大限度地利用了子图的对称特性。我们将 ISMA 与一种简单的递归基于树的算法和一些著名的子图匹配算法进行了比较。我们的算法优于其他算法，尤其是在大型网络和大型查询子图上。ISMA 的 Java 实现可在 http://sourceforge.net/projects/isma/ 上免费获得。

https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/b7838f4455ee/pone.0061183.g011.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/63b712e62136/pone.0061183.g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/41279d555e81/pone.0061183.g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/29368b79fb11/pone.0061183.g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/2e44d208ab68/pone.0061183.g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/48f442771e23/pone.0061183.g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/16c20c8c8861/pone.0061183.g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/0af764cfed0f/pone.0061183.g007.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/ca251ced2ebe/pone.0061183.g008.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/d82495a99dae/pone.0061183.g009.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/ba4b45ccaebd/pone.0061183.g010.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/b7838f4455ee/pone.0061183.g011.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/63b712e62136/pone.0061183.g001.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/41279d555e81/pone.0061183.g002.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/29368b79fb11/pone.0061183.g003.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/2e44d208ab68/pone.0061183.g004.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/48f442771e23/pone.0061183.g005.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/16c20c8c8861/pone.0061183.g006.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/0af764cfed0f/pone.0061183.g007.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/ca251ced2ebe/pone.0061183.g008.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/d82495a99dae/pone.0061183.g009.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/ba4b45ccaebd/pone.0061183.g010.jpg
https://cdn.ncbi.nlm.nih.gov/pmc/blobs/bc3e/3631255/b7838f4455ee/pone.0061183.g011.jpg

相似文献

1
The index-based subgraph matching algorithm (ISMA): fast subgraph enumeration in large networks using optimized search trees.基于索引的子图匹配算法（ISMA）：使用优化搜索树在大型网络中快速枚举子图。
PLoS One. 2013 Apr 19;8(4):e61183. doi: 10.1371/journal.pone.0061183. Print 2013.
2
The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.基于索引的具有一般对称性的子图匹配算法（ISMAGS）：利用对称性实现更快的子图枚举。
PLoS One. 2014 May 30;9(5):e97896. doi: 10.1371/journal.pone.0097896. eCollection 2014.
3
Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs.用于估计子图浓度和检测网络基序的高效采样算法。
Bioinformatics. 2004 Jul 22;20(11):1746-58. doi: 10.1093/bioinformatics/bth163. Epub 2004 Mar 4.
4
A linear delay algorithm for enumerating all connected induced subgraphs.一种用于枚举所有连通诱导子图的线性延迟算法。
BMC Bioinformatics. 2019 Jun 20;20(Suppl 12):319. doi: 10.1186/s12859-019-2837-y.
5
Network subgraph-based approach for analyzing and comparing molecular networks.基于网络子图的分析和比较分子网络的方法。
PeerJ. 2022 May 3;10:e13137. doi: 10.7717/peerj.13137. eCollection 2022.
6
A subgraph isomorphism algorithm and its application to biochemical data.子图同构算法及其在生化数据中的应用。
BMC Bioinformatics. 2013;14 Suppl 7(Suppl 7):S13. doi: 10.1186/1471-2105-14-S7-S13. Epub 2013 Apr 22.
7
Sensible method for updating motif instances in an increased biological network.用于在扩展生物网络中更新基序实例的合理方法。
Methods. 2015 Jul 15;83:71-9. doi: 10.1016/j.ymeth.2015.04.007. Epub 2015 Apr 11.
8
Discovery of network motifs based on induced subgraphs using a dynamic expansion tree.基于动态扩展树的诱导子图网络基元发现。
Comput Biol Chem. 2021 Aug;93:107530. doi: 10.1016/j.compbiolchem.2021.107530. Epub 2021 Jun 11.
9
SING: subgraph search in non-homogeneous graphs.SING：非齐次图中的子图搜索。
BMC Bioinformatics. 2010 Feb 19;11:96. doi: 10.1186/1471-2105-11-96.
10
RMOD: a tool for regulatory motif detection in signaling network.RMOD：一种用于信号网络中调控基序检测的工具。
PLoS One. 2013 Jul 12;8(7):e68407. doi: 10.1371/journal.pone.0068407. Print 2013.

引用本文的文献

1
Generating random graphs with prescribed graphlet frequency bounds derived from probabilistic networks.生成具有从概率网络导出的规定图元频率界限的随机图。
PLoS One. 2025 Aug 26;20(8):e0328639. doi: 10.1371/journal.pone.0328639. eCollection 2025.
2
SUBATOMIC: a SUbgraph BAsed mulTi-OMIcs clustering framework to analyze integrated multi-edge networks.亚原子：一种基于子图的多组学聚类框架，用于分析集成的多边缘网络。
BMC Bioinformatics. 2022 Sep 5;23(1):363. doi: 10.1186/s12859-022-04908-3.
3
Edge-colored directed subgraph enumeration on the connectome.

本文引用的文献

1
Enrichment and aggregation of topological motifs are independent organizational principles of integrated interaction networks.拓扑基序的富集和聚集是整合相互作用网络的独立组织原则。
Mol Biosyst. 2011 Oct;7(10):2769-78. doi: 10.1039/c1mb05241a. Epub 2011 Aug 23.
2
CyClus3D: a Cytoscape plugin for clustering network motifs in integrated networks.CyClus3D：一个 Cytoscape 插件，用于在整合网络中聚类网络基元。
Bioinformatics. 2011 Jun 1;27(11):1587-8. doi: 10.1093/bioinformatics/btr182. Epub 2011 Apr 8.
3
A global protein kinase and phosphatase interaction network in yeast.
脑连接组上的带边有向子图枚举。
Sci Rep. 2022 Jul 5;12(1):11349. doi: 10.1038/s41598-022-15027-7.
4
Function, dynamics and evolution of network motif modules in integrated gene regulatory networks of worm and plant.网络基元模块在蠕虫和植物综合基因调控网络中的功能、动态和进化。
Nucleic Acids Res. 2018 Jul 27;46(13):6480-6503. doi: 10.1093/nar/gky468.
5
An Algorithm to Automatically Generate the Combinatorial Orbit Counting Equations.一种自动生成组合轨道计数方程的算法。
PLoS One. 2016 Jan 21;11(1):e0147078. doi: 10.1371/journal.pone.0147078. eCollection 2016.
6
The Index-based Subgraph Matching Algorithm with General Symmetries (ISMAGS): exploiting symmetry for faster subgraph enumeration.基于索引的具有一般对称性的子图匹配算法（ISMAGS）：利用对称性实现更快的子图枚举。
PLoS One. 2014 May 30;9(5):e97896. doi: 10.1371/journal.pone.0097896. eCollection 2014.
酵母中全局的蛋白激酶和磷酸酶相互作用网络。
Science. 2010 May 21;328(5981):1043-6. doi: 10.1126/science.1176495.
4
Complex systems and networks. Connections. Introduction.复杂系统与网络。连接。引言。
Science. 2009 Jul 24;325(5939):405. doi: 10.1126/science.325_405.
5
Functional organization of the S. cerevisiae phosphorylation network.酿酒酵母磷酸化网络的功能组织
Cell. 2009 Mar 6;136(5):952-63. doi: 10.1016/j.cell.2008.12.039.
6
STRING 8--a global view on proteins and their functional interactions in 630 organisms.STRING 8——关于630种生物中蛋白质及其功能相互作用的全局视图。
Nucleic Acids Res. 2009 Jan;37(Database issue):D412-6. doi: 10.1093/nar/gkn760. Epub 2008 Oct 21.
7
InParanoid 6: eukaryotic ortholog clusters with inparalogs.InParanoid 6：含旁系同源基因的真核直系同源簇
Nucleic Acids Res. 2008 Jan;36(Database issue):D263-6. doi: 10.1093/nar/gkm1020. Epub 2007 Nov 30.
8
Network motifs: theory and experimental approaches.网络基序：理论与实验方法
Nat Rev Genet. 2007 Jun;8(6):450-61. doi: 10.1038/nrg2102.
9
Getting connected: analysis and principles of biological networks.建立联系：生物网络的分析与原理
Genes Dev. 2007 May 1;21(9):1010-24. doi: 10.1101/gad.1528707.
10
SAGA: a subgraph matching tool for biological graphs.SAGA：一种用于生物图谱的子图匹配工具。
Bioinformatics. 2007 Jan 15;23(2):232-9. doi: 10.1093/bioinformatics/btl571. Epub 2006 Nov 16.