{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:48:56Z","timestamp":1772520536705,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T00:00:00Z","timestamp":1623283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>\n                      <jats:bold>Background<\/jats:bold>\n                    <\/jats:title>\n                    <jats:p>Mutation trees are rooted trees in which nodes are of arbitrary degree and labeled with a mutation set. These trees, also referred to as clonal trees, are used in computational oncology to represent the mutational history of tumours. Classical tree metrics such as the popular Robinson\u2013Foulds distance are of limited use for the comparison of mutation trees. One reason is that mutation trees inferred with different methods or for different patients often contain different sets of mutation labels.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>\n                      <jats:bold>Results<\/jats:bold>\n                    <\/jats:title>\n                    <jats:p>We generalize the Robinson\u2013Foulds distance into a set of distance metrics called Bourque distances for comparing mutation trees. We show the basic version of the Bourque distance for mutation trees can be computed in linear time. We also make a connection between the Robinson\u2013Foulds distance and the nearest neighbor interchange distance.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-021-00188-3","type":"journal-article","created":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T12:03:25Z","timestamp":1623326605000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["The Bourque distances for mutation trees of cancers"],"prefix":"10.1186","volume":"16","author":[{"given":"Katharina","family":"Jahn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niko","family":"Beerenwinkel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0260-824X","authenticated-orcid":false,"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,10]]},"reference":[{"key":"188_CR1","volume-title":"Inferring phylogenies","author":"J Felsenstein","year":"2004","unstructured":"Felsenstein J. Inferring phylogenies. Sunderland: Sinauer Associates; 2004."},{"issue":"4260","key":"188_CR2","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1126\/science.959840","volume":"194","author":"PC Nowell","year":"1976","unstructured":"Nowell PC. The clonal evolution of tumor cell populations. Science. 1976;194(4260):23\u20138.","journal-title":"Science."},{"key":"188_CR3","doi-asserted-by":"crossref","unstructured":"Tateno Y, Nei M, F T. Accuracy of estimated phylogenetic trees from molecular data. J Mol Evol. 1982;18:387\u2013404.","DOI":"10.1007\/BF01840887"},{"issue":"5","key":"188_CR4","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1016\/0010-4809(89)90039-6","volume":"22","author":"SY Le","year":"1989","unstructured":"Le SY, Nussinov R, Maizel JV. Tree graphs of RNA secondary structures and their comparisons. Comput Biomed Res. 1989;22(5):461\u201373.","journal-title":"Comput Biomed Res."},{"issue":"4","key":"188_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1093\/bioinformatics\/6.4.309","volume":"6","author":"BA Shapiro","year":"1990","unstructured":"Shapiro BA, Zhang K. Comparing multiple RNA secondary structures using tree comparisons. Bioinformatics. 1990;6(4):309\u201318.","journal-title":"Bioinformatics."},{"key":"188_CR6","unstructured":"Bourque M. Arbes de Steiner et r\u00e9seaux dont certains sommets sont \u00e0 localisation variable. Thesis (Ph. D.: Informatique), Universit\u00e9 de Montr\u00e9al, Canada; 1978."},{"issue":"2","key":"188_CR7","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0095-8956(71)90020-7","volume":"11","author":"DF Robinson","year":"1971","unstructured":"Robinson DF. Comparison of labeled trees with valency three. J Comb Theory, Ser B. 1971;11(2):105\u201319.","journal-title":"J Comb Theory, Ser B."},{"issue":"1\u20132","key":"188_CR8","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson DF, Foulds LR. Comparison of phylogenetic trees. Math Biosci. 1981;53(1\u20132):131\u201347.","journal-title":"Math Biosci."},{"issue":"3","key":"188_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/0022-5193(73)90251-8","volume":"38","author":"GW Moore","year":"1973","unstructured":"Moore GW, Goodman M, Barnabas J. An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets. J Theor Biol. 1973;38(3):423\u201357.","journal-title":"J Theor Biol."},{"issue":"3","key":"188_CR10","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1093\/sysbio\/45.3.323","volume":"45","author":"DE Critchlow","year":"1996","unstructured":"Critchlow DE, Pearl DK, Qian C. The triples distance for rooted bifurcating phylogenetic trees. Syst Biol. 1996;45(3):323\u201334.","journal-title":"Syst Biol."},{"issue":"2","key":"188_CR11","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1093\/sysbio\/28.2.132","volume":"28","author":"M Goodman","year":"1979","unstructured":"Goodman M, Czelusniak J, Moore GW, Romero-Herrera AE, Matsuda G. Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. Syst Biol. 1979;28(2):132\u201363.","journal-title":"Syst Biol."},{"issue":"3","key":"188_CR12","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","volume":"46","author":"WP Maddison","year":"1997","unstructured":"Maddison WP. Gene trees in species trees. Syst Biol. 1997;46(3):523\u201336.","journal-title":"Syst Biol."},{"key":"188_CR13","volume-title":"Algorithms on trees and graphs","author":"G Valiente","year":"2013","unstructured":"Valiente G. Algorithms on trees and graphs, vol. 2. New York: Springer; 2013."},{"key":"188_CR14","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/0218082","volume":"18","author":"K Zhang","year":"1989","unstructured":"Zhang K, Shasha D. Simple fast algorithms for the editing distance between trees and related problems. SIAM J Comput. 1989;18:1245\u201362.","journal-title":"SIAM J Comput."},{"issue":"1","key":"188_CR15","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1109\/TCBB.2011.48","volume":"9","author":"D Bogdanowicz","year":"2011","unstructured":"Bogdanowicz D, Giaro K. Matching split distance for unrooted binary phylogenetic trees. IEEE\/ACM Trans Comput Biol Bioinform. 2011;9(1):150\u201360.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"10","key":"188_CR16","doi-asserted-by":"publisher","first-page":"2735","DOI":"10.1093\/molbev\/msw124","volume":"33","author":"M Kendall","year":"2016","unstructured":"Kendall M, Colijn C. Mapping phylogenetic trees to reveal distinct patterns of evolution. Mol Biol Evol. 2016;33(10):2735\u201343.","journal-title":"Mol Biol Evol."},{"issue":"4","key":"188_CR17","doi-asserted-by":"publisher","first-page":"1014","DOI":"10.1109\/TCBB.2011.157","volume":"9","author":"Y Lin","year":"2011","unstructured":"Lin Y, Rajan V, Moret BM. A metric for phylogenetic trees based on matching. IEEE\/ACM Trans Comput Biol Bioinform. 2011;9(4):1014\u201322.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform."},{"issue":"1","key":"188_CR18","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1093\/bioinformatics\/bti720","volume":"22","author":"TM Nye","year":"2006","unstructured":"Nye TM, Lio P, Gilks WR. A novel algorithm and web-based tool for comparing two alternative phylogenetic trees. Bioinformatics. 2006;22(1):117\u20139.","journal-title":"Bioinformatics."},{"key":"188_CR19","doi-asserted-by":"publisher","first-page":"519","DOI":"10.2307\/1218253","volume":"20","author":"W Williams","year":"1971","unstructured":"Williams W, Clifford H. On the comparison of two classifications of the same set of elements. Taxon. 1971;20:519\u201322.","journal-title":"Taxon."},{"issue":"50","key":"188_CR20","doi-asserted-by":"publisher","first-page":"17947","DOI":"10.1073\/pnas.1420822111","volume":"111","author":"C Gawad","year":"2014","unstructured":"Gawad C, Koh W, Quake SR. Dissecting the clonal origins of childhood acute lymphoblastic leukemia by single-cell genomics. Proc Natl Acad Sci. 2014;111(50):17947\u201352.","journal-title":"Proc Natl Acad Sci."},{"issue":"1","key":"188_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-015-0602-8","volume":"16","author":"AG Deshwar","year":"2015","unstructured":"Deshwar AG, Vembu S, Yung CK, Jang GH, Stein L, Morris Q. PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 2015;16(1):1\u201320.","journal-title":"Genome Biol."},{"issue":"13","key":"188_CR22","doi-asserted-by":"publisher","first-page":"i357","DOI":"10.1093\/bioinformatics\/bty270","volume":"34","author":"J Eaton","year":"2018","unstructured":"Eaton J, Wang J, Schwartz R. Deconvolution and phylogeny inference of structural variations in tumor genomic samples. Bioinformatics. 2018;34(13):i357\u201365.","journal-title":"Bioinformatics."},{"issue":"12","key":"188_CR23","doi-asserted-by":"publisher","first-page":"i62","DOI":"10.1093\/bioinformatics\/btv261","volume":"31","author":"M El-Kebir","year":"2015","unstructured":"El-Kebir M, Oesper L, Acheson-Field H, Raphael BJ. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics. 2015;31(12):i62\u201370.","journal-title":"Bioinformatics."},{"issue":"9","key":"188_CR24","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","volume":"31","author":"S Malikic","year":"2015","unstructured":"Malikic S, McPherson AW, Donmez N, Sahinalp CS. Clonality inference in multiple tumor samples using phylogeny. Bioinformatics. 2015;31(9):1349\u201356.","journal-title":"Bioinformatics."},{"issue":"1","key":"188_CR25","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1186\/s13059-015-0647-8","volume":"16","author":"V Popic","year":"2015","unstructured":"Popic V, Salari R, Hajirasouliha I, Kashef-Haghighi D, West RB, Batzoglou S. Fast and scalable inference of multi-sample cancer lineages. Genome Biol. 2015;16(1):91.","journal-title":"Genome Biol."},{"issue":"3","key":"188_CR26","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/bioinformatics\/btaa722","volume":"37","author":"S Ciccolella","year":"2021","unstructured":"Ciccolella S, Gomez MS, Patterson M, Della Vedova G, Hajirasouliha I, Bonizzoni P. Inferring cancer progression from single cell sequencing while allowing loss of mutations. Bioinformatics. 2021;37(3):326\u201333.","journal-title":"Bioinformatics"},{"issue":"17","key":"188_CR27","doi-asserted-by":"publisher","first-page":"i671","DOI":"10.1093\/bioinformatics\/bty589","volume":"34","author":"M El-Kebir","year":"2018","unstructured":"El-Kebir M. SPhyR: tumor phylogeny estimation from single-cell sequencing data under loss and error. Bioinformatics. 2018;34(17):i671\u20139.","journal-title":"Bioinformatics."},{"issue":"1","key":"188_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-016-0936-x","volume":"17","author":"K Jahn","year":"2016","unstructured":"Jahn K, Kuipers J, Beerenwinkel N. Tree inference for single-cell data. Genome Biol. 2016;17(1):1\u201317.","journal-title":"Genome Biol."},{"key":"188_CR29","doi-asserted-by":"publisher","first-page":"1847","DOI":"10.1101\/gr.243121.118","volume":"29","author":"H Zafar","year":"2019","unstructured":"Zafar H, Navin N, Chen K, Nakhleh L. SiCloneFit: Bayesian inference of population structure, genotype, and phylogeny of tumor clones from single-cell genome sequencing data. Genome Res. 2019;29:1847\u201359.","journal-title":"Genome Res."},{"issue":"11","key":"188_CR30","doi-asserted-by":"publisher","first-page":"1860","DOI":"10.1101\/gr.234435.118","volume":"29","author":"S Malikic","year":"2019","unstructured":"Malikic S, Mehrabadi FR, Ciccolella S, Rahman MK, Ricketts C, Haghshenas E, et al. PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data. Genome Res. 2019;29(11):1860\u201377.","journal-title":"Genome Res."},{"issue":"1","key":"188_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-019-10737-5","volume":"10","author":"S Malikic","year":"2019","unstructured":"Malikic S, Jahn K, Kuipers J, Sahinalp SC, Beerenwinkel N. Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data. Nat Commun. 2019;10(1):1\u201312.","journal-title":"Nat Commun."},{"key":"188_CR32","unstructured":"Bernardini G, Bonizzoni P, Gawrychowski P. On two measures of distance between fully-labelled trees. arXiv preprint arXiv:200205600. 2020."},{"issue":"S10","key":"188_CR33","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1186\/s12864-020-07011-0","volume":"21","author":"S Briand","year":"2020","unstructured":"Briand S, Dessimoz C, El-Mabrouk N, Lafond M, Lobinska G. A generalized Robinson\u2013Foulds distance for labeled trees. BMC Genomics. 2020;21(S10):779.","journal-title":"BMC Genomics."},{"issue":"2","key":"188_CR34","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1093\/bioinformatics\/btaa676","volume":"37","author":"S Ciccolella","year":"2021","unstructured":"Ciccolella S, Bernardini G, Denti L, Bonizzoni P, Previtali M, Della\u00a0Vedova G. Triplet-based similarity score for fully multi-labeled trees with poly-occurring labels. Bioinformatics. 2021;37(2):178\u201384.","journal-title":"Bioinformatics"},{"issue":"7","key":"188_CR35","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1093\/bioinformatics\/btz869","volume":"36","author":"Z DiNardo","year":"2020","unstructured":"DiNardo Z, Tomlinson K, Ritz A, Oesper L. Distance measures for tumor evolutionary trees. Bioinformatics. 2020;36(7):2090\u20137.","journal-title":"Bioinformatics."},{"key":"188_CR36","doi-asserted-by":"crossref","unstructured":"Govek K, Sikes C, Oesper L. A consensus approach to infer tumor evolutionary histories. In: Proceedings of 2018 ACM International Conference on Bioinformatics, Comput. Biol. Health Informatics; 2018. p. 63\u201372.","DOI":"10.1145\/3233547.3233584"},{"key":"188_CR37","doi-asserted-by":"crossref","unstructured":"Karpov N, Malikic S, Rahman MK, Sahinalp SC. A multi-labeled tree dissimilarity measure for comparing \u201cclonal trees\u201d of tumor progression. Algorithms Mol Biol. 2019;14(1):17.","DOI":"10.1186\/s13015-019-0152-9"},{"issue":"1","key":"188_CR38","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01908061","volume":"2","author":"WH Day","year":"1985","unstructured":"Day WH. Optimal algorithms for comparing trees with labeled leaves. J Classif. 1985;2(1):7\u201328.","journal-title":"J Classif."},{"issue":"4","key":"188_CR39","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1006\/jtbi.1996.0188","volume":"182","author":"M Li","year":"1996","unstructured":"Li M, Tromp J, Zhang L. On the nearest neighbour interchange distance between evolutionary trees. J Theor Biol. 1996;182(4):463\u20137.","journal-title":"J Theor Biol."},{"issue":"2","key":"188_CR40","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1006\/jagm.1999.1010","volume":"32","author":"M Li","year":"1999","unstructured":"Li M, Zhang L. Twist-rotation transformations of binary trees and arithmetic expressions. J Algorithms. 1999;32(2):155\u201366.","journal-title":"J Algorithms."},{"key":"188_CR41","first-page":"126","volume":"42","author":"M Steel","year":"1993","unstructured":"Steel M, Penny D. Distributions of tree comparison metrics-some new results. Syst Biol. 1993;42:126\u201341.","journal-title":"Systematic Biology."},{"issue":"11","key":"188_CR42","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1101\/gr.220707.117","volume":"27","author":"J Kuipers","year":"2017","unstructured":"Kuipers J, Jahn K, Raphael BJ, Beerenwinkel N. Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors. Genome Res. 2017;27(11):1885\u201394.","journal-title":"Genome Research."},{"key":"188_CR43","unstructured":"El-Kebir M. OncoLib: Library for tumor heterogeneity. GitHub repository. 2018."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00188-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-021-00188-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-021-00188-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,10]],"date-time":"2021-06-10T12:03:47Z","timestamp":1623326627000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-021-00188-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,10]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["188"],"URL":"https:\/\/doi.org\/10.1186\/s13015-021-00188-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.05.31.109892","asserted-by":"object"}]},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,10]]},"assertion":[{"value":"1 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This research did not involve any human subjects, human material, or human data. The ethics approval is not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"9"}}