A subgraph isomorphism algorithm and its application to biochemical data.
A subgraph isomorphism algorithm and its application to biochemical data.
复制标题
DOI：
10.1186/1471-2105-14-s7-s13
复制
发表时间：
2013
影响因子：
3
通讯作者：
Ferro A
中科院分区：
文献类型：
--
作者：
Bonnici V;Giugno R;Pulvirenti A;Shasha D;Ferro A
图形可以在分子、蛋白质或物种水平上表示生物网络。一个重要的查询是找到模式图与目标图的所有匹配。实现这一点本身就很困难（np完全），启发式算法对该问题的效率可能取决于输入图。现有算法的共同目标是尽早消除不成功的映射，并尽可能降低成本。本文提出了一种新的子图同构算法，该算法采用一种搜索策略，在不使用任何复杂的剪枝规则或域约简过程的情况下显著减小了搜索空间。我们将我们的方法与最新和最有效的子图同构算法（VFlib， LAD和我们的c++实现FocusSearch，最初分布在Modula2中）在合成，分子和交互网络数据上进行了比较。与其他优秀的方法相比，我们的方法显著减少了运行时间，并且随着内存需求的增加，我们的算法也可以很好地扩展。子图同构算法在生化工具中被广泛使用。我们的分析给出了子图同构的不同软件方法的全面比较，突出了它们的优缺点。这将有助于研究人员根据不同的应用在不同的方法之间做出合理的选择。我们还发布了一个开源包，包括我们的系统和我们自己的FocusSearch c++实现以及所有使用的数据集（http://ferrolab.dmi.unict.it/ri.html）。在未来的工作中，我们的发现可能会扩展到近似子图同构算法。
Graphs can represent biological networks at the molecular, protein, or species level. An important query is to find all matches of a pattern graph to a target graph. Accomplishing this is inherently difficult (NP-complete) and the efficiency of heuristic algorithms for the problem may depend upon the input graphs. The common aim of existing algorithms is to eliminate unsuccessful mappings as early as and as inexpensively as possible. We propose a new subgraph isomorphism algorithm which applies a search strategy to significantly reduce the search space without using any complex pruning rules or domain reduction procedures. We compare our method with the most recent and efficient subgraph isomorphism algorithms (VFlib, LAD, and our C++ implementation of FocusSearch which was originally distributed in Modula2) on synthetic, molecules, and interaction networks data. We show a significant reduction in the running time of our approach compared with these other excellent methods and show that our algorithm scales well as memory demands increase. Subgraph isomorphism algorithms are intensively used by biochemical tools. Our analysis gives a comprehensive comparison of different software approaches to subgraph isomorphism highlighting their weaknesses and strengths. This will help researchers make a rational choice among methods depending on their application. We also distribute an open-source package including our system and our own C++ implementation of FocusSearch together with all the used datasets (http://ferrolab.dmi.unict.it/ri.html). In future work, our findings may be extended to approximate subgraph isomorphism algorithms.