Celine Scornavacca

  1. Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable.

    Authors: Steven Kelk, Celine Scornavacca
    Subjects: Computational Complexity
    Abstract

    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).

Syndicate content