GraphMatch Software

Given a query graph, GraphMatch finds subgraphs that are most similar to the query graph in a network by an exact algorithm that enumerates all connected induced subgraphs of the query graph and finds all corresponding valid solutions.

Installing GraphMatch

The GraphMatch 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 following steps will create a directory called graphmatch. Detailed usage of GraphMatch is provided in a README file that is also included with the download.

• gunzip graphmatch.tar.gz
• tar xvf graphmatch.tar
• cd graphmatch
• ./install

Examples

• The following shows the top result from querying the protein interaction network of C. elegans with a functional module of the mating-pheromone response pathway (corresponding edges between the query and the result are shown on the same line, with — denoting no indel and --- denoting one indel on an edge in the result):

  Hsc82p	—	Ste11p	daf-21	---	mig-15
  Hsc82p	—	Bud6p
  Ste11p	—	Bud6p
  Ste11p	—	Ste5p
  Ste11p	—	Spa2p	mig-15	---	zyg-1
  Ste11p	—	Sph1p
  Ste11p	—	Fus3p	mig-15	---	mpk-1
  Ste11p	—	Kss1p	mig-15	---	mpk-1
  Bud6p	—	Spa2p
  Ste5p	—	Ste7p
  Ste5p	—	Fus3p
  Ste5p	—	Kss1p
  Spa2p	—	Ste7p	zyg-1	---	mig-15
  Spa2p	—	Mkk1p	zyg-1	---	sek-1
  Spa2p	—	Mkk2p	zyg-1	---	sek-1
  Ste7p	—	Sph1p
  Ste7p	—	Fus3p	mig-15	---	mpk-1
  Ste7p	—	Kss1p	mig-15	---	mpk-1
  Sph1p	—	Mkk1p
  Sph1p	—	Mkk2p
  Fus3p	—	Mpt5p	mpk-1	---	C52B11.2
  Fus3p	—	Dig1p	mpk-1	—	4I879
  Fus3p	—	Dig2p	mpk-1	---	vab-3
  Kss1p	—	Mpt5p	mpk-1	---	C52B11.2
  Kss1p	—	Dig1p	mpk-1	—	4I879
  Kss1p	—	Dig2p	mpk-1	---	vab-3
  Dig1p	—	Dig2p	4I879	---	vab-3
  query			result

• The following shows the top result from querying a combined metabolic network of glycolysis, gluconeogenesis, the citrate cycle and the glyoxylate metabolism in E. coli with a tree-like network containing part of the α-aminoadipic pathway in T. thermophilus (corresponding edges between the query and the result are shown on the same line):

  2-Oxoglutarate	—	2.3.3.14	Oxaloacetate	—	2.3.3.1
  Acetyl-CoA	—	2.3.3.14	Acetyl-CoA	—	2.3.3.1
  2.3.3.14	—	Homo-Citrate	2.3.3.1	—	Citrate
  2.3.3.14	—	CoA	2.3.3.1	—	CoA
  Homo-Citrate	—	4.2.1.36	Citrate	—	4.2.1.3
  4.2.1.36	—	Homo-cis-Aconitate	4.2.1.3	—	cis-Aconitate
  Homo-cis-Aconitate	—	4.2.1.36	cis-Aconitate	—	4.2.1.3
  4.2.1.36	—	Homo-Isocitrate	4.2.1.3	—	Isocitrate
  Homo-Isocitrate	—	1.1.1.87	Isocitrate	—	1.1.1.41
  NAD	—	1.1.1.87	NADP	—	1.1.1.41
  1.1.1.87	—	2-Oxoadipate	1.1.1.41	—	2-Oxoglutarate
  1.1.1.87	—	NADH	1.1.1.41	—	NADPH
  query			result

Reference

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