101 %% \fntext[label2]{} |
101 %% \fntext[label2]{} |
102 %% \cortext[cor1]{} |
102 %% \cortext[cor1]{} |
103 %% \address{Address\fnref{label3}} |
103 %% \address{Address\fnref{label3}} |
104 %% \fntext[label3]{} |
104 %% \fntext[label3]{} |
105 |
105 |
106 \title{Improved Algorithms for Matching Biological Graphs} |
106 \title{VF2++ --- An Improved Subgraph Isomorphism Algorithm} |
107 |
107 |
108 %% use optional labels to link authors explicitly to addresses: |
108 %% use optional labels to link authors explicitly to addresses: |
109 %% \author[label1,label2]{} |
109 %% \author[label1,label2]{} |
110 %% \address[label1]{} |
110 %% \address[label1]{} |
111 %% \address[label2]{} |
111 %% \address[label2]{} |
112 |
112 |
113 \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi} |
113 \author[egres,elte]{Alp{\'a}r J{\"u}ttner} |
114 |
114 \ead{alpar@cs.elte.hu} |
115 \address{Dept of Operations Research, ELTE} |
115 \author[elte]{P{\'e}ter Madarasi} |
|
116 \ead{madarasip@caesar.elte.hu} |
|
117 \address[egres]{MTA-ELTE Egerv{\'a}ry Research Group, Budapest, Hungary.} |
|
118 \address[elte]{Department of Operations Research, E{\"o}tv{\"o}s Lor{\'a}nd University, Budapest, Hungary.} |
116 |
119 |
117 \begin{abstract} |
120 \begin{abstract} |
118 Subgraph isomorphism is a well-known NP-Complete problem, while its |
121 |
119 special case, the graph isomorphism problem is one of the few problems |
122 This paper presents a largely improved version of the VF2 algorithm |
120 in NP neither known to be in P nor NP-Complete. Their appearance in |
123 for the \emph{Subgraph Isomorphism Problem}. The improvements are |
121 many fields of application such as pattern analysis, computer vision |
124 twofold. Firstly, it is based on a new approach for determining the |
122 questions and the analysis of chemical and biological systems has |
125 matching order of the nodes, and secondly, more efficient - |
123 fostered the design of various algorithms for handling special graph |
126 nevertheless easier to compute - cutting rules significantly |
124 structures. |
127 reducing the search space are applied. |
125 |
128 |
126 This paper presents VF2++, a new algorithm based on the original VF2, |
129 In addition to the usual subgraph isomorphism, the paper also |
127 which runs significantly faster on most test cases and performs |
130 presents specialized versions for the \emph{Induced Subgraph |
128 especially well on special graph classes stemming from biological |
131 Isomorphism} and for the \emph{Graph Isomorphism Problems}. |
129 questions. VF2++ handles graphs of thousands of nodes in practically |
132 |
130 near linear time including preprocessing. Not only is it an improved |
133 Finally, an extensive experimental evaluation is provided using a |
131 version of VF2, but in fact, it is by far the fastest existing |
134 wide range of inputs, including both real life biological and |
132 algorithm especially on biological graphs. |
135 chemical datasets and standard randomly generated graph series. The |
133 |
136 results show major and consistent running time improvements over the |
134 The reason for VF2++' superiority over VF2 is twofold. Firstly, taking |
137 other known methods. |
135 into account the structure and the node labeling of the graph, VF2++ |
138 |
136 determines a state order in which most of the unfruitful branches of |
139 The C++ implementations of the algorithms are available open source as |
137 the search space can be pruned immediately. Secondly, introducing more |
140 the part of the LEMON graph and network optimization library. |
138 efficient - nevertheless still easier to compute - cutting rules |
141 |
139 reduces the chance of going astray even further. |
|
140 |
|
141 In addition to the usual subgraph isomorphism, specialized versions |
|
142 for induced subgraph isomorphism and for graph isomorphism are |
|
143 presented. VF2++ has gained a runtime improvement of one order of |
|
144 magnitude respecting induced subgraph isomorphism and a better |
|
145 asymptotical behaviour in the case of graph isomorphism problem. |
|
146 |
|
147 After having provided the description of VF2++, in order to evaluate |
|
148 its effectiveness, an extensive comparison to the contemporary other |
|
149 algorithms is shown, using a wide range of inputs, including both real |
|
150 life biological and chemical datasets and standard randomly generated |
|
151 graph series. |
|
152 |
|
153 The work was motivated and sponsored by QuantumBio Inc., and all the |
|
154 developed algorithms are available as the part of the open source |
|
155 LEMON graph and network optimization library |
|
156 (http://lemon.cs.elte.hu). |
|
157 \end{abstract} |
142 \end{abstract} |
158 |
143 |
159 \begin{keyword} |
144 \begin{keyword} |
|
145 Computational Biology, Subgraph Isomorphism Problem |
160 %% keywords here, in the form: keyword \sep keyword |
146 %% keywords here, in the form: keyword \sep keyword |
161 |
147 |
162 %% PACS codes here, in the form: \PACS code \sep code |
148 %% PACS codes here, in the form: \PACS code \sep code |
163 |
149 |
164 %% MSC codes here, in the form: \MSC code \sep code |
150 %% MSC codes here, in the form: \MSC code \sep code |