Consistent alignment of metabolic pathways without abstraction

Ferhat Ay*, Tamer Kahveci, Valerie de Crécy-Lagard

Department of Computer Science and Engineering, University of Florida, Gainesville, FL 32611, USA. fay@cise.ufl.edu

Proc LSS Comput Syst Bioinform Conf. August, 2008. Vol. 7, p. 237-248. Full-Text PDF

*To whom correspondence should be addressed.

Pathways show how different biochemical entities interact with each other to perform vital functions for the survival of organisms. Similarities between pathways indicate functional similarities that are difficult to identify by comparing the individual entities that make up those pathways. When interacting entities are of single type, the problem of identifying similarities reduces to graph isomorphism problem. However, for pathways with varying types of entities, such as metabolic pathways, alignment problem is more challenging. Existing methods, often, address the metabolic pathway alignment problem by ignoring all the entities except for one type. This kind of abstraction reduces the relevance of the alignment significantly as it causes losses in the information content. In this paper, we develop a method to solve the pairwise alignment problem for metabolic pathways. One distinguishing feature of our method is that it aligns reactions, compounds and enzymes without abstraction of pathways. We pursue the intuition that both pairwise similarities of entities (homology) and their organization (topology) are crucial for metabolic pathway alignment. In our algorithm, we account for both by creating an eigenvalue problem for each entity type. We enforce the consistency by considering the reachability sets of the aligned entities. Our experiments show that, our method finds biologically and statistically significant alignments in the order of seconds for pathways with ~ 100 entities. Keywords: metabolic pathway alignment, metabolic reconstruction, alternative enzyme identification