Locating a tree in a phylogenetic network

Details Locating a tree in a phylogenetic network Locating a tree in a phylogenetic network

2010-06-16

arxiv.org/abs/1006.3122v1

Biology

Quantitative Biology

Populations and Evolution

9 pages, 4 figures

Scientific paper

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 binary tree-child networks, and for level-$k$ networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both Tree Containment and Cluster Containment remain NP-complete.

Affiliated with

Also associated with

No associations

Rating

Locating a tree in a phylogenetic network does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Locating a tree in a phylogenetic network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Locating a tree in a phylogenetic network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-99988