Pathways show how different biochemical entities, such as
proteins, interact with each other to perform functions that are
vital for the survival of organisms. Similarities between pathways
indicate important functional similarities that are hard to
identify by comparing the individual entities. When interacting
entities are of single type, the problem of identifying
similarities is, usually, solved similar to graph isomorphism
problem. However, for pathways with varying types of entities
alignment problem is more challenging. Examples include metabolic
pathways since in this case interactions involve compounds,
enzymes, and reactions. Existing methods, often, try to address
metabolic pathway alignment problem by ignoring all the entities
except for one type. This kind of abstraction, however, reduces
the relevance of the alignment significantly as it can cause
massive losses in the information content.
We consider the pairwise alignment problem for metabolic pathways.
One distinguishing feature of our method is that it aligns
reactions, compounds and enzymes without any abstraction of
pathways. We pursue the intuition that both pairwise similarities
of entities and the similarities of their neighborhood are crucial
in aligning these entities. Hence, we account for the effect of
pairwise similarities (homology) and the effect of organization of
pathways (topology) in our algorithm. We do this by creating an
eigenvalue problem for each entity type. We enforce the
consistency of the alignment by considering the reachability sets
of the aligned entities. Our experiments show that, our method
finds biologically and statistically significant alignments in
less than a second for pathways with ~100 entities.