We consider the problem of aligning two metabolic pathways. Unlike
traditional pathway alignment problems, we do not restrict the
alignment to one-to-one mapping 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. This problem is motivated
by the fact that metabolisms of different organisms can perform the
same or similar functions through different sets of reactions. 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 alignments 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. Our
experiments on real datasets demonstrate that our method can identify
biologically relevant alignments that are missed by the traditional
alignment methods. Furthermore, our method is scalable. It can compare
networks with around 50 reactions in less than a minute.