Tree-Child Cluster Networks

• Autorzy: Alcalà A. , Llabrés M. , Rosselló F. , Rullan P.

Identyfikatory

DOI

10.3233/FI-2014-1087

• Języki publikacji: EN

Abstrakty

EN

In general, a phylogenetic network is a graphical representation of an evolutionary history that involves reticulate events like recombinations, hybridizations, or lateral gene transfers. Tree-child reticulate networks (TC networks) are a special class of phylogenetic networks that allow to represent evolutionary histories where, despite the existence of such reticulate events, every ancestral species has some descendant through mutations. In this paper we establish two equivalent characterizations of the families of clusters of TC networks. These characterizations yield a simple, polynomial-time algorithm that decides whether a given family of clusters on a set of taxa is the family of clusters of some TC network or not, and, when the answer is positive, outputs a TC network that is a minimal reticulate network representing this family of clusters. This algorithm is based on the notion of cluster network introduced by Huson and Rupp, and it has been implemented in a Python package and a companion web tool, which are freely available on the web.

Słowa kluczowe

EN

phylogenetic network; tree-child networks; cluster networks; regular networks; clusters

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 1/2
• Strony: 1--15
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Alcalà A.

• Department of Mathematics and Computer Science, University of the Balearic, Islands, E-07122 Palma de Mallorca, Spain

autor

Llabrés M.

• Department of Mathematics and Computer Science, University of the Balearic, Islands, E-07122 Palma de Mallorca, Spain

autor

Rosselló F.

• Department of Mathematics and Computer Science, University of the Balearic, Islands, E-07122 Palma de Mallorca, Spain

autor

Rullan P.

• Department of Mathematics and Computer Science, University of the Balearic, Islands, E-07122 Palma de Mallorca, Spain

Bibliografia

• [1] Baroni, M., Semple, C., Steel, M.: A framework for representing reticulate evolution, Ann. Combin., 8, 2004, 391-408.
• [2] Cardona, G., Rosselló, F., Valiente, G.: Extended Newick: it is time for a standard representation of phylogenetic networks, BMC Bioinformatics, 9, 2008, 532.
• [3] Cardona, G., Rosselló, F., Valiente, G.: Tripartitions do not always discriminate phylogenetic networks, Mathematical Biosciences, 211, 2008, 356370.
• [4] Cardona, G., Rosselló, F., Valiente, G.: Comparison of tree-child phylogenetic networks, IEEE T. Comput. Biol., 6, 2009, 552569.
• [5] Doolittle, W. F.: Phylogenetic classification and the universal tree, Science, 284, 1999, 21242128.
• [6] Felsenstein, J.: Inferring Phylogenies, Sinauer Associates Inc., 2004.
• [7] Huson, D. H., Bryant, D.: Application of phylogenetic networks in evolutionary studies, Molecular Biology and Evolution, 23, 2006, 254267.
• [8] Huson, D. H., Rupp, R.: Summarizing multiple gene trees using cluster networks, in: Algorithms in Bioinformatics, vol. 5252 of Lecture Notes in Bioinformatics, Springer, 2008, 296305.
• [9] Huson, D. H., Rupp, R., Scornavacca, C.: Phylogenetic Networks, Cambridge University Press, 2010.
• [10] Morrison, D.: An Introduction to Phylogenetic Networks, RJR Productions, 2011.
• [11] Semple, C., Steel, M.: Phylogenetics, Oxford University Press, 2003.
• [12] Willson, S. J.: Reconstruction of certain phylogenetic networks from the genomes at their leaves, Journal of Theoretical Biology, 252, 2008, 338349.