The Bioinformatics Lab

Home People Publications Projects Courses Funding Contact Archive

SubMAP: Subnetwork Mappings in Alignment of Pathways

Abstract:
We consider the problem of aligning two metabolic pathways. Unlike traditional approaches, we do not restrict the alignment to one-to-one mappings between the molecules of the two input pathways. We allow aligning a single molecule of one pathway with a connected subnetwork of the other pathway. We follow the observation that in nature different organisms can perform the same or similar functions through different sets of reactions and molecules. The number and the topology of the molecules in these alternative sets often vary from one organism to another. In other words, given two metabolic pathways P and P' and an upper bound k (k is a positive integer) on the size of the alternative reaction set, we would like to find the mapping between P and P' that has the maximum similarity while mapping a molecule in one pathway with a connected subnetwork of size at most k from the other pathway. We transform this problem into an eigenvalue problem. The solution to this eigenvalue problem produces alternative mappings in the form of a weighted bipartite graph. We then convert this graph to a vertex weighted graph. The maximum weight independent subset of this new graph is the alignment that maximizes the alignment score while ensuring consistency. We call our algorithm SubMAP (Subnetwork Mappings in Alignment of Pathways). We evaluate its accuracy and performance on real datasets. Our experiments on demonstrate that SubMAP can identify biologically relevant mappings that are missed by traditional alignment methods and it is scalable. SubMAP can align pathways with around 50 reactions in less than a minute.

Keywords: Metabolic pathway alignment, Subnetwork mappings, Alternative subnetworks, Alternative Paths, Network alignment
Software:
Download the SubMAP software for aligning metabolic pathways with subnetwork mappings
People:

Publications:


Tamer Kahveci
Last modified: Mon May 3 17:01:54 EDT 2010