×

Folding and unfolding phylogenetic trees and networks. (English) Zbl 1348.05200

Summary: Phylogenetic networks are rooted, labelled directed acyclic graphs which are commonly used to represent reticulate evolution. There is a close relationship between phylogenetic networks and multi-labelled trees (MUL-trees). Indeed, any phylogenetic network \(N\) can be “unfolded” to obtain a MUL-tree \(U(N)\) and, conversely, a MUL-tree \(T\) can in certain circumstances be “folded” to obtain a phylogenetic network \(F(T)\) that exhibits \(T\). In this paper, we study properties of the operations \(U\) and \(F\) in more detail. In particular, we introduce the class of stable networks, phylogenetic networks \(N\) for which \(F(U(N))\) is isomorphic to \(N\), characterise such networks, and show that they are related to the well-known class of tree-sibling networks. We also explore how the concept of displaying a tree in a network \(N\) can be related to displaying the tree in the MUL-tree \(U(N)\). To do this, we develop a phylogenetic analogue of graph fibrations. This allows us to view \(U(N)\) as the analogue of the universal cover of a digraph, and to establish a close connection between displaying trees in \(U(N)\) and reconciling phylogenetic trees with networks.

MSC:

05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C90 Applications of graph theory
92D15 Problems related to evolution

Software:

PADRE; PhyloNetwork
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Boldi P, Vigna S (2002) Fibrations of graphs. Discrete Math 243(1):21-66 · Zbl 0988.05073
[2] Cardona G, Llabrés M, Rosselló F, Valiente G (2008) A distance metric for a class of tree-sibling phylogenetic networks. Bioinformatics 24(13):1481-1488
[3] Cardona G, Rossello F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Trans Comput Biol Bioinf (TCBB) 6(4):552-569
[4] Gusfield D (2014) ReCombinatorics: the algorithmics of ancestral recombination graphs and explicit phylogenetic networks. MIT Press, Cambridge · Zbl 1316.92001
[5] Huber K, Moulton V (2006) Phylogenetic networks from multi-labelled trees. J Math Biol 52(5):613-632 · Zbl 1110.92027
[6] Huber KT, Moulton V, Spillner A, Storandt S, Suchecki R (2012) Computing a consensus of multilabeled trees. In: Proceedings of the meeting on algorithm engineering & experiments (ALENEX 12), SIAM, pp 84-92 · Zbl 1430.68473
[7] Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, Cambridge
[8] Kanj I, Nakhleh L, Than C, Xia G (2008) Seeing the trees and their branches in the network is hard. Theor Comput Sci 401(1):153-164 · Zbl 1147.68059
[9] Lott M, Spillner A, Huber KT, Petri A, Oxelman B, Moulton V (2009) Inferring polyploid phylogenies from multiply-labeled gene trees. BMC Evol Biol 9(1):216
[10] Marcussen T, Heier L, Brysting AK, Oxelman B, Jakobsen KS (2015) From gene trees to a dated allopolyploid network: insights from the angiosperm genus viola (violaceae). Syst Biol 64(1):84-101
[11] Pardi F, Scornavacca C (2015) Reconstructible phylogenetic networks: do not distinguish the indistinguishable. PLoS Comput Biol 11(4):e1004,135
[12] Semple C, Steel M (2003) Phylogenetics. Oxford University Press, Oxford · Zbl 1043.92026
[13] van Iersel L, Semple C, Steel M (2010) Locating a tree in a phylogenetic network. Inf Process Lett 110:1037-1043 · Zbl 1379.68184
[14] Willson S (2012) CSD homomorphisms between phylogenetic networks. IEEE/ACM Trans Comput Biol Bioinf (TCBB) 9(4):1128-1138
[15] Wu T, Zhang L (2011) Structural properties of the reconciliation space and their applications in enumerating nearly-optimal reconciliations between a gene tree and a species tree. BMC Bioinf 12(Suppl 9):S7
[16] Zhang L, Ng YK, Wu T, Zheng Y (2011) Network model and efficient method for detecting relative duplications or horizontal gene transfers. In: 2011 IEEE 1st international conference on computational advances in bio and medical sciences (ICCABS). IEEE, pp 214-219
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.