{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T21:07:31Z","timestamp":1766869651042},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"S14","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>In contrast to the increasing number of the successful genome projects, there still remain many orphan metabolites for which their synthesis processes are unknown. Metabolites, including these orphan metabolites, can be classified into groups that share the same core substructures, originated from the same biosynthetic pathways. It is known that many metabolites are synthesized by adding up building blocks to existing metabolites. Therefore, it is proposed that, for any given group of metabolites, finding the core substructure and the branched substructures can help predict their biosynthetic pathway. There already have been many reports on the multiple graph alignment techniques to find the conserved chemical substructures in relatively small molecules. However, they are optimized for ligand binding and are not suitable for metabolomic studies.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>We developed an efficient multiple graph alignment method named as MUCHA (Multiple Chemical Alignment), specialized for finding metabolic building blocks. This method showed the strength in finding metabolic building blocks with preserving the relative positions among the substructures, which is not achieved by simply applying the frequent graph mining techniques. Compared with the combined pairwise alignments, this proposed MUCHA method generally reduced computational costs with improving the quality of the alignment.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>MUCHA successfully find building blocks of secondary metabolites, and has a potential to complement to other existing methods to reconstruct metabolic networks using reaction patterns.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-12-s14-s1","type":"journal-article","created":{"date-parts":[[2011,12,14]],"date-time":"2011-12-14T19:40:16Z","timestamp":1323891616000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["MUCHA: multiple chemical alignment algorithm to identify building block substructures of orphan secondary metabolites"],"prefix":"10.1186","volume":"12","author":[{"given":"Masaaki","family":"Kotera","sequence":"first","affiliation":[]},{"given":"Toshiaki","family":"Tokimatsu","sequence":"additional","affiliation":[]},{"given":"Minoru","family":"Kanehisa","sequence":"additional","affiliation":[]},{"given":"Susumu","family":"Goto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,12,14]]},"reference":[{"key":"4960_CR1","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.mycres.2007.08.018","volume":"112","author":"JC Frisvad","year":"2008","unstructured":"Frisvad JC, Andersen B, Thrane U: The use of secondary metabolite profiling in chemotaxonomy of filamentous fungi. Mycological Research 2008, 112: 231\u2013240. 10.1016\/j.mycres.2007.08.018","journal-title":"Mycological Research"},{"key":"4960_CR2","doi-asserted-by":"publisher","first-page":"1747","DOI":"10.1002\/jsfa.2560","volume":"86","author":"M Smallwood","year":"2006","unstructured":"Smallwood M: The impact of genomics on crops for industry. J Sci Food Agric 2006, 86: 1747\u20131754. 10.1002\/jsfa.2560","journal-title":"J Sci Food Agric"},{"key":"4960_CR3","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00303957","volume":"75","author":"M Wink","year":"1988","unstructured":"Wink M: Plant breeding: importance of plant secondary metabolites for protection against pathogens and herbivores. Theor App Genet 1988, 75: 225\u2013233. 10.1007\/BF00303957","journal-title":"Theor App Genet"},{"key":"4960_CR4","doi-asserted-by":"publisher","first-page":"2335","DOI":"10.1021\/ci800213g","volume":"48","author":"M Kotera","year":"2008","unstructured":"Kotera M, McDonald AG, Boyce S, Tipton KF: Eliciting possible reaction equations and metabolic pathways involving orphan metabolites. J Chem Inf Model 2008, 48: 2335\u20132349. 10.1021\/ci800213g","journal-title":"J Chem Inf Model"},{"key":"4960_CR5","doi-asserted-by":"publisher","first-page":"1407","DOI":"10.1016\/S0304-3975(02)00043-9","volume":"290","author":"P Blayo","year":"2003","unstructured":"Blayo P, Rouz\u00e9 P, Sagot M: Orphan gene finding - an exon assembly approach. Theor Comp Sci 2003, 290: 1407\u20131431. 10.1016\/S0304-3975(02)00043-9","journal-title":"Theor Comp Sci"},{"key":"4960_CR6","doi-asserted-by":"publisher","first-page":"14689","DOI":"10.1073\/pnas.0305199101","volume":"101","author":"J Berg","year":"2004","unstructured":"Berg J, Lassig M: Local graph alignment and motif search in biological networks. PNAS 2004, 101: 14689\u201314694. 10.1073\/pnas.0305199101","journal-title":"PNAS"},{"key":"4960_CR7","doi-asserted-by":"publisher","first-page":"1669","DOI":"10.1126\/science.1069883","volume":"295","author":"EH Davidson","year":"2002","unstructured":"Davidson EH, Rast JP, Oliveri P, Ransick A, Calestani C, Yuh C, Minokawa T, Amore G, Hinman V, Arenas-Mena C, Otim O, Brown TC, Livi CB, Lee PY, Revilla R, Rust AG, Pan ZJ, Schilstra MJ, Clarke PJC, Arnone MI, Rowen L, Cameron RA, McClay DR, Hood L, Bolouri H: A genomic regulatory network for development. Science 2002, 295: 1669\u20131678. 10.1126\/science.1069883","journal-title":"Science"},{"key":"4960_CR8","doi-asserted-by":"publisher","first-page":"D277","DOI":"10.1093\/nar\/gkh063","volume":"32","author":"M Kanehisa","year":"2004","unstructured":"Kanehisa M, Goto S, Kawashima S, Okuno Y, Hattori M: The KEGG resource for deciphering the genome. Nucl Acids Res 2004, 32: D277-D280. 10.1093\/nar\/gkh063","journal-title":"Nucl Acids Res"},{"key":"4960_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1093\/nar\/30.1.303","volume":"30","author":"XL Salwinski","year":"2002","unstructured":"Salwinski XL, Duan X, Higney P, Kim S, Eisenberg D: DIP, the database for interacting proteins: A research tool for studying cellular networks of protein interactions. Nucl Acids Res 2002, 30: 303\u2013305. 10.1093\/nar\/30.1.303","journal-title":"Nucl Acids Res"},{"key":"4960_CR10","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1089\/106652701300312896","volume":"8","author":"N Leibowitz","year":"2001","unstructured":"Leibowitz N, Nussinov R, Wolfson HJ: MUSTA-a general, efficient, automated method for multiple structure alignment and detection of common motifs: application to proteins. J Comp Biol 2001, 8: 93\u2013121. 10.1089\/106652701300312896","journal-title":"J Comp Biol"},{"key":"4960_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1002\/prot.10628","volume":"56","author":"M Shatsky","year":"2004","unstructured":"Shatsky M, Nussinov R, Wolfson HJ: A method for simultaneous alignment of multiple protein structures. Proteins Struct Func Bioinf 2004, 56: 143\u2013156. 10.1002\/prot.10628","journal-title":"Proteins Struct Func Bioinf"},{"key":"4960_CR12","doi-asserted-by":"publisher","first-page":"2110","DOI":"10.1093\/bioinformatics\/btp144","volume":"25","author":"T Fober","year":"2009","unstructured":"Fober T, Mernberger M, Klebe G, Hullermeier E: Evolutionary construction of multiple graph alignments for the structural analysis of biomolecules. Bioinformatics 2009, 25: 2110\u20132117. 10.1093\/bioinformatics\/btp144","journal-title":"Bioinformatics"},{"key":"4960_CR13","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1021\/ci020023s","volume":"42","author":"L Chen","year":"2002","unstructured":"Chen L, Nourse JG, Christie BD, Leland BA, Grier DL: Over 20 years of reaction access systems from MDL: a novel reaction substructure search algorithm. J Chem Inf Comput Sci 2002, 42: 1296\u20131310. 10.1021\/ci020023s","journal-title":"J Chem Inf Comput Sci"},{"key":"4960_CR14","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1021\/ci00031a005","volume":"21","author":"JJ McGregor","year":"1981","unstructured":"McGregor JJ, Willett P: Use of a maximal common subgraph algorithm in the automatic identification of the ostensible bond changes occurring in chemical reactions. J Chem Inf Comput Sci 1981, 21: 137\u2013140. 10.1021\/ci00031a005","journal-title":"J Chem Inf Comput Sci"},{"key":"4960_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-642-73975-0_33","volume-title":"Chemical Structures, The International Language of Chemistry","author":"TE Moock","year":"1988","unstructured":"Moock TE, Nourse JG, Grier D, Hounshell WD: The implementation of atom-atom mapping and related features in the reaction access system (REACCS). In Chemical Structures, The International Language of Chemistry. Edited by: Warr WA. Berlin. Germany: Springer-Verlag; 1988:303\u2013313."},{"key":"4960_CR16","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1023\/A:1021271615909","volume":"16","author":"JW Raymond","year":"2002","unstructured":"Raymond JW, Willett P: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J Comput Aided Mol Des 2002, 16: 521\u2013533. 10.1023\/A:1021271615909","journal-title":"J Comput Aided Mol Des"},{"key":"4960_CR17","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1093\/comjnl\/45.6.631","volume":"45","author":"JW Raymond","year":"2002","unstructured":"Raymond JW, Gardiner EJ, Willett P: RASCAL: Calculation of graph similarity using maximum common edge subgraphs. Comput J 2002, 45: 631\u2013644. 10.1093\/comjnl\/45.6.631","journal-title":"Comput J"},{"key":"4960_CR18","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1021\/ci010381f","volume":"42","author":"JW Raymond","year":"2002","unstructured":"Raymond JW, Gardiner EJ, Willett P: Heuristics for similarity searching of chemical graphs using a maximum common edge subgraph algorithm. J Chem Inf Comput Sci 2002, 42: 305\u2013316. 10.1021\/ci010381f","journal-title":"J Chem Inf Comput Sci"},{"key":"4960_CR19","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1016\/S0003-2670(00)83783-6","volume":"200","author":"Y Takahashi","year":"1987","unstructured":"Takahashi Y, Maeda S, Sasaki S: Automated recognition of common geometrical patterns among a variety of three-dimensional molecular structures. Analytica Chimica Acta 1987, 200: 363\u2013377.","journal-title":"Analytica Chimica Acta"},{"key":"4960_CR20","doi-asserted-by":"publisher","first-page":"11853","DOI":"10.1021\/ja036030u","volume":"125","author":"M Hattori","year":"2003","unstructured":"Hattori M, Okuno Y, Goto S, Kanehisa M: Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways. J Am Chem Soc 2003, 125: 11853\u201311865. 10.1021\/ja036030u","journal-title":"J Am Chem Soc"},{"key":"4960_CR21","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ipl.2004.06.019","volume":"92","author":"A Yamaguchi","year":"2004","unstructured":"Yamaguchi A, Aoki KF, Mamitsuka H: Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees. Inf Process Lett 2004, 92: 57\u201363. 10.1016\/j.ipl.2004.06.019","journal-title":"Inf Process Lett"},{"key":"4960_CR22","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1023\/A:1021726221443","volume":"50","author":"A Inokuchi","year":"2003","unstructured":"Inokuchi A, Washio T, Motoda H: Complete mining of frequent patterns from graphs: mining graph data. Machine Learning 2003, 50: 321\u2013354. 10.1023\/A:1021726221443","journal-title":"Machine Learning"},{"key":"4960_CR23","doi-asserted-by":"publisher","first-page":"i200","DOI":"10.1093\/bioinformatics\/bth919","volume":"20","author":"M Koyuturk","year":"2004","unstructured":"Koyuturk M, Grama A, Szpankowski W: An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics 2004, 20: i200-i207. 10.1093\/bioinformatics\/bth919","journal-title":"Bioinformatics"},{"key":"4960_CR24","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.entcs.2004.12.039","volume":"127","author":"S Nijssen","year":"2005","unstructured":"Nijssen S, Kok JN: The gaston tool for frequent subgraph mining. Electronic Notes Theor Comput Sci 2005, 127: 77\u201387. 10.1016\/j.entcs.2004.12.039","journal-title":"Electronic Notes Theor Comput Sci"},{"key":"4960_CR25","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-1-4615-4401-2_10","volume":"15","author":"H Bunke","year":"2000","unstructured":"Bunke H, Jiang X: Graph matching and similarity. Intel ligent systems and interfaces 2000, 15: 281\u2013304. 10.1007\/978-1-4615-4401-2_10","journal-title":"Intel ligent systems and interfaces"},{"key":"4960_CR26","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron C, Kerbosch J: Finding all cliques of an undirected graph. Comm ACM 1973, 16: 575\u2013577. 10.1145\/362342.362367","journal-title":"Comm ACM"},{"key":"4960_CR27","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/spe.4380120103","volume":"12","author":"JJ McGregor","year":"1982","unstructured":"McGregor JJ: Backtrack search algorithms and the maximal common subgraph problem. Software - Practice and Experience 1982, 12: 23\u201334. 10.1002\/spe.4380120103","journal-title":"Software - Practice and Experience"},{"key":"4960_CR28","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1145\/321958.321963","volume":"23","author":"DC Schmidt","year":"1976","unstructured":"Schmidt DC, Druffel LE: A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices. J ACM 1976, 23: 433\u2013445. 10.1145\/321958.321963","journal-title":"J ACM"},{"key":"4960_CR29","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1093\/nar\/30.1.402","volume":"30","author":"S Goto","year":"2002","unstructured":"Goto S, Okuno Y, Hattori M, Nishioka T, Kanehisa M: LIGAND: database of chemical compounds and reactions in biological pathways. Nucl Acids Res 2002, 30: 402\u2013404. 10.1093\/nar\/30.1.402","journal-title":"Nucl Acids Res"},{"key":"4960_CR30","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1145\/959242.959248","volume":"5","author":"T Gartner","year":"2003","unstructured":"Gartner T: A survey of kernels for structured data. SIGKKD Explorations 2003, 5: 49\u201358. 10.1145\/959242.959248","journal-title":"SIGKKD Explorations"},{"key":"4960_CR31","doi-asserted-by":"publisher","first-page":"16487","DOI":"10.1021\/ja0466457","volume":"126","author":"M Kotera","year":"2004","unstructured":"Kotera M, Okuno Y, Hattori M, Goto S, Kanehisa M: Computational assignment of the EC numbers for genomic-scale analysis of enzymatic reactions. J Am Chem Soc 2004, 126: 16487\u201316498. 10.1021\/ja0466457","journal-title":"J Am Chem Soc"},{"key":"4960_CR32","doi-asserted-by":"publisher","first-page":"i179","DOI":"10.1093\/bioinformatics\/btp223","volume":"25","author":"Y Yamanishi","year":"2009","unstructured":"Yamanishi Y, Hattori M, Kotera M, Goto S, Kanehisa M: E-zyme: predicting potential EC numbers from the chemical transformation pattern of substrate-product pairs. Bioinformatics 2009, 25: i179-i186. 10.1093\/bioinformatics\/btp223","journal-title":"Bioinformatics"},{"key":"4960_CR33","doi-asserted-by":"publisher","first-page":"D517","DOI":"10.1093\/nar\/gkj076","volume":"34","author":"LBM Ellis","year":"2006","unstructured":"Ellis LBM, Roe D, Wackett LP: The University of Minnesota Biocatalysis\/Biodegradation Database: the first decade. Nucl Acids Res 2006, 34: D517-D521. 10.1093\/nar\/gkj076","journal-title":"Nucl Acids Res"},{"key":"4960_CR34","doi-asserted-by":"publisher","first-page":"W138","DOI":"10.1093\/nar\/gkq318","volume":"38","author":"Y Moriya","year":"2010","unstructured":"Moriya Y, Shigemizu D, Hattori M, Tokimatsu T, Kotera M, Goto S, Kanehisa M: PathPred: an enzyme-catalyzed metabolic pathway prediction server. Nucl Acids Res 2010, 38: W138-W143. 10.1093\/nar\/gkq318","journal-title":"Nucl Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-12-S14-S1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T17:47:45Z","timestamp":1630518465000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-12-S14-S1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":34,"journal-issue":{"issue":"S14","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["4960"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-12-s14-s1","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"14 December 2011","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S1"}}