title: Approximating metrics with planar boundary-labeled phylogenetic networks.
abstract: Phylogenetic networks are useful for visualizing evolutionary relationships between species with reticulate events such as hybridizations and horizontal gene transfers. In this paper, we consider the problem of constructing undirected phylogenetic networks that (1) are planar graphs and (2) admit embeddings in the plane where the vertices labeling all taxa are on the boundary of the network. We develop a new algorithm for constructing phylogenetic networks satisfying these constraints. First, we show that only approximate networks can be constructed for some distance matrices with at least five taxa. Then we prove that any five-point metric can be represented approximately by a planar boundary-labeled network with guaranteed fit value of 94.79. We extend the networks constructed in the proof to design an algorithm for computing planar boundary-labeled networks for any number of taxa.
authors: Department of Computer Science, University of Texas at Dallas, Box 830688, Richardson, TX 75083, USA. rxs077000@utdallas.edu
authors: Ruogu
authors: R
authors: Sheng
authors: Sergey
authors: S
authors: Bereg
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D022761:Gene Transfer, Horizontal; D006801:Humans; D010802:Phylogeny