{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,1]],"date-time":"2024-08-01T22:04:45Z","timestamp":1722549885600},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"13","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1201,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Given a pair of metabolic pathways, an alignment of the pathways corresponds to a mapping between similar substructures of the pair. Successful alignments may provide useful applications in phylogenetic tree reconstruction, drug design and overall may enhance our understanding of cellular metabolism.<\/jats:p>\n               <jats:p>Results: We consider the problem of providing one-to-many alignments of reactions in a pair of metabolic pathways. We first provide a constrained alignment framework applicable to the problem. We show that the constrained alignment problem even in a primitive setting is computationally intractable, which justifies efforts for designing efficient heuristics. We present our Constrained Alignment of Metabolic Pathways (CAMPways) algorithm designed for this purpose. Through extensive experiments involving a large pathway database, we demonstrate that when compared with a state-of-the-art alternative, the CAMPways algorithm provides better alignment results on metabolic networks as far as measures based on same-pathway inclusion and biochemical significance are concerned. The execution speed of our algorithm constitutes yet another important improvement over alternative algorithms.<\/jats:p>\n               <jats:p>Availability: Open source codes, executable binary, useful scripts, all the experimental data and the results are freely available as part of the Supplementary Material at http:\/\/code.google.com\/p\/campways\/.<\/jats:p>\n               <jats:p>Contact: \u00a0cesim@khas.edu.tr<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btt235","type":"journal-article","created":{"date-parts":[[2013,6,27]],"date-time":"2013-06-27T05:33:26Z","timestamp":1372311206000},"page":"i145-i153","source":"Crossref","is-referenced-by-count":15,"title":["CAMPways: constrained alignment framework for the comparative analysis of a pair of metabolic pathways"],"prefix":"10.1093","volume":"29","author":[{"given":"Gamze","family":"Abaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T\u00fcrker","family":"B\u0131y\u0131ko\u011flu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cesim","family":"Erten","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2013,6,19]]},"reference":[{"key":"2023062614275699300_btt235-B1","doi-asserted-by":"crossref","first-page":"e1002518","DOI":"10.1371\/journal.pcbi.1002518","article-title":"Reconstruction of genome-scale active metabolic networks for 69 human cell types and 16 cancer types using init","volume":"8","author":"Agren","year":"2012","journal-title":"PLoS Comput. Biol."},{"key":"2023062614275699300_btt235-B2","doi-asserted-by":"crossref","first-page":"917","DOI":"10.1093\/bioinformatics\/btt071","article-title":"Spinal: scalable protein interaction network alignment","volume":"29","author":"Alada\u011f","year":"2013","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B3","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1089\/cmb.2010.0280","article-title":"Submap: aligning metabolic pathways with subnetwork mappings","volume":"18","author":"Ay","year":"2011","journal-title":"J. Comput. Biol."},{"key":"2023062614275699300_btt235-B4","doi-asserted-by":"crossref","first-page":"S2","DOI":"10.1186\/1471-2105-13-S3-S2","article-title":"Metabolic network alignment in large scale by network compression","volume":"13","author":"Ay","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023062614275699300_btt235-B5","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1137\/090753115","article-title":"Belief propagation for weighted b-matchings on arbitrary graphs and its relation to linear programs with integer solutions","volume":"25","author":"Bayati","year":"2011","journal-title":"SIAM J. Discrete Math."},{"key":"2023062614275699300_btt235-B6","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1515\/BC.2009.021","article-title":"Murine and human cathepsin B exhibit similar properties: possible implications for drug discovery","volume":"390","author":"Caglic","year":"2009","journal-title":"Biol. Chem."},{"key":"2023062614275699300_btt235-B7","doi-asserted-by":"crossref","first-page":"D623","DOI":"10.1093\/nar\/gkm900","article-title":"The MetaCyc database of metabolic pathways and enzymes and the biocyc collection of pathway\/genome databases","volume":"36","author":"Caspi","year":"2008","journal-title":"Nucleic Acids Res."},{"key":"2023062614275699300_btt235-B8","first-page":"123","article-title":"Local optimization for global alignment of protein interaction networks","volume-title":"Pacific Symposium on Biocomputing","author":"Chindelevitch","year":"2010"},{"key":"2023062614275699300_btt235-B9","doi-asserted-by":"crossref","first-page":"e110","DOI":"10.1093\/bioinformatics\/btl307","article-title":"Phylogenetic reconstruction from non-genomic data","volume":"23","author":"Clemente","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.6028\/jres.069B.013","article-title":"Maximum matching and a polyhedron with 0 1-vertices","volume":"69","author":"Edmonds","year":"1965","journal-title":"J. Res. Natl Bur. Stand. B"},{"key":"2023062614275699300_btt235-B11","doi-asserted-by":"crossref","first-page":"1169","DOI":"10.1101\/gr.5235706","article-title":"Graemlin: general and robust alignment of multiple large interaction networks","volume":"16","author":"Flannick","year":"2006","journal-title":"Genome Res."},{"key":"2023062614275699300_btt235-B12","author":"Gabow","year":"1983"},{"key":"2023062614275699300_btt235-B13","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"2023062614275699300_btt235-B14","doi-asserted-by":"crossref","first-page":"1616","DOI":"10.1093\/bioinformatics\/btm150","article-title":"A network-based method for target selection in metabolic networks","volume":"23","author":"Guimer\u00e0","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B15","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1093\/bioinformatics\/btg1018","article-title":"Deriving phylogenetic trees from the similarity analysis of metabolic pathways","volume":"19","author":"Heymans","year":"2003","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1093\/nar\/gkr988","article-title":"KEGG for integration and interpretation of large-scale molecular data sets","volume":"40","author":"Kanehisa","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023062614275699300_btt235-B17","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":"2023062614275699300_btt235-B18","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1089\/cmb.2006.13.182","article-title":"Pairwise alignment of protein interaction networks","volume":"13","author":"Koyut\u00fcrk","year":"2006","journal-title":"J. Comput. Biol."},{"key":"2023062614275699300_btt235-B19","doi-asserted-by":"crossref","first-page":"1390","DOI":"10.1093\/bioinformatics\/btr127","article-title":"Integrative network alignment reveals large regions of global network similarity in yeast and human","volume":"27","author":"Kuchaiev","year":"2011","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B20","doi-asserted-by":"crossref","first-page":"i253","DOI":"10.1093\/bioinformatics\/btp203","article-title":"Isorankn: spectral methods for global alignment of multiple protein networks","volume":"25","author":"Liao","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B21","volume-title":"Advanced Organic Chemistry: Reactions, Mechanisms, and Structure","author":"March","year":"1985"},{"key":"2023062614275699300_btt235-B22","volume-title":"Leda: A Platform for Combinatorial and Geometric Computing","author":"Mehlhorn","year":"1999"},{"key":"2023062614275699300_btt235-B23","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1093\/molbev\/msq213","article-title":"Comparative analysis of metabolic networks provides insight into the evolution of plant pathogenic and non-pathogenic lifestyles in Pseudomonas","volume":"28","author":"Mithani","year":"2011","journal-title":"Mol. Biol. Evol."},{"key":"2023062614275699300_btt235-B24","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":"2023062614275699300_btt235-B25","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1016\/S0166-218X(02)00205-6","article-title":"A note on greedy algorithms for the maximum weighted independent set problem","volume":"126","author":"Sakai","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"2023062614275699300_btt235-B26","doi-asserted-by":"crossref","first-page":"1974","DOI":"10.1073\/pnas.0409522102","article-title":"Conserved patterns of protein interaction in multiple species","volume":"102","author":"Sharan","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA"},{"key":"2023062614275699300_btt235-B27","first-page":"303","article-title":"Global alignment of multiple protein interaction networks","volume-title":"Pacific Symposium on Biocomputing","author":"Singh","year":"2008"},{"key":"2023062614275699300_btt235-B28","author":"Tohsato","year":"2000"},{"key":"2023062614275699300_btt235-B29","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1089\/cmb.2006.0076","article-title":"Path matching and graph matching in biological networks","volume":"14","author":"Yang","year":"2007","journal-title":"J. Comput. Biol."},{"key":"2023062614275699300_btt235-B30","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1093\/bioinformatics\/btp196","article-title":"Global alignment of protein-protein interaction networks by graph matching methods","volume":"25","author":"Zaslavskiy","year":"2009","journal-title":"Bioinformatics"},{"key":"2023062614275699300_btt235-B31","doi-asserted-by":"crossref","first-page":"1631","DOI":"10.1093\/bioinformatics\/btm156","article-title":"Alignment of molecular networks by integer quadratic programming","volume":"23","author":"Zhenping","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i145\/50702494\/bioinformatics_29_13_i145.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/29\/13\/i145\/50702494\/bioinformatics_29_13_i145.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,26]],"date-time":"2023-06-26T15:27:41Z","timestamp":1687793261000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/29\/13\/i145\/197346"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6,19]]},"references-count":31,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btt235","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2013,7]]},"published":{"date-parts":[[2013,6,19]]}}}