PathMatch Software

Given a query path, PathMatch finds paths that are most similar to the query graph in a network by reducing the problem to finding a longest weighted path in a directed acyclic graph, which can be solved in polynomial time.

Installing PathMatch

The PathMatch source code, including sample input and output files and network files for a few protein interaction networks from the DIP database and a few metabolic networks from the KEGG and the EcoCyc databases, can be compiled under the Unix/Linux/Windows(Cygwin) environment. The source code includes a modified version of an implementation of the Eppstein's algorithm for finding k shortest paths by Jiménez and Marzal. The following steps will create a directory called pathmatch. Detailed usage of PathMatch is provided in a README file that is also included with the download.



Yang Q. and Sze S.-H. (2007) Path matching and graph matching in biological networks. Journal of Computational Biology, 14, 56-67.