{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T22:45:30Z","timestamp":1774478730154,"version":"3.50.1"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1622369"],"award-info":[{"award-number":["1622369"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1916037"],"award-info":[{"award-number":["1916037"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the behavior of phylogenetic tree shapes in the tropical geometric interpretation of tree space. Tree shapes are formally referred to as tree topologies; a tree topology can also be thought of as a tree combinatorial type, which is given by the tree\u2019s branching configuration and leaf labeling. We use the tropical line segment as a framework to define notions of variance as well as invariance of tree topologies: we provide a combinatorial search theorem that describes all tree topologies occurring along a tropical line segment, as well as a setting under which tree topologies do not change along a tropical line segment. Our study is motivated by comparison to the moduli space endowed with a geodesic metric proposed by Billera, Holmes, and Vogtmann (referred to as BHV space); we consider the tropical geometric setting as an alternative framework to BHV space for sets of phylogenetic trees. We give an algorithm to compute tropical line segments which is lower in computational complexity than the fastest method currently available for BHV geodesics and show that its trajectory behaves more subtly: while the BHV geodesic traverses the origin for vastly different tree topologies, the tropical line segment bypasses it.<\/jats:p>","DOI":"10.1007\/s00454-022-00410-y","type":"journal-article","created":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T22:26:13Z","timestamp":1657664773000},"page":"817-849","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Tropical Geometric Variation of Tree Shapes"],"prefix":"10.1007","volume":"68","author":[{"given":"Bo","family":"Lin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6774-8150","authenticated-orcid":false,"given":"Anthea","family":"Monod","sequence":"additional","affiliation":[]},{"given":"Ruriko","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,12]]},"reference":[{"issue":"12","key":"410_CR1","doi-asserted-by":"publisher","first-page":"3261","DOI":"10.1016\/j.laa.2011.06.009","volume":"435","author":"M Akian","year":"2011","unstructured":"Akian, M., Gaubert, S., Ni\u0163ic\u0103, V., Singer, I.: Best approximation in max-plus semimodules. Linear Algebra Appl. 435(12), 3261\u20133296 (2011)","journal-title":"Linear Algebra Appl."},{"issue":"9","key":"410_CR2","doi-asserted-by":"publisher","first-page":"1320","DOI":"10.1016\/j.aml.2009.03.003","volume":"22","author":"R Alberich","year":"2009","unstructured":"Alberich, R., Cardona, G., Rossell\u00f3, F., Valiente, G.: An algebraic metric for phylogenetic trees. Appl. Math. Lett. 22(9), 1320\u20131324 (2009)","journal-title":"Appl. Math. Lett."},{"issue":"1","key":"410_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"BL Allen","year":"2001","unstructured":"Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1\u201315 (2001)","journal-title":"Ann. Combin."},{"issue":"2","key":"410_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.aam.2006.10.002","volume":"40","author":"ES Allman","year":"2008","unstructured":"Allman, E.S., Rhodes, J.A.: Phylogenetic ideals and varieties for the general Markov model. Adv. Appl. Math. 40(2), 127\u2013148 (2008)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"410_CR5","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s00026-004-0227-1","volume":"8","author":"F Ardila","year":"2004","unstructured":"Ardila, F.: Subdominant matroid ultrametrics. Ann. Combin. 8(4), 379\u2013389 (2004)","journal-title":"Ann. Combin."},{"issue":"1","key":"410_CR6","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.jctb.2005.06.004","volume":"96","author":"F Ardila","year":"2006","unstructured":"Ardila, F., Klivans, C.J.: The Bergman complex of a matroid and phylogenetic trees. J. Combin. Theory Ser. B 96(1), 38\u201349 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"1","key":"410_CR7","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0001-8708(92)90061-O","volume":"92","author":"H-J Bandelt","year":"1992","unstructured":"Bandelt, H.-J., Dress, A.W.M.: A canonical decomposition theory for metrics on a finite set. Adv. Math. 92(1), 47\u2013105 (1992)","journal-title":"Adv. Math."},{"issue":"1","key":"410_CR8","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1137\/18M1218741","volume":"34","author":"DI Bernstein","year":"2020","unstructured":"Bernstein, D.I.: L-infinity optimization to Bergman fans of matroids with an application to phylogenetics. SIAM J. Discret. Math. 34(1), 701\u2013720 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"410_CR9","doi-asserted-by":"publisher","first-page":"875","DOI":"10.1137\/16M1101027","volume":"31","author":"DI Bernstein","year":"2017","unstructured":"Bernstein, D.I., Long, C.: L-infinity optimization to linear spaces and phylogenetic trees. SIAM J. Discret. Math. 31(2), 875\u2013889 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"410_CR10","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1006\/aama.2001.0759","volume":"27","author":"LJ Billera","year":"2001","unstructured":"Billera, L.J., Holmes, S.P., Vogtmann, K.: Geometry of the space of phylogenetic trees. Adv. Appl. Math. 27(4), 733\u2013767 (2001)","journal-title":"Adv. Appl. Math."},{"key":"410_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","volume":"17","author":"P Buneman","year":"1974","unstructured":"Buneman, P.: A note on the metric properties of trees. J. Combin. Theory Ser. B 17, 48\u201350 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"410_CR12","doi-asserted-by":"crossref","unstructured":"Cardona, G., Mir, A., Rossell\u00f3, F., Rotger, L., S\u00e1nchez,\u00a0D.: Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf. BMC Bioinform. 14, #\u00a03 (2013)","DOI":"10.1186\/1471-2105-14-3"},{"key":"410_CR13","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.laa.2003.08.010","volume":"379","author":"G Cohen","year":"2004","unstructured":"Cohen, G., Gaubert, S., Quadrat, J.-P.: Duality and separation theorems in idempotent semimodules. Linear Algebra Appl. 379, 395\u2013422 (2004)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"410_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1093\/sysbio\/syx046","volume":"67","author":"C Colijn","year":"2018","unstructured":"Colijn, C., Plazzotta, G.: A metric on phylogenetic tree shapes. Syst. Biol. 67(1), 113\u2013126 (2018)","journal-title":"Syst. Biol."},{"issue":"3","key":"410_CR15","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/0001-8708(84)90029-X","volume":"53","author":"AWM Dress","year":"1984","unstructured":"Dress, A.W.M.: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces. Adv. Math. 53(3), 321\u2013402 (1984)","journal-title":"Adv. Math."},{"issue":"6","key":"410_CR16","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1007\/BF01734359","volume":"17","author":"J Felsenstein","year":"1981","unstructured":"Felsenstein, J.: Evolutionary trees from DNA sequences: a maximum likelihood approach. J. Mol. Evol. 17(6), 368\u2013376 (1981)","journal-title":"J. Mol. Evol."},{"issue":"4","key":"410_CR17","doi-asserted-by":"publisher","first-page":"406","DOI":"10.2307\/2412116","volume":"20","author":"WM Fitch","year":"1971","unstructured":"Fitch, W.M.: Toward defining the course of evolution: minimum change for a specific tree topology. Syst. Zool. 20(4), 406\u2013416 (1971)","journal-title":"Syst. Zool."},{"issue":"1","key":"410_CR18","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"LR Foulds","year":"1982","unstructured":"Foulds, L.R., Graham, R.L.: The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math. 3(1), 43\u201349 (1982)","journal-title":"Adv. Appl. Math."},{"issue":"1","key":"410_CR19","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/S0040-5809(02)00005-9","volume":"63","author":"S Holmes","year":"2003","unstructured":"Holmes, S.: Statistics for phylogenetic trees. Theor. Popul. Biol. 63(1), 17\u201332 (2003)","journal-title":"Theor. Popul. Biol."},{"issue":"2","key":"410_CR20","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0025-5564(67)90032-6","volume":"1","author":"CJ Jardine","year":"1967","unstructured":"Jardine, C.J., Jardine, N., Sibson, R.: The structure and construction of taxonomic hierarchies. Math. Biosci. 1(2), 173\u2013179 (1967)","journal-title":"Math. Biosci."},{"issue":"4","key":"410_CR21","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s12532-018-0135-8","volume":"10","author":"D Juhl","year":"2018","unstructured":"Juhl, D., Warme, D.M., Winter, P., Zachariasen, M.: The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study. Math. Program. Comput. 10(4), 487\u2013532 (2018)","journal-title":"Math. Program. Comput."},{"issue":"4","key":"410_CR22","doi-asserted-by":"publisher","first-page":"1461","DOI":"10.1093\/genetics\/156.4.1461","volume":"156","author":"JFC Kingman","year":"2000","unstructured":"Kingman, J.F.C.: Origins of the coalescent: 1974\u20131982. Genetics 156(4), 1461\u20131463 (2000)","journal-title":"Genetics"},{"key":"410_CR23","doi-asserted-by":"crossref","unstructured":"Knowles, L.L.: Statistical phylogeography. Ann. Rev. Ecol. Evol. Syst. 40, 593\u2013612 (2009)","DOI":"10.1146\/annurev.ecolsys.38.091206.095702"},{"key":"410_CR24","doi-asserted-by":"crossref","unstructured":"Lee, W., Li, W., Lin, B., Monod, A.: Tropical optimal transport and Wasserstein distances. Inf. Geom. (2021). https:\/\/link.springer.com\/article\/10.1007\/s41884-021-00046-6","DOI":"10.1007\/s41884-021-00046-6"},{"issue":"3","key":"410_CR25","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1137\/16M1079841","volume":"31","author":"B Lin","year":"2017","unstructured":"Lin, B., Sturmfels, B., Tang, X., Yoshida, R.: Convexity in tree spaces. SIAM J. Discret. Math. 31(3), 2015\u20132038 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"410_CR26","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1137\/16M1071122","volume":"32","author":"B Lin","year":"2018","unstructured":"Lin, B., Yoshida, R.: Tropical Fermat\u2013Weber points. SIAM J. Discret. Math. 32(2), 1229\u20131245 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"410_CR27","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.aam.2014.12.003","volume":"64","author":"C Long","year":"2015","unstructured":"Long, C., Sullivant, S.: Identifiability of $$3$$-class Jukes\u2013Cantor mixtures. Adv. Appl. Math. 64, 89\u2013110 (2015)","journal-title":"Adv. Appl. Math."},{"key":"410_CR28","doi-asserted-by":"crossref","unstructured":"Maclagan, D., Sturmfels, B.: Introduction to Tropical Geometry. Graduate Studies in Mathematics, vol. 161. American Mathematical Society, Providence (2015)","DOI":"10.1090\/gsm\/161"},{"key":"410_CR29","unstructured":"Monod, A., Lin, B., Yoshida, R., Kang, Q.: Tropical geometry of phylogenetic tree space: a statistical perspective (2018). arXiv:1805.12400"},{"key":"410_CR30","doi-asserted-by":"crossref","unstructured":"Munch, E., Stefanou, A.: The $$\\ell ^\\infty $$-cophenetic metric for phylogenetic trees as an interleaving distance. In: Research in Data Science (Providence 2017). Association for Women in Mathematics Series, vol. 17, pp. 109\u2013127. Springer, Cham (2019)","DOI":"10.1007\/978-3-030-11566-1_5"},{"issue":"1","key":"410_CR31","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TCBB.2010.3","volume":"8","author":"M Owen","year":"2011","unstructured":"Owen, M., Provan, J.S.: A fast algorithm for computing geodesic distances in tree space. IEEE\/ACM Trans. Comput. Biol. Bioinform. 8(1), 2\u201313 (2011)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"4","key":"410_CR32","first-page":"547","volume":"15","author":"Ch Peng","year":"2007","unstructured":"Peng, Ch.: Distance based methods in phylogenetic tree construction. Neural Parallel Sci. Comput. 15(4), 547\u2013560 (2007)","journal-title":"Neural Parallel Sci. Comput."},{"issue":"1","key":"410_CR33","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s11538-011-9672-2","volume":"74","author":"JA Rhodes","year":"2012","unstructured":"Rhodes, J.A., Sullivant, S.: Identifiability of large phylogenetic mixture models. Bull. Math. Biol. 74(1), 212\u2013231 (2012)","journal-title":"Bull. Math. Biol."},{"issue":"1\u20132","key":"410_CR34","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"DF Robinson","year":"1981","unstructured":"Robinson, D.F., Foulds, L.R.: Comparison of phylogenetic trees. Math. Biosci. 53(1\u20132), 131\u2013147 (1981)","journal-title":"Math. Biosci."},{"issue":"7","key":"410_CR35","doi-asserted-by":"publisher","first-page":"1465","DOI":"10.1111\/j.0014-3820.2003.tb00355.x","volume":"57","author":"NA Rosenberg","year":"2003","unstructured":"Rosenberg, N.A.: The shapes of neutral gene genealogies in two species: probabilities of monophyly, paraphyly, and polyphyly in a coalescent model. Evolution 57(7), 1465\u20131477 (2003)","journal-title":"Evolution"},{"key":"410_CR36","first-page":"361","volume":"15","author":"E Schr\u00f6der","year":"1870","unstructured":"Schr\u00f6der, E.: Vier combinatorische Probleme. Z. Math. Phys. 15, 361\u2013376 (1870)","journal-title":"Z. Math. Phys."},{"issue":"3","key":"410_CR37","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1515\/advg.2004.023","volume":"4","author":"D Speyer","year":"2004","unstructured":"Speyer, D., Sturmfels, B.: The tropical Grassmannian. Adv. Geom. 4(3), 389\u2013411 (2004)","journal-title":"Adv. Geom."},{"issue":"3","key":"410_CR38","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1080\/0025570X.2009.11953615","volume":"82","author":"D Speyer","year":"2009","unstructured":"Speyer, D., Sturmfels, B.: Tropical mathematics. Math. Mag. 82(3), 163\u2013173 (2009)","journal-title":"Math. Mag."},{"issue":"2","key":"410_CR39","first-page":"126","volume":"42","author":"MA Steel","year":"1993","unstructured":"Steel, M.A., Penny, D.: Distributions of tree comparison metrics: some new results. Systematic Biology 42(2), 126\u2013141 (1993)","journal-title":"Systematic Biology"},{"issue":"3","key":"410_CR40","doi-asserted-by":"publisher","first-page":"1563","DOI":"10.1214\/105051606000000196","volume":"16","author":"MA Steel","year":"2006","unstructured":"Steel, M.A., Sz\u00e9kely, L.A.: On the variational distance of two trees. Ann. Appl. Probab. 16(3), 1563\u20131575 (2006)","journal-title":"Ann. Appl. Probab."},{"key":"410_CR41","unstructured":"Tang, X., Wang, H., Yoshida, R.: Tropical support vector machine and its applications to phylogenomics (2020). arXiv:2003.00677"},{"key":"410_CR42","unstructured":"Tavar\u00e9, S.: Some probabilistic and statistical problems in the analysis of DNA sequences. In: Some Mathematical Questions in Biology\u2014DNA Sequence Analysis (New York 1984). Lectures on Mathematics in the Life Sciences, vol. 17, pp. 57\u201386. American Mathematical Society, Providence (1986)"},{"key":"410_CR43","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.ympev.2013.09.004","volume":"70","author":"Y Tian","year":"2014","unstructured":"Tian, Y., Kubatko, L.S.: Gene tree rooting methods give distributions that mimic the coalescent process. Mol. Phylogenet. Evol. 70, 63\u201369 (2014)","journal-title":"Mol. Phylogenet. Evol."},{"issue":"3","key":"410_CR44","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","volume":"20","author":"MS Waterman","year":"1976","unstructured":"Waterman, M.S., Smith, T.F., Beyer, W.A.: Some biological sequence metrics. Adv. Math. 20(3), 367\u2013387 (1976)","journal-title":"Adv. Math."},{"issue":"2","key":"410_CR45","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/s11538-018-0493-4","volume":"81","author":"R Yoshida","year":"2019","unstructured":"Yoshida, R., Zhang, L., Zhang, X.: Tropical principal component analysis and its application to phylogenetics. Bull. Math. Biol. 81(2), 568\u2013597 (2019)","journal-title":"Bull. Math. Biol."},{"key":"410_CR46","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.laa.2019.10.026","volume":"587","author":"L Yu","year":"2020","unstructured":"Yu, L.: Extreme rays of the $$\\ell ^\\infty $$-nearest ultrametric tropical polytope. Linear Algebra Appl. 587, 23\u201344 (2020)","journal-title":"Linear Algebra Appl."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00410-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-022-00410-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-022-00410-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,14]],"date-time":"2022-09-14T10:16:22Z","timestamp":1663150582000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-022-00410-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,12]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["410"],"URL":"https:\/\/doi.org\/10.1007\/s00454-022-00410-y","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,12]]},"assertion":[{"value":"26 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}