{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T08:09:57Z","timestamp":1778054997911,"version":"3.51.4"},"reference-count":15,"publisher":"Oxford University Press (OUP)","issue":"15","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: An important tool for analyzing biological networks is the ability to perform homology searches, i.e. given a pattern network one would like to be able to search for occurrences of similar (sub)networks within a set of host networks. In the context of metabolic pathways, Pinter et al. [Bioinformatics, 2005] proposed to solve this computationally hard problem by restricting it to the case where both the pattern and host networks are trees. This restriction, however, severely limits the applicability of their algorithm.<\/jats:p><jats:p>Results: We propose a very fast and simple algorithm for the alignment of metabolic pathways that does not restrict the topology of the host or pattern network in any way; instead, our algorithm exploits a natural property of metabolic networks that we call \u2018local diversity property\u2019. Experiments on a test bed of metabolic pathways from the BioCyc database indicate that our algorithm is much faster than the restricted algorithm of Pinter et al.\u2014the metabolic pathways of two organisms can be aligned in mere seconds\u2014and yet has a wider range of applicability and yields new biological insights. Our ideas can likely be extended to work for the alignment of various types of biological networks other than metabolic pathways.<\/jats:p><jats:p>Availability: Our algorithm has been implemented in C++ as a user-friendly metabolic pathway alignment tool called METAPAT. The tool runs under Linux or Windows and can be downloaded at http:\/\/theinf1.informatik.uni-jena.de\/metapat\/;<\/jats:p><jats:p>Contact: \u00a0florian.rasche@uni-jena.de<\/jats:p><jats:p>Supplementary information: Supplementary data are available at bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btm279","type":"journal-article","created":{"date-parts":[[2007,6,1]],"date-time":"2007-06-01T00:14:26Z","timestamp":1180656866000},"page":"1978-1985","source":"Crossref","is-referenced-by-count":25,"title":["Simple and fast alignment of metabolic pathways by exploiting local diversity"],"prefix":"10.1093","volume":"23","author":[{"given":"Sebastian","family":"Wernicke","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Rasche","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Friedrich-Schiller-Universit\u00e4t Jena, Ernst-Abbe-Platz 2, 07743 Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2007,5,31]]},"reference":[{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/s004530010023","article-title":"Faster algorithms for subgraph isomorphism of k-connected partial k-trees","volume":"27","author":"Dessmark","year":"2000","journal-title":"Algorithmica"},{"key":"2023041105315951900_","volume-title":"Biological Sequence Analysis","author":"Durbin","year":"1999"},{"key":"2023041105315951900_","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2023041105315951900_","first-page":"305","article-title":"Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth","volume-title":"Proceedings of the 27th International. Symposium on Mathematical Foundations of Computer Science (MFCS'02), volume 2420 of Lecture Notes in Computer Science","author":"Hajiaghayi","year":"2002"},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"6083","DOI":"10.1093\/nar\/gki892","article-title":"Expansion of the BioCyc collection of pathway\/genome databases to 160 genomes","volume":"19","author":"Karp","year":"2005","journal-title":"Nucleic Acids Res."},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1093\/nar\/gkh411","article-title":"PathBLAST: a tool for alignment of protein interaction networks","volume":"32","author":"Kelley","year":"2004","journal-title":"Nucleic Acids Res."},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/0012-365X(92)90687-B","article-title":"On the complexity of finding iso- and other morphisms for partial k-trees","volume":"108","author":"Matou\u0161ek","year":"1992","journal-title":"Discrete Math."},{"key":"2023041105315951900_","volume-title":"Bioinformatics: Sequence and Genome Analysis","author":"Mount","year":"2004"},{"key":"2023041105315951900_","first-page":"59","article-title":"Approximate labelled subtree homeomorphism","volume-title":"Proceedings of 15th CPM, volume 3109 of Lecture Notes in Computer Science","author":"Pinter","year":"2004"},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"3401","DOI":"10.1093\/bioinformatics\/bti554","article-title":"Alignment of metabolic pathways","volume":"21","author":"Pinter","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1038\/nbt1196","article-title":"Modeling cellular machinery through biological network comparison","volume":"24","author":"Sharan","year":"2006","journal-title":"Nat. Biotechnol."},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1186\/1471-2105-7-199","article-title":"QPath: a method for querying pathways in a protein\u2013protein interaction network","volume":"7","author":"Shlomi","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023041105315951900_","volume-title":"Cross-Platform GUI Programming with wxWidgets","author":"Smart","year":"2005"},{"key":"2023041105315951900_","first-page":"376","article-title":"A multiple alignment algorithm for metabolic pathway analysis using enzyme hierarchy. In","volume-title":"Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology (ISMB'00)","author":"Tohsato","year":"2000"},{"key":"2023041105315951900_","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1109\/TCBB.2006.51","article-title":"Efficient detection of network motifs","volume":"3","author":"Wernicke","year":"2006","journal-title":"IEEE\/ACM Trans. Compu. Biol. Bioinform."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/15\/1978\/49815378\/bioinformatics_23_15_1978.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/23\/15\/1978\/49815378\/bioinformatics_23_15_1978.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,12]],"date-time":"2023-05-12T03:43:08Z","timestamp":1683862988000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/23\/15\/1978\/204855"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,31]]},"references-count":15,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2007,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btm279","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2007,8]]},"published":{"date-parts":[[2007,5,31]]}}}