publication . Article . Other literature type . Preprint . 2010

Locating a tree in a phylogenetic network

Mike Steel;
Open Access
  • Published: 01 Jan 2010 Journal: Information Processing Letters, volume 110, pages 1,037-1,043 (issn: 0020-0190, Copyright policy)
  • Publisher: Elsevier BV
  • Country: Netherlands
Abstract
Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The Tree Containment problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the Cluster Containment problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that Tree Containment is polynomial-time solvable for normal networks, for...
Subjects
arXiv: Quantitative Biology::Populations and EvolutionQuantitative Biology::Genomics
ACM Computing Classification System: ComputingMethodologies_PATTERNRECOGNITIONMathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Signal Processing, Theoretical Computer Science, Information Systems, Computer Science Applications, Phylogenetic tree, Time complexity, Phylogenetic network, Computational complexity theory, Computational phylogenetics, K-ary tree, Mathematics, Binary tree, Combinatorics, Tree rearrangement, Quantitative Biology - Populations and Evolution, Computer Science - Data Structures and Algorithms
Related Organizations

[1] M. Baroni, C. Semple, and M. Steel, A Framework for Representing Reticulate Evolution, Ann. Comb., 8:391- 408, 2004.

[2] M. Baroni, C. Semple, and M. Steel, Hybrids in Real Time. Syst. Biol., 55(1):46-56, 2006.

[3] G. Cardona, M. Llabrs, F. Rossell, and G. Valiente, A Distance Metric for a Class of Tree-Sibling Phylogenetic Networks, Bioinformatics, 24(13):1481-1488 (2008).

[4] G. Cardona, F. Rossell, and G. Valiente, Comparison of Tree-Child Phylogenetic Networks, IEEE/ACM Trans. Comput. Biol. Bioinf., 6(4):552-569 (2009).

[5] W.F. Doolittle and E. Bapteste, Pattern pluralism and the Tree of Life hypothesis, Proc. Natl. Acad. Sci. USA 104: 20432049, 2007. [OpenAIRE]

[6] D.H. Huson and D. Bryant, Application of Phylogenetic Networks in Evolutionary Studies, Mol. Biol. Evol., 23(2):254-267, 2006.

[7] D.H. Huson, R. Rupp, and C. Scornavacca, Phylogenetic Networks, Cambridge University Press, to appear.

[8] L.J.J. van Iersel and S.M. Kelk, When two trees go to war, arXiv:1004.5332v1 [q-bio.PE], 2010. [OpenAIRE]

[9] I.A. Kanj, L. Nakhleh, C. Than, and G. Xia, Seeing the trees and their branches in the network is hard, Theor. Comput. Sci., 401:153-164, 2008. [OpenAIRE]

[10] S. Linz, C. Semple, and T. Stadler, Analyzing and reconstructing reticulation networks under timing constraints, J. Math. Biol., to appear.

[11] L. Nakhleh, Evolutionary phylogenetic networks: models and issues. In: The Problem Solving Handbook for Computational Biology and Bioinformatics, L. Heath and N. Ramakrishnan (editors). Springer, to appear.

[12] S.J. Willson, Regular networks are determined by their trees, IEEE/ACM Trans. Comput. Biol. Bioinf., to appear.

[13] S.J. Willson, Properties of Normal Phylogenetic Networks, Bull. of Math. Biol., 72(2):340-58, 2010.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Other literature type . Preprint . 2010

Locating a tree in a phylogenetic network

Mike Steel;