SubMAP: Aligning metabolic pathways with subnetwork mappings

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.