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.
- gunzip pathmatch.tar.gz
- tar xvf pathmatch.tar
- cd pathmatch
- ./install
Examples
- With the mating-pheromone response pathway
| Ste18p | Ste4p | Gpa1p | Ste11p | Ste5p |
Ste7p | Fus3p | Dig1p | Ste12p | Mat1ap |
from the protein interaction network of S.cervisiae as query path,
PathMatch finds the following top scoring similar paths from the protein
interaction network of C.elegans (represented as path alignments):
| 1. | query | Ste18p | — |
Ste4p | Gpa1p | Ste11p | Ste15p | Ste7p |
— | Fus3p | Dig1p | Ste12p | Mat1ap |
| | | | | | | |
| | | | | | | | | | | | |
| |
| result | ifc-2 | dyb-1 |
unc-15 | T04H1.2 | mig-15 | ttx-1 | mig-15 |
csn-5 | mpk-1 | Y42H9AR.1 | gei-4 | K09B11.9 |
| 2. | query | Ste18p | — |
Ste4p | Gpa1p | Ste11p | Ste15p | Ste7p |
— | Fus3p | Dig1p | Ste12p | Mat1ap |
| | | | | | | |
| | | | | | | | | | | | | | |
| result | ifc-2 | dyb-1 |
unc-15 | T04H1.2 | mig-15 | dpy-14 | mig-15 |
csn-5 | mpk-1 | Y42H9AR.1 | gei-4 | K09B11.9 |
| 3. | query | Ste18p | — |
Ste4p | — | Gpa1p | Ste11p | Ste15p |
Ste7p | — | Fus3p | Dig1p | Ste12p |
Mat1ap |
| | | | | | | |
| | | | | | | | | | | | |
| | | |
| result | Y38F2AR.7 | akt-2 |
T28C6.7 | mig-15 | hsp-1 | mig-15 | ttx-1 |
mig-15 | csn-5 | mpk-1 | Y42H9AR.1 | gei-4 |
K09B11.9 |
- With the metabolic pathway
| Propionate | 6.2.1.17 | Propionyl-CoA | 2.3.3.5 |
2-Methylcitrate | 4.2.1.79 | cis-2-Methylaconitate |
4.2.1.3 | Methylisocitrate | 4.1.3.30 | Succinate |
from the propanoate metabolism, PathMatch finds the following top scoring
similar paths from a combined network of glycolysis, gluconeogenesis, the
citrate cycle and the glyoxylate metabolism in E.coli (represented
as path alignments):
| 1. | query | Propionate | 6.2.1.17 |
Propionyl-CoA | 2.3.3.5 | 2-Methylcitrate | 4.2.1.79 |
cis-2-Methylaconitate | 4.2.1.3 | Methylisocitrate |
4.1.3.30 | Succinate |
| | | | | | | | | |
| | | | | | | | | | | | | |
| result | Acetate | 6.2.1.1 |
Acetyl-CoA | 2.3.3.1 | Citrate | 4.2.1.3 |
cis-Aconitate | 4.2.1.3 | Isocitrate | 4.1.3.1 |
Succinate |
| 2. | query | Propionate | 6.2.1.17 |
Propionyl-CoA | 2.3.3.5 | 2-Methylcitrate | 4.2.1.79 |
cis-2-Methylaconitate | 4.2.1.3 | Methylisocitrate |
4.1.3.30 | Succinate |
| | | | | | | | | |
| | | | | | | | | | | | | |
| result | Acetate | 6.2.1.1 |
Acetyl-CoA | 2.3.3.1 | Citrate | 4.2.1.3 |
Isocitrate | 4.2.1.3 | Citrate | 4.1.3.6 |
Oxaloacetate |
| 3. | query | Propionate | 6.2.1.17 |
Propionyl-CoA | 2.3.3.5 | 2-Methylcitrate | 4.2.1.79 |
cis-2-Methylaconitate | 4.2.1.3 | Methylisocitrate |
4.1.3.30 | Succinate |
| | | | | | | | | |
| | | | | | | | | | | | | |
| result | Acetate | 6.2.1.1 |
Acetyl-CoA | 2.3.3.1 | Citrate | 4.2.1.3 |
cis-Aconitate | 4.2.1.3 | Citrate | 4.1.3.6 |
Oxaloacetate |
Reference
Yang Q. and Sze S.-H. (2007)
Path
matching and graph matching in biological
networks. Journal of Computational Biology, 14, 56-67.