Convexity in tree spaces

Bo Lin; Bernd Sturmfels; Xiaoxian Tang; Ruriko Yoshida

doi:10.1137/16M1079841

Convexity in tree spaces

Bo Lin
, Bernd Sturmfels
, Xiaoxian Tang
, Ruriko Yoshida

University of California at Berkeley
Texas A&M University
Naval Postgraduate School

Research output: Contribution to journal › Article › peer-review

36 Scopus citations

Abstract

We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0) metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the OwenProvan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.

Original language	English
Pages (from-to)	2015-2038
Number of pages	24
Journal	SIAM Journal on Discrete Mathematics
Volume	31
Issue number	3
DOIs	https://doi.org/10.1137/16M1079841
State	Published - 2017
Externally published	Yes

Keywords

Billera-Holmes-Vogtman metric
CAT(0) space
Geodesic triangle
Phylogenetic tree
Polytope
Tropical convexity
Ultrametric

Access to Document

10.1137/16M1079841

Cite this

@article{118b5800daff434fba6c1a7b01b5913b,

title = "Convexity in tree spaces",

abstract = "We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0) metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the OwenProvan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.",

keywords = "Billera-Holmes-Vogtman metric, CAT(0) space, Geodesic triangle, Phylogenetic tree, Polytope, Tropical convexity, Ultrametric",

author = "Bo Lin and Bernd Sturmfels and Xiaoxian Tang and Ruriko Yoshida",

note = "Publisher Copyright: {\textcopyright} 2017 Society for Industrial and Applied Mathematics.",

year = "2017",

doi = "10.1137/16M1079841",

language = "英语",

volume = "31",

pages = "2015--2038",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

T1 - Convexity in tree spaces

AU - Lin, Bo

AU - Sturmfels, Bernd

AU - Tang, Xiaoxian

AU - Yoshida, Ruriko

PY - 2017

Y1 - 2017

N2 - We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0) metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the OwenProvan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.

AB - We study the geometry of metrics and convexity structures on the space of phylogenetic trees, which is here realized as the tropical linear space of all ultrametrics. The CAT(0) metric of Billera-Holmes-Vogtman arises from the theory of orthant spaces. While its geodesics can be computed by the OwenProvan algorithm, geodesic triangles are complicated. We show that the dimension of such a triangle can be arbitrarily high. Tropical convexity and the tropical metric exhibit properties that are desirable for geometric statistics, such as geodesics of small depth.

KW - Billera-Holmes-Vogtman metric

KW - CAT(0) space

KW - Geodesic triangle

KW - Phylogenetic tree

KW - Polytope

KW - Tropical convexity

KW - Ultrametric

UR - https://www.scopus.com/pages/publications/85031731980

U2 - 10.1137/16M1079841

DO - 10.1137/16M1079841

M3 - 文章

AN - SCOPUS:85031731980

SN - 0895-4801

VL - 31

SP - 2015

EP - 2038

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 3

ER -

Convexity in tree spaces

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this