Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

Details Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

2011-08-18

arxiv.org/abs/1108.3653v1

Computer Science

Computational Complexity

Submitted

Scientific paper

Here we show that, given a set of clusters C on a set of taxa X, where |X|=n, it is possible to determine in time f(k).poly(n) whether there exists a level-<= k network (i.e. a network where each biconnected component has reticulation number at most k) that represents all the clusters in C in the softwired sense, and if so to construct such a network. This extends a polynomial time result from "On the elusiveness of clusters" by Kelk, Scornavacca and Van Iersel(2011). By generalizing the concept of "level-k generator" to general networks, we then extend this fixed parameter tractability result to the problem where k refers not to the level but to the reticulation number of the whole network.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-180716