An inexact graph matching technique using genetic algorithms and its application in systems biology

Abstract

Graph is a versatile datastructure for representing and processing relational information. Inexact graph matching is the process of determining the best possible match of one graph against another where there is not much correspondence between the graphs. The inexact graph matching problem is NP-hard. This paper proposes a genetic algorithm based technique to find the best possible match between two graphs. The technique is aided by loosely coupled similarity estimation metrics to perform the matching. The technique has been applied to a real world inexact graph matching problem and the results have been provided.