## The Bioinformatics Lab

#### 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