×

A space of phylogenetic networks. (English) Zbl 1380.92046

Summary: A classical problem in computational biology is constructing a phylogenetic tree given a set of distances between \(n\) species. In many cases, a tree structure is too constraining. We consider a split network, which is a generalization of a tree in which multiple parallel edges signify divergence. A geometric space of such networks is introduced, forming a natural extension of the familiar space of phylogenetic trees. We explore properties of the space of networks and construct a natural embedding of the compactification of the real moduli space of curves within it.

MSC:

92D15 Problems related to evolution
05C90 Applications of graph theory
92-08 Computational methods for problems pertaining to biology
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] H.-J. Bandelt and A. Dress, {\it Split decomposition: A new and useful approach to phylogenetic analysis of distance data}, Mol. Phylogenetics Evol., 1 (1992), pp. 242-252.
[2] M. Bridson and A. Häfliger, {\it Metric Spaces of Non-positive Curvature}, Springer-Verlag, Berlin, 1999. · Zbl 0988.53001
[3] 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
[4] D. Bryant and V. Moulton, {\it Neighbor-net: An agglomerative method for the construction of phylogenetic networks}, Mol. Biol. Evol., 21 (2004), pp. 255-265.
[5] P. Buneman, {\it A note on the metric properties of trees}, J. Combinatorial Theory Ser. B, 17 (1974), pp. 48-50. · Zbl 0286.05102
[6] M. Davis, T. Januszkiewicz, and R. Scott, {\it Nonpositive curvature of blowups}, Selecta Math., 4 (1998), pp. 491-547. · Zbl 0924.53033
[7] S. Devadoss, {\it Tessellations of moduli spaces and the mosaic operad}, in Homotopy Invariant Algebraic Structures, Contemp. Math. 239, AMS, Providence, RI, 1999, pp. 91-114. · Zbl 0968.32009
[8] S. Devadoss, {\it Combinatorial equivalence of real moduli spaces}, Notices Amer. Math. Soc., 51 (2004), pp. 620-628. · Zbl 1093.14509
[9] S. Devadoss and J. Morava, {\it Navigation in tree spaces}, Adv. Appl. Math., 67 (2015), pp. 75-95. · Zbl 1349.14111
[10] P. Diaconis and S. Holmes, {\it Matchings and phylogenetic trees}, Proc. Natl. Acad. Sci. USA, 95 (1998), pp. 14600-14602. · Zbl 0908.92023
[11] K. Fukaya, Y.-G. Oh, H. Ohta, and K. Ono, {\it Lagrangian Intersection Floer Theory: Anomaly and Obstruction}, AMS, Providence, RI, 2010. · Zbl 1181.53002
[12] P. Gambette and D. Huson, {\it Improved layout of phylogenetic networks}, IEEE/ACM Trans. Comput. Biol. Bioinform., 5 (2008), pp. 1-8.
[13] A. Goncharov and Y. Manin, {\it Multiple \(ζ\)-motives and moduli spaces \CMn}, Compos. Math., 140 (2004), pp. 1-14. · Zbl 1047.11063
[14] P. Hacking, S. Keel, and J. Tevelev, {\it Stable pair, tropical, and log canonical compactifications of moduli spaces of del Pezzo surfaces}, Invent. Math., 178 (2009), pp. 173-227. · Zbl 1205.14012
[15] K. Huber, V. Moulton, and T. Wu, {\it Transforming phylogenetic networks: Moving beyond tree space}, J. Theoret. Biol., 404 (2016), pp. 30-39. · Zbl 1343.92348
[16] D. Huson and D. Bryant, {\it Application of phylogenetic networks in evolutionary studies}, Mol. Biol. Evol., 23 (2006), pp. 254-267.
[17] D. Huson and C. Scornavacca, {\it A survey of combinatorial methods for phylogenetic networks}, Genome Biol. Evol., 3 (2010), pp. 23-35.
[18] D. Huson, R. Rupp, and C. Scornavacca, {\it Phylogenetic Networks}, Cambridge University Press, New York, 2010.
[19] M. Kapranov, {\it The permutoassociahedron, MacLane’s coherence theorem, and asymptotic zones for the \(KZ\) equation}, J. Pure Appl. Algebra, 85 (1993), pp. 119-142. · Zbl 0812.18003
[20] C. Lee, {\it The associahedron and triangulations of the \(n\)-gon}, European J. Combin., 10 (1989), pp. 551-560. · Zbl 0682.52004
[21] D. Levy and L. Pachter, {\it The neighbor-net algorithm}, Adv. Appl. Math., 47 (2011), pp. 240-258. · Zbl 1274.92005
[22] 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
[23] E. Miller, M. Owen, and S. Provan, {\it Polyhedral computational geometry for averaging metric phylogenetic trees}, Adv. Appl. Math., 68 (2015), pp. 51-91. · Zbl 1329.68266
[24] D. Mumford, J. Fogarty, and F. Kirwan, {\it Geometric Invariant Theory}, Springer-Verlag, New York, 1994. · Zbl 0797.14004
[25] M. Owen, {\it Computing geodesic distances in tree space}, SIAM J. Discrete Math., 25 (2011), pp. 1506-1529, . · Zbl 1237.05045
[26] N. Saitou and M. Nei, {\it The neighbor-joining method: A new method for reconstructing phylogenetic trees}, Mol. Biol. Evol., 4 (1987), pp. 406-425.
[27] J. Sekiguchi and M. Yoshida, {\it \(W(E_6)\)-action on the configuration space of six lines on the real projective plane}, Kyushu J. Math., 51 (1997), pp. 297-354. · Zbl 0932.14027
[28] C. Semple and M. Steel, {\it Phylogenetics}, Oxford University Press, London, 2003. · Zbl 1043.92026
[29] D. Speyer and B. Sturmfels, {\it The tropical Grassmannian}, Adv. Geom., 4 (2004), pp. 389-411. · Zbl 1065.14071
[31] R. Stanley, {\it Enumerative Combinatorics}, Vol. 2, Cambridge University Press, Cambridge, UK, 1999. · Zbl 0928.05001
[32] J. Stasheff, {\it Homotopy associativity of \(H\)-spaces}, Trans. Amer. Math. Soc., 108 (1963), pp. 275-292. · Zbl 0114.39402
[33] K. Vogtmann, {\it Local structures of some out \((F_n)\)-complexes}, Proc. Edinburgh Math. Soc., 33 (1990), pp. 367-379. · Zbl 0694.20021
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.