×

Level-1 phylogenetic networks and their balanced minimum evolution polytopes. (English) Zbl 1440.90021

Summary: Balanced minimum evolution is a distance-based criterion for the reconstruction of phylogenetic trees. Several algorithms exist to find the optimal tree with respect to this criterion. One approach is to minimize a certain linear functional over an appropriate polytope. Here we present polytopes that allow a similar linear programming approach to finding phylogenetic networks. We investigate a two-parameter family of polytopes that arise from phylogenetic networks, and which specialize to the Balanced Minimum Evolution polytopes as well as the Symmetric Travelling Salesman polytopes. We show that the vertices correspond to certain level-1 phylogenetic networks, and that there are facets or faces for every split. We also describe lower bound faces and a family of faces for every dimension.

MSC:

90C05 Linear programming
52B11 \(n\)-dimensional polytopes
92D15 Problems related to evolution

Software:

OEIS; polymake
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aguiar M, Ardila F (2017) Hopf monoids and generalized permutahedra. arXiv:1709.07504 [math.CO], p 1-113
[2] Brandes, U.; Cornelsen, S., Phylogenetic graph models beyond trees, Discrete Appl Math, 157, 10, 2361-2369 (2009) · Zbl 1163.92030 · doi:10.1016/j.dam.2008.06.031
[3] Bryant, D.; Moulton, V.; Andreas, S., Consistency of the neighbor-net algorithm, Algorithms Mol Biol, 2, 1, 8 (2007) · doi:10.1186/1748-7188-2-8
[4] Catanzaro, D.; Labbé, M.; Pesenti, R.; Salazar-González, Jj, The balanced minimum evolution problem, INFORMS J Comput, 24, 2, 276-294 (2012) · Zbl 1461.92066 · doi:10.1287/ijoc.1110.0455
[5] Catanzaro, D.; Aringhieri, R.; Di Summa, M.; Pesenti, R., A branch-price-and-cut algorithm for the minimum evolution problem, Eur J Oper Res, 244, 3, 753-765 (2015) · Zbl 1346.90210 · doi:10.1016/j.ejor.2015.02.019
[6] Devadoss, S.; Petti, S., A space of phylogenetic networks, SIAM J Appl Algebra Geom, 1, 683-705 (2017) · Zbl 1380.92046 · doi:10.1137/16M1103129
[7] Devadoss S, Durell C, Forcey S (2019) Split network polytopes and network spaces. In: SLC 82B, Proceedings of FPSAC 31, to appear · Zbl 1435.05050
[8] Eickmeyer, K.; Huggins, P.; Pachter, L.; Yoshida, R., On the optimality of the neighbor-joining algorithm, Algorithms Mol Biol, 3, 1, 5 (2008) · doi:10.1186/1748-7188-3-5
[9] Ewgenij, G.; Michael, J.; Kalai, G.; Ziegler, Gm, Polymake: a framework for analyzing convex polytopes, Polytopes—Combinatorics and Computation, 43-74 (2000), Basel: Birkhäuser, Basel · Zbl 0960.68182
[10] Forcey, S.; Keefe, L.; Sands, W., Facets of the balanced minimal evolution polytope, J Math Biol, 73, 2, 447-468 (2016) · Zbl 1346.90572 · doi:10.1007/s00285-015-0957-1
[11] Forcey, S.; Keefe, L.; Sands, W., Split-facets for balanced minimal evolution polytopes and the permutoassociahedron, Bull Math Biol, 79, 5, 975-994 (2017) · Zbl 1373.90072 · doi:10.1007/s11538-017-0264-7
[12] Forcey, S.; Hamerlinck, G.; Sands, W.; Robeva, R.; Macauley, M., Optimization problems in phylogenetics: polytopes, programming and interpretation, Algebraic and Combinatorial Computational Biology (2018), Cambridge: Academic Press, Cambridge
[13] Gambette, P.; Huber, Kt; Scholz, Ge, Uprooted phylogenetic networks, Bull Math Biol, 79, 9, 2022-2048 (2017) · Zbl 1372.92071 · doi:10.1007/s11538-017-0318-x
[14] Haws, D.; Hodge, T.; Yoshida, R., Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope, Bull Math Biol, 73, 11, 2627-2648 (2011) · Zbl 1334.92292 · doi:10.1007/s11538-011-9640-x.
[15] Levy, D.; Pachter, L., The neighbor-net algorithm., Adv Appl Math, 47, 240-258 (2011) · Zbl 1274.92005 · doi:10.1016/j.aam.2010.09.002
[16] Philippe, G.; Katharina, H.; Steven, K., On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters, J Math Biol, 74, 7, 1729-1751 (2017) · Zbl 1366.92087 · doi:10.1007/s00285-016-1068-3
[17] Semple, C.; Steel, M., Cyclic permutations and evolutionary trees, Adv. Appl. Math., 32, 4, 669-680 (2004) · Zbl 1050.05027 · doi:10.1016/S0196-8858(03)00098-8.
[18] Semple, C.; Steel, M., Unicyclic networks: compatibility and enumeration, IEEE/ACM Trans Comput Biol Bioinform, 3, 1, 84-91 (2006) · doi:10.1109/TCBB.2006.14
[19] Sloane NJA (2018) The On-Line Encyclopedia of Integer Sequences. published electronically at www.oeis.org. Accessed 6 Feb 2020
[20] Steel, M., Phylogeny—Discrete and Random Processes in Evolution (2016), Philadelphia: Society for Industrial and Applied Mathematics (SIAM), Philadelphia · Zbl 1361.92001
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.