Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks

Details Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks

2007-12-18

arxiv.org/abs/0712.2932v3

Biology

Quantitative Biology

Populations and Evolution

Scientific paper

Phylogenetic networks provide a way to describe and visualize evolutionary histories that have undergone so-called reticulate evolutionary events such as recombination, hybridization or horizontal gene transfer. The level k of a network determines how non-treelike the evolution can be, with level-0 networks being trees. We study the problem of constructing level-k phylogenetic networks from triplets, i.e. phylogenetic trees for three leaves (taxa). We give, for each k, a level-k network that is uniquely defined by its triplets. We demonstrate the applicability of this result by using it to prove that (1) for all k of at least one it is NP-hard to construct a level-k network consistent with all input triplets, and (2) for all k it is NP-hard to construct a level-k network consistent with a maximum number of input triplets, even when the input is dense. As a response to this intractability we give an exact algorithm for constructing level-1 networks consistent with a maximum number of input triplets.

Affiliated with

Also associated with

No associations

Rating

Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks 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 Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-549297