An important tool for analyzing metabolic pathways is being able to do homology searches, that is, for a given pattern network one would like to find occurrences of similar (sub)networks within a set of host networks. In the context of metabolic pathways, Pinter et al. [Bioinformatics, 2005] recently proposed to solve this computationally hard problem by restricting it to the case where both the pattern and host network are trees. This restriction, however, severely limits the applicability of theiralgorithm. Here, we propose a novel algorithm that does not restrict the topology of the host or pattern network in any way; instead, we exploit a natural property of metabolic networks that we call "local diversity property," which allows us to obtain avery fast and simple algorithm for the alignment of metabolic pathways. Experiments on a testbed of metabolic pathways extracted from the BloCYC database indicate that our algorithm is much faster than the restricted algorithm of Pinter et al. and yet has a wider range of applicability and yields new biological insights.
展开▼
