A short note on the tractability of constructing phylogenetic networks from clusters

2009/12/22 by Leo van Iersel, Steven Kelk, van Iersel, Leo +1
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Medicine · #Chromosomal and Genetic Variations #FOS: Biological sciences #Fungal Infections and Studies #Genomics and Phylogenetic Studies #Populations and Evolution (q-bio.PE) #q-bio.PE

paper · pdf · doi:10.48550/arxiv.0912.4502

arxiv created 2009/12/22 · openalex publication_date 2009/12/22 · arxiv updated 2010/01/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In [2] it was proven that the Cass algorithm is a polynomial-time algorithm for constructing level<=2 networks from clusters. Here we demonstrate, for each k>=0, a polynomial-time algorithm for constructing level-k phylogenetic networks from clusters. Unlike Cass the algorithm scheme given here is only of theoretical interest. It does, however, strengthen the hope that efficient polynomial-time algorithms (and perhaps fixed parameter tractable algorithms) exist for this problem.

Related

• On the elusiveness of clusters
• Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
• Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable
• Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks
• Constructing level-2 phylogenetic networks from triplets