×

Tropical Fermat-Weber points. (English) Zbl 1420.14148

Summary: In a metric space, the Fermat-Weber points of a sample are statistics to measure the central tendency of the sample and it is well known that the Fermat-Weber point of a sample is not necessarily unique in the metric space. We investigate the computation of Fermat-Weber points under the tropical metric on the quotient space \(\mathbb{R}^{n} / \mathbb{R} {1}\) with a fixed \(n \in \mathbb{N}\), motivated by its application to the space of equidistant phylogenetic trees with \(N\) leaves (in this case \(n=\binom{N}{2}\)) realized as the tropical linear space of all ultrametrics. We show that the set of all tropical Fermat-Weber points of a finite sample is always a classical convex polytope, and we present a combinatorial formula for a key value associated with this set. We identify conditions under which this set is a singleton. We apply numerical experiments to analyze the set of the tropical Fermat-Weber points within a space of phylogenetic trees. We discuss the issues in the computation of the tropical Fermat-Weber points.

MSC:

14T05 Tropical geometry (MSC2010)
92B05 General biology and biomathematics
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
52B11 \(n\)-dimensional polytopes
92B15 General biostatistics

Software:

Maple; ape; polymake
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] M. Akian, S. Gaubert, V. Niţică, and I. Singer, {\it Best approximation in max-plus semimodules}, Linear Algebra Appl., 435 (2011), pp. 3261-3296. · Zbl 1226.15016
[2] L. Bernardin, P. Chin, P. DeMarco, K. O. Geddes, D. E. G. Hare, K. M. Heal, G. Labahn, J. P. May, J. McCarron, M. B. Monagan, D. Ohashi, and S. M. Vorkoetter, {\it Maple 2015 Programming Guide}, Maplesoft, Waterloo, ON, Canada, 2015.
[3] D. I. Bernstein and C. Long, {\it L-infinity optimization to linear spaces and phylogenetic trees}, SIAM J. Discrete Math., 31 (2017), pp. 875-889. · Zbl 1362.92050
[4] R. Betancur, C. Li, T. Munroe, J. Ballesteros, and G. Ortí, {\it Addressing gene tree discordance and non-stationarity to resolve a multi-locus phylogeny of the flatfishes (teleostei: Pleuronectiformes)}, Systemat. Biol., 62 (2013), pp. 763-785, .
[5] L. Billera, S. Holmes, and K. Vogtmann, {\it Geometry of the space of phylogenetic trees}, Adv. Appl. Math., 27 (2001), pp. 733-767. · Zbl 0995.92035
[6] M. Carling and R. Brumfield, {\it Integrating phylogenetic and population genetic analyses of multiple loci to test species divergence hypotheses in {\it passerina} buntings}, Genetics, 178 (2008), pp. 363-377.
[7] D. Cieslik, {\it Shortest Connectivity: An Introduction with Applications in Phylogeny}, Combin. Optim. 17, Springer, New York, 2005. · Zbl 1086.92037
[8] G. Cohen, S. Gaubert, and J. Quadrat, {\it Duality and separation theorems in idempotent semimodules}, Linear Algebra Appl., 379 (2004), pp. 395-422. · Zbl 1042.46004
[9] E. Gawrilow and M. Joswig, {\it polymake: a framework for analyzing convex polytopes}, in Polytopes–Combinatorics and Computation, G. Kalai and G. M. Ziegler, eds., Birkhäuser, Basel, 2000, pp. 43-74. · Zbl 0960.68182
[10] P. Hall, {\it On representatives of subsets}, J. London Math. Soc. (1), 10 (1935), pp. 26-30. · JFM 61.0067.01
[11] J. Heled and A. Drummond, {\it Bayesian inference of species trees from multilocus data}, Mol. Biol. Evol., 27 (2011), pp. 570-580.
[12] B. Lin, B. Sturmfels, X. Tang, and R. Yoshida, {\it Convexity in tree spaces}, SIAM J. Discrete Math., 31 (2017), pp. 2015-2038. · Zbl 1370.05040
[13] D. Maclagan and B. Sturmfels, {\it Introduction to Tropical Geometry}, Grad. Stud. Math. 161, AMS, Providence, RI, 2015. · Zbl 1321.14048
[14] F. Nielsen and R. Bhatia, {\it Matrix Information Geometry}, Springer, Berlin, 2012.
[15] E. Paradis, J. Claude, and K. Strimmer, {\it APE: Analyses of phylogenetics and evolution in R language}, Bioinformatics, 20 (2004), pp. 289-290.
[16] D. Speyer and B. Sturmfels, {\it The tropical Grassmannian}, Adv. Geom., 4 (2004), pp. 389-411. · Zbl 1065.14071
[17] K. Thompson and L. Kubatko, {\it Using ancestral information to detect and localize quantitative trait loci in genome-wide association studies}, BMC Bioinform., 14 (2013), 200.
[18] Y. Yu, T. Warnow, and L. Nakhleh, {\it Algorithms for MDC-based multi-locus phylogeny inference: Beyond rooted binary gene trees on single alleles}, J. Comput. Biol., 18 (2011), pp. 1543-1559.
[19] G. M. Ziegler, {\it Lectures on Polytopes}, Grad. Texts in Math. 152, Springer, New York, 1995.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.