Abstract
In phylogenetics, tree-based networks are used to model and visualize the evolutionary history of species where reticulate events such as horizontal gene transfer have occurred. Formally, a tree-based network N consists of a phylogenetic tree T (a rooted, binary, leaf-labeled tree) and so-called reticulation edges that span between edges of T. The network N is typically visualized by drawing T downward and planar and reticulation edges with one of several different styles. One aesthetic criteria is to minimize the number of crossings between tree edges and reticulation edges. This optimization problem has not yet been researched. We show that, if reticulation edges are drawn x-monotone, the problem is NP-complete, but fixed-parameter tractable in the number of reticulation edges. If, on the other hand, reticulation edges are drawn like “ears”, the crossing minimization problem can be solved in quadratic time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anaya, M., et al.: On determining if tree-based networks contain fixed trees. Bull. Math. Biol. 78(5), 961–969 (2016). https://doi.org/10.1007/s11538-016-0169-x
Calamoneri, T., Di Donato, V., Mariottini, D., Patrignani, M.: Visualizing co-phylogenetic reconciliations. Theoret. Comput. Sci. 815, 228–245 (2020). https://doi.org/10.1016/j.tcs.2019.12.024
Doolittle, W.F.: Phylogenetic classification and the universal tree. Science 284(5423), 2124–2128 (1999). https://doi.org/10.1126/science.284.5423.2124
Francis, A.R., Steel, M.: Which phylogenetic networks are merely trees with additional arcs? Syst. Biol. 64(5), 768–777 (2015). https://doi.org/10.1093/sysbio/syv037
Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209–221 (1985). https://doi.org/10.1016/0022-0000(85)90014-5
Garey, M.R., Johnson, D.S.: Computers and intractability, vol. 174. Freeman San Francisco (1979)
Huson, D.H.: Drawing rooted phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(1), 103–109 (2009)
Huson, D.H., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press (2010). https://doi.org/10.1093/sysbio/syr055
Jetten, L., van Iersel, L.: Nonbinary tree-based phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 15(1), 205–217 (2018). https://doi.org/10.1109/TCBB.2016.2615918
Kumar, V., et al.: The evolutionary history of bears is characterized by gene flow across species. Sci. Rep. 7(1) (2017). https://doi.org/10.1038/srep46487
Pons, J.C., Semple, C., Steel, M.: Tree-based networks: characterisations, metrics, and support trees. J. Math. Biol. 78(4), 899–918 (2018). https://doi.org/10.1007/s00285-018-1296-9
Semple, C., Steel, M.A.: Phylogenetics, vol. 24. Oxford University Press, Oxford (2003)
Steel, M.: Phylogeny: Discrete and Random Processes in Evolution. Society for Industrial and Applied Mathematics (2016)
Tollis, I.G., Kakoulis, K.G.: Algorithms for visualizing phylogenetic networks. In: Hu, Y., Nöllenburg, M. (eds.) GD 2016. LNCS, vol. 9801, pp. 183–195. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50106-2_15
Vaughan, T.G., Welch, D., Drummond, A.J., Biggs, P.J., George, T., French, N.P.: Inferring ancestral recombination graphs from bacterial genomic data. Genetics 205(2), 857–870 (2017). https://doi.org/10.1534/genetics.116.193425
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Klawitter, J., Stumpf, P. (2020). Drawing Tree-Based Phylogenetic Networks with Minimum Number of Crossings. In: Auber, D., Valtr, P. (eds) Graph Drawing and Network Visualization. GD 2020. Lecture Notes in Computer Science(), vol 12590. Springer, Cham. https://doi.org/10.1007/978-3-030-68766-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-030-68766-3_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68765-6
Online ISBN: 978-3-030-68766-3
eBook Packages: Computer ScienceComputer Science (R0)