{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T01:10:21Z","timestamp":1773277821468,"version":"3.50.1"},"reference-count":30,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1576,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Mass spectrometry allows sensitive, automated and high-throughput analysis of small molecules such as metabolites. One major bottleneck in metabolomics is the identification of \u2018unknown\u2019 small molecules not in any database. Recently, fragmentation tree alignments have been introduced for the automated comparison of the fragmentation patterns of small molecules. Fragmentation pattern similarities are strongly correlated with the chemical similarity of the molecules, and allow us to cluster compounds based solely on their fragmentation patterns.<\/jats:p>\n               <jats:p>Results: Aligning fragmentation trees is computationally hard. Nevertheless, we present three exact algorithms for the problem: a dynamic programming (DP) algorithm, a sparse variant of the DP, and an Integer Linear Program (ILP). Evaluation of our methods on three different datasets showed that thousands of alignments can be computed in a matter of minutes using DP, even for \u2018challenging\u2019 instances. Running times of the sparse DP were an order of magnitude better than for the classical DP. The ILP was clearly outperformed by both DP approaches. We also found that for both DP algorithms, computing the 1% slowest alignments required as much time as computing the 99% fastest.<\/jats:p>\n               <jats:p>Contact: \u00a0sebastian.boecker@uni-jena.de<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts207","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T14:09:18Z","timestamp":1339423758000},"page":"i265-i273","source":"Crossref","is-referenced-by-count":13,"title":["Fast alignment of fragmentation trees"],"prefix":"10.1093","volume":"28","author":[{"given":"Franziska","family":"Hufsky","sequence":"first","affiliation":[{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"},{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"D\u00fchrkop","sequence":"additional","affiliation":[{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Rasche","sequence":"additional","affiliation":[{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"B\u00f6cker","sequence":"additional","affiliation":[{"name":"1 Chair for Bioinformatics, Friedrich-Schiller-University, 2Max Planck Institute for Chemical Ecology, Beutenberg Campus and 3Algorithm Engineering, Friedrich-Schiller-University, Jena, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2012,6,9]]},"reference":[{"key":"2023012512384415200_B1","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","article-title":"Proof verification and the hardness of approximation problems","volume":"45","author":"Arora","year":"1998","journal-title":"J. ACM"},{"key":"2023012512384415200_B2","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.jda.2010.09.001","article-title":"Sparse RNA folding: time and space efficient algorithms","volume":"9","author":"Backofen","year":"2011","journal-title":"J. Discrete Algorithms"},{"key":"2023012512384415200_B3","first-page":"67","article-title":"Fourier meets M\u00f6bius: fast subset convolution","volume-title":"Proceedings of ACM Symposium on Theory of Computing (STOC 2007)","author":"Bj\u00f6rklund","year":"2007"},{"key":"2023012512384415200_B4","doi-asserted-by":"crossref","first-page":"I49","DOI":"10.1093\/bioinformatics\/btn270","article-title":"Towards de novo identification of metabolites by analyzing tandem mass spectra","volume":"24","author":"B\u00f6cker","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512384415200_B5","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/978-3-642-22006-7_9","article-title":"On tree-constrained matchings and generalizations","volume-title":"Proceedings of International Conference on Automata, Languages and Programming (ICALP 2011)","author":"Canzar","year":"2011"},{"key":"2023012512384415200_B6","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1038\/nbt0208-162","article-title":"Metabolite identification via the Madison Metabolomics Consortium Database","volume":"26","author":"Cui","year":"2008","journal-title":"Nat. Biotechnol."},{"key":"2023012512384415200_B7","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1038\/nrm1451","article-title":"Metabolite profiling: from diagnostics to systems biology","volume":"5","author":"Fernie","year":"2004","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023012512384415200_B8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.trac.2008.01.007","article-title":"Extending the breadth of metabolite profiling by gas chromatography coupled to mass spectrometry","volume":"27","author":"Fiehn","year":"2008","journal-title":"Trends Analyt. Chem."},{"key":"2023012512384415200_B9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1093\/jxb\/eri069","article-title":"Chemical derivatization and mass spectral libraries in metabolic profiling by GC\/MS and LC\/MS\/MS","volume":"56","author":"Halket","year":"2005","journal-title":"J. Exp. Bot."},{"key":"2023012512384415200_B10","first-page":"350","article-title":"Hopscotch hashing","volume-title":"Proceedings of Symposium on Distributed Computing (DISC 2008)","author":"Herlihy","year":"2008"},{"key":"2023012512384415200_B11","doi-asserted-by":"crossref","first-page":"5574","DOI":"10.1021\/ac800548g","article-title":"Mass spectral metabonomics beyond elemental formula: chemical database querying by matching experimental with computational fragmentation spectra","volume":"80","author":"Hill","year":"2008","journal-title":"Anal. Chem."},{"key":"2023012512384415200_B12","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1002\/jms.1777","article-title":"MassBank: a public repository for sharing mass spectral data for life sciences","volume":"45","author":"Horai","year":"2010","journal-title":"J. Mass Spectrom."},{"key":"2023012512384415200_B13","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/0304-3975(95)80029-9","article-title":"Alignment of trees: an alternative to tree edit","volume":"143","author":"Jiang","year":"1995","journal-title":"Theor. Comput. Sci."},{"key":"2023012512384415200_B14","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1038\/nrm2098","article-title":"Towards the plant metabolome and beyond","volume":"8","author":"Last","year":"2007","journal-title":"Nat. Rev. Mol. Cell Biol."},{"key":"2023012512384415200_B15","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1073\/pnas.53.1.134","article-title":"Topological mapping of organic molecules","volume":"53","author":"Lederberg","year":"1965","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023012512384415200_B16","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/0010-4809(89)90039-6","article-title":"Tree graphs of RNA secondary structures and their comparisons","volume":"22","author":"Le","year":"1989","journal-title":"Comput. Biomed. Res."},{"key":"2023012512384415200_B17","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1126\/science.1168243","article-title":"Drug discovery and natural products: end of an era or an endless frontier?","volume":"325","author":"Li","year":"2009","journal-title":"Science"},{"key":"2023012512384415200_B18","first-page":"68","article-title":"Solving the prize-collecting steiner tree problem to optimality","volume-title":"Proceedings of Algorithm Engineering and Experiments (ALENEX 2005)","author":"Ljubi\u0107","year":"2005"},{"key":"2023012512384415200_B19","doi-asserted-by":"crossref","first-page":"2779","DOI":"10.1007\/s00216-010-4142-5","article-title":"Computational mass spectrometry for metabolomics \u2013 a review","volume":"398","author":"Neumann","year":"2010","journal-title":"Anal. Bioanal. Chem."},{"key":"2023012512384415200_B20","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1002\/jms.1545","article-title":"On the inter-instrument and inter-laboratory transferability of a tandem mass spectral reference library: 1. results of an Austrian multicenter study","volume":"44","author":"Oberacher","year":"2009","journal-title":"J. Mass Spectrom."},{"key":"2023012512384415200_B21","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","article-title":"Cuckoo hashing","volume":"51","author":"Pagh","year":"2004","journal-title":"J. Algorithms"},{"key":"2023012512384415200_B22","doi-asserted-by":"crossref","first-page":"1243","DOI":"10.1021\/ac101825k","article-title":"Computing fragmentation trees from tandem mass spectrometry data","volume":"83","author":"Rasche","year":"2011","journal-title":"Anal. Chem."},{"key":"2023012512384415200_B23","doi-asserted-by":"crossref","first-page":"3417","DOI":"10.1021\/ac300304u","article-title":"Identifying the unknowns by aligning fragmentation trees","volume":"84","author":"Rasche","year":"2012","journal-title":"Anal. Chem."},{"key":"2023012512384415200_B24","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/978-3-642-29627-7_22","article-title":"Finding maximum colorful subtrees in practice","volume-title":"Proceedings of Research in Computational Molecular Biology (RECOMB 2012).","author":"Rauf","year":"2012"},{"key":"2023012512384415200_B25","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/978-3-642-20036-6_36","article-title":"Computing fragmentation trees from metabolite multiple mass spectrometry data","volume-title":"Proceedings of Research in Computational Molecular Biology (RECOMB 2011)","author":"Scheubert","year":"2011"},{"key":"2023012512384415200_B26","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1038\/nchembio0707-360","article-title":"Revisiting the ancient concept of botanical therapeutics","volume":"3","author":"Schmidt","year":"2007","journal-title":"Nat. Chem. Biol."},{"key":"2023012512384415200_B27","first-page":"599","article-title":"Dijkstra's algorithm revisited: the dynamic programming connexion","volume":"35","author":"Sniedovich","year":"2006","journal-title":"Control Cybern."},{"key":"2023012512384415200_B28","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.jchromb.2008.07.004","article-title":"Mass spectrometry for the identification of the discriminating signals from metabolomics: current status and future trends","volume":"871","author":"Werner","year":"2008","journal-title":"J. Chromatogr. B"},{"key":"2023012512384415200_B29","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(94)90062-0","article-title":"Some MAX SNP-hard results concerning unordered labeled trees","volume":"49","author":"Zhang","year":"1994","journal-title":"Inf. Process. Lett."},{"key":"2023012512384415200_B30","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/BF01975866","article-title":"A constrained edit distance between unordered labeled trees","volume":"15","author":"Zhang","year":"1996","journal-title":"Algorithmica"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i265\/48872789\/bioinformatics_28_12_i265.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i265\/48872789\/bioinformatics_28_12_i265.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T16:40:46Z","timestamp":1674664846000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/12\/i265\/267717"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,9]]},"references-count":30,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts207","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,6,15]]},"published":{"date-parts":[[2012,6,9]]}}}