×

Comparing and simplifying distinct-cluster phylogenetic networks. (English) Zbl 1361.92054

Summary: Phylogenetic networks are rooted acyclic directed graphs in which the leaves are identified with members of a set \(X\) of species. The cluster of a vertex is the set of leaves that are descendants of the vertex. A network is “distinct-cluster” if distinct vertices have distinct clusters. This paper focuses on the set \(DC(X)\) of distinct-cluster networks whose leaves are identified with the members of \(X\). For a fixed X, a metric on \(DC(X)\) is defined. There is a “cluster-preserving” simplification process by which vertices or certain arcs may be removed without changing the clusters of any remaining vertices. Many of the resulting networks may be uniquely determined without regard to the order of the simplifying operations.

MSC:

92D15 Problems related to evolution
05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C90 Applications of graph theory

Software:

PhyloNetwork
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allen B., Steel M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Combin. 5(1), 1-15 (2001) · Zbl 0978.05023 · doi:10.1007/s00026-001-8006-8
[2] Baroni M., Semple C., Steel M.: A framework for representing reticulate evolution. Ann. Combin. 8(4), 391-408 (2004) · Zbl 1059.05034 · doi:10.1007/s00026-004-0228-0
[3] Boucher Y., Douady C.J., Papke R.T., Walsh D.A., Boudreau M.E.R., Nesbo C.L., Case R.J., Doolittle W.F.: Lateral gene transfer and the origins of prokaryotic groups. Ann. Rev. Genet. 37, 283-328 (2003) · doi:10.1146/annurev.genet.37.050503.084247
[4] Cardona G., Labrés M., Rossalló F., Valiente G.: A distance metric for a class of treesibling phylogenetic networks. Bioinform. 24(13), 1481-1488 (2008) · doi:10.1093/bioinformatics/btn231
[5] Cardona G., Labrés M., Rossalló F., Valiente G.: On Nakhleh’s metric for reduced phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 629-638 (2009) · doi:10.1109/TCBB.2009.33
[6] Cardona G., Labrés M., Rossalló F., Valiente G.: Metrics for phylogenetic networks I: generalizations of the Robinson-Foulds metric. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(1), 46-61 (2009) · doi:10.1109/TCBB.2008.70
[7] Cardona G., Rossalló F., Valiente G.: Comparison of tree-child phylogenetic networks. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 552-569 (2009) · doi:10.1109/TCBB.2007.70270
[8] Critchlow D., Pearl D., Qian C.: The triples distance for rooted bifurcating phylogenetic trees. Syst. Biol. 45(3), 323-334 (1996) · doi:10.1093/sysbio/45.3.323
[9] Doolittle W.F., Bapteste E.: Pattern pluralism and the tree of life hypothesis. Proc. Natl. Acad. Sci. USA 104(7), 2043-2049 (2007) · doi:10.1073/pnas.0610699104
[10] Gusfield D., Eddhu S., Langley C.: The fine structure of galls in phylogenetic networks. INFORMS J. Comput. 16(4), 459-469 (2004) · Zbl 1402.92313 · doi:10.1287/ijoc.1040.0099
[11] Harary, F.: Graph Theory. Addison-Wesley, Reading, Mass. (1969) · Zbl 0182.57702
[12] Huson D., Rupp R., Scornavacca C.: Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, Cambridge (2010) · doi:10.1017/CBO9780511974076
[13] Lin Y., Rajan V., Moret B.: A metric for phylogenetic trees based on matching. IEEE/ACM Trans. Comput. Biol. Bioinform. 9(4), 1014-1022 (2012) · doi:10.1109/TCBB.2011.157
[14] Mindell D.: The tree of life: metaphor, model, and heuristic Device. Syst. Biol. 62(3), 479-489 (2013) · doi:10.1093/sysbio/sys115
[15] Moret B., Nakhleh L., Warnow T., Linder C.R., Tholse A., Padolina A., Sun J., Timme R.: Phylogenetic networks: modeling, reconstructibility, and accuracy. IEEE Trans. Comput. Biol. Bioinform. 1(1), 13-23 (2004) · doi:10.1109/TCBB.2004.10
[16] Morrison, D.: Introduction to Phylogenetic Networks. RJR Productions, Uppsala, Sweden (2011) http://www.rjr-productions.org/
[17] Nakhleh L., Warnow T., Linder C.R., John K.: Reconstructing reticulate evolution in species — theory and practice. J. Comput. Biol. 12(5), 796-811 (2005) · doi:10.1089/cmb.2005.12.796
[18] Rhymer J., Symberloff D.: Extinction by hybridization and introgression. Ann. Rev. Ecol. Syst. 27, 83-109 (1996) · doi:10.1146/annurev.ecolsys.27.1.83
[19] Robinson D.F.: Comparison of labeled trees with valency three. J. Combin. Theory Ser. B 11(2), 105-119 (1971) · Zbl 0185.27704 · doi:10.1016/0095-8956(71)90020-7
[20] Robinson D., Foulds I.: Comparison of phylogenetic trees. Math. Biosci. 53(1-2), 131-147 (1981) · Zbl 0451.92006 · doi:10.1016/0025-5564(81)90043-2
[21] Semple C., Steel M.: Phylogenetics. Oxford University Press, Oxford (2003) · Zbl 1043.92026
[22] van Iersel L., Keijsper J., Kelk S., Stouigie L., Hagen F., Boekhout T.: Constructing level-2 phylogenetic networks from triplets. IEEE/ACM Trans. Comput. Biol. Bioinform. 6(4), 667-681 (2009) · doi:10.1109/TCBB.2009.22
[23] Waterman M., Smith T.: On the similarity of dendrograms. J. Theoret. Biol. 73(4), 789-800 (1978) · doi:10.1016/0022-5193(78)90137-6
[24] Willson S.: Properties of normal phylogenetic networks. Bull. Math. Biol. 72(2), 340-358 (2010) · Zbl 1185.92085 · doi:10.1007/s11538-009-9449-z
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.