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.
Online Encyclopedia of Integer Sequences:
Number of labeled series-reduced dyslexic planted planar trees (root unlabeled) with n leaves.Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.
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.