71 %% \fntext[label2]{} |
71 %% \fntext[label2]{} |
72 %% \cortext[cor1]{} |
72 %% \cortext[cor1]{} |
73 %% \address{Address\fnref{label3}} |
73 %% \address{Address\fnref{label3}} |
74 %% \fntext[label3]{} |
74 %% \fntext[label3]{} |
75 |
75 |
76 \title{} |
76 \title{Improved Algorithms for Matching Biological Graphs} |
77 |
77 |
78 %% use optional labels to link authors explicitly to addresses: |
78 %% use optional labels to link authors explicitly to addresses: |
79 %% \author[label1,label2]{} |
79 %% \author[label1,label2]{} |
80 %% \address[label1]{} |
80 %% \address[label1]{} |
81 %% \address[label2]{} |
81 %% \address[label2]{} |
82 |
82 |
83 \author{} |
83 \author{Alp{\'a}r J{\"u}ttner and P{\'e}ter Madarasi} |
84 |
84 |
85 \address{} |
85 \address{Dept of Operations Research, ELTE} |
86 |
86 |
87 \begin{abstract} |
87 \begin{abstract} |
88 %% Text of abstract |
88 Subgraph isomorphism is a well-known NP-Complete problem, while its |
|
89 special case, the graph isomorphism problem is one of the few problems |
|
90 in NP neither known to be in P nor NP-Complete. Their appearance in |
|
91 many fields of application such as pattern analysis, computer vision |
|
92 questions and the analysis of chemical and biological systems has |
|
93 fostered the design of various algorithms for handling special graph |
|
94 structures. |
89 |
95 |
|
96 The idea of using state space representation and checking some |
|
97 conditions in each state to prune the search tree has made the VF2 |
|
98 algorithm one of the state of the art graph matching algorithms for |
|
99 more than a decade. Recently, biological questions of ever increasing |
|
100 importance have required more efficient, specialized algorithms. |
|
101 |
|
102 This paper presents VF2++, a new algorithm based on the original VF2, |
|
103 which runs significantly faster on most test cases and performs |
|
104 especially well on special graph classes stemming from biological |
|
105 questions. VF2++ handles graphs of thousands of nodes in practically |
|
106 near linear time including preprocessing. Not only is it an improved |
|
107 version of VF2, but in fact, it is by far the fastest existing |
|
108 algorithm regarding biological graphs. |
|
109 |
|
110 The reason for VF2++' superiority over VF2 is twofold. Firstly, taking |
|
111 into account the structure and the node labeling of the graph, VF2++ |
|
112 determines a state order in which most of the unfruitful branches of |
|
113 the search space can be pruned immediately. Secondly, introducing more |
|
114 efficient - nevertheless still easier to compute - cutting rules |
|
115 reduces the chance of going astray even further. |
|
116 |
|
117 In addition to the usual subgraph isomorphism, specialized versions |
|
118 for induced subgraph isomorphism and for graph isomorphism are |
|
119 presented. VF2++ has gained a runtime improvement of one order of |
|
120 magnitude respecting induced subgraph isomorphism and a better |
|
121 asymptotical behaviour in the case of graph isomorphism problem. |
|
122 |
|
123 After having provided the description of VF2++, in order to evaluate |
|
124 its effectiveness, an extensive comparison to the contemporary other |
|
125 algorithms is shown, using a wide range of inputs, including both real |
|
126 life biological and chemical datasets and standard randomly generated |
|
127 graph series. |
|
128 |
|
129 The work was motivated and sponsored by QuantumBio Inc., and all the |
|
130 developed algorithms are available as the part of the open source |
|
131 LEMON graph and network optimization library |
|
132 (http://lemon.cs.elte.hu). |
90 \end{abstract} |
133 \end{abstract} |
91 |
134 |
92 \begin{keyword} |
135 \begin{keyword} |
93 %% keywords here, in the form: keyword \sep keyword |
136 %% keywords here, in the form: keyword \sep keyword |
94 |
137 |