Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable

2011/08/18 by Steven Kelk, Céline Scornavacca, Kelk, Steven +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Earth and Planetary Sciences · #Computational Complexity (cs.CC) #Evolution and Paleontology Studies #FOS: Biological sciences #FOS: Computer and information sciences #Genetic diversity and population structure #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #cs.CC #q-bio.PE

paper · pdf · doi:10.48550/arxiv.1108.3653

Submitted

arxiv created 2011/08/18 · openalex publication_date 2011/08/18 · arxiv updated 2011/08/19 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28

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

Citations

• On the elusiveness of clusters

Related

• On the elusiveness of clusters
• A short note on the tractability of constructing phylogenetic networks from clusters
• Minimum Network Level Forced by Hardwired Cluster Data
• Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
• On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters