| Mapping and Filling Metabolic Pathways (2008) | |||||||||||||||||
Abstract | |||||||||||||||||
| Abstract. Network mappings are extensively used for comparing, exploring, and predicting biological networks, are essential for pathway database search and also helpful for finding and filling pathway holes. Existing mapping tools are mostly based on isomorphic and homeomorphic embedding effectively solving a problem that is NP-complete even when searching a match for a tree in acyclic networks. On the other hand, if mapping of different nodes from the query network into the same node from the text network is allowed, then trees can be optimally mapped into arbitrary networks in polynomial time. For such mappings (homomorphisms), the undesirable node collapse can be prevented by appropriately setting cost on matching of different nodes. In this paper we extend our algorithm to efficiently find optimal homomorphism from a directed graph with restricted cyclic structure to an arbitrary network. We have applied homomorphisms to mapping metabolic pathways using enzyme matching cost based on EC notation. We have performed pairwise mapping of all pathways for four organisms (E. coli, S. cerevisiae, B. subtilis and T. thermophilus species) and found a reasonably large set of statistically significant pathway similarities. We compared the obtained sets between when only tree pathways can be available for query network in the pairwise mapping and when both non tree and tree pathways are available for query network. Our experiments show that organism-to-organism pathway mapping frequently identifies pathway holes simultaneously providing possible candidates for filling them. We have proposed a framework of detecting and filling pathway holes that includes database search for missing enzymes and proteins with the matching prosites and high sequence similarity. We have identified conserved pathways across examined species and detected and filled pathway holes in existing pathway descriptions. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||