Consistent Alignment of Metabolic Pathways without Abstraction

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.