A New Tool for the Alignment of Metabolic Pathways

Ron Y. Pinter, Oleg Rokhlenko, Esti Yeger-Lotem, Michal Ziv-Ukelson

Dept. of Computer Science, Technion - Israel Institute of Technology, Haifa 32000, Israel

{fpinter, olegro, estiy, michalzg} @cs.technion.ac.il

Abstract

Several genome-scale efforts are underway to reconstruct metabolic networks for a variety of
organisms. As the resulting data accumulates, the need for analysis tools increases. A notable
requirement is a pathway alignment finder that enables both the detection of conserved
metabolic pathways among different species as well as divergent metabolic pathways within
a specie. When comparing two pathways, the tool should be powerful enough to take into
account both the pathway topology as well as the nodes’ labels (e.g. the enzymes they
denote), and allow flexibility by matching similar — rather than identical — pathways.
MetaPathwayHunter is a pathway alignment tool that, given a query pathway and a collection
of pathways, finds and reports all approximate occurrences of the query in the collection,
ranked by similarity and statistical significance. It is based on novel, efficient graph matching
algorithms that extend the functionality of known techniques. The program also supports a
visualization interface with which the alignment of two homologous pathways can be graphically
displayed.
We employed this tool to study the similarities and differences in the metabolic networks
of several organisms (as represented in highly curated databases that are available on the
World Wide Web). We reaffirmed that most known metabolic pathways common to bacteria
and yeast are conserved; furthermore, we present a few cases in which the comparison of
metabolic pathways between species exemplifies divergent and putative convergent evolution,
and within a specie — exemplifies divergent evolution. We conclude with a description of
several biologically meaningful meta-queries, demonstrating the power and flexibility of our
new tool in the analysis of metabolic pathways.