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 species. 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 a novel,
efficient graph matching algorithm (to be described in this
presentation) that extends 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 retrieved 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 discovered a few intriguing
evolutionary relations between pathways by aligning metabolic
pathways between species and within a species. 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.

Joint work with Oleg Rokhlenko, Esti Yeger-Lotem, and Michal
Ziv-Ukelson.