Constructing level-2 phylogenetic networks from triplets

Details Constructing level-2 phylogenetic networks from triplets Constructing level-2 phylogenetic networks from triplets

2007-07-19

arxiv.org/abs/0707.2890v1

Biology

Quantitative Biology

Populations and Evolution

Scientific paper

Jansson and Sung showed that, given a dense set of input triplets T (representing hypotheses about the local evolutionary relationships of triplets of species), it is possible to determine in polynomial time whether there exists a level-1 network consistent with T, and if so to construct such a network. They also showed that, unlike in the case of trees (i.e. level-0 networks), the problem becomes NP-hard when the input is non-dense. Here we further extend this work by showing that, when the set of input triplets is dense, the problem is even polynomial-time solvable for the construction of level-2 networks. This shows that, assuming density, it is tractable to construct plausible evolutionary histories from input triplets even when such histories are heavily non-tree like. This further strengthens the case for the use of triplet-based methods in the construction of phylogenetic networks. We also show that, in the non-dense case, the level-2 problem remains NP-hard.

Affiliated with

Also associated with

No associations

Rating

Constructing level-2 phylogenetic networks from triplets 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 Constructing level-2 phylogenetic networks from triplets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Constructing level-2 phylogenetic networks from triplets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-544977