The Bioinformatics Lab

Home People Publications Projects Courses Funding Contact Archive

Alignment of Metabolic Pathways

Abstract:
Pathways show how different biochemical entities interact with each other to perform vital functions for the survival of organisms. Comparative analysis of pathways is crucial in identifying 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 by aligning the pathways reduces to graph isomorphism problem. However, for pathways with varying types of entities, such as metabolic pathways, alignment problem is more challenging. In order to simplify this problem, existing methods, often, reduces the metabolic pathways to graphs with restricted topologies and with only a single type of nodes. These kinds of abstractions, however, reduces the relevance of the alignment significantly as they cause losses in the information content. In this paper, we describe an algorithm to solve the pairwise alignment problem for metabolic pathways. One distinguishing feature of our method is that it aligns different types of entities, such as enzymes, reactions and compounds, without any abstraction in modeling. We pursue the intuition that both pairwise similarities of entities (homology) and the organization of their interactions (topology) are important 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 milliseconds.

Keywords: metabolic pathway alignment, alternative enzyme identification, phylogenetic reconstruction.
Software:
Download the software for pairwise alignment of metalic pathways
People:
Publications:
Tamer Kahveci
Last modified: Thu May 7 10:20:32 EDT 2009