Reconstructing a phylogenetic level-1 network from quartets

2013/08/23 by Judith Keijsper, Keijsper, J. C. M., Rudi Pendavingh +1 · 1 citation
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Earth and Planetary Sciences · #05C85 Graph algorithms #Combinatorics (math.CO) #Evolution and Paleontology Studies #FOS: Mathematics #Genomics and Phylogenetic Studies #Plant Diversity and Evolution

paper · pdf · doi:10.48550/arxiv.1308.5206

openalex publication_date 2013/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe a method that will reconstruct an unrooted binary phylogenetic level-1 network on n taxa from the set of all quartets containing a certain fixed taxon, in O(n³) time. We also present a more general method which can handle more diverse quartet data, but which takes O(n⁶) time. Both methods proceed by solving a certain system of linear equations over GF(2). For a general dense quartet set (containing at least one quartet on every four taxa) our O(n⁶) algorithm constructs a phylogenetic level-1 network consistent with the quartet set if such a network exists and returns an (O(n²) sized) certificate of inconsistency otherwise. This answers a question raised by Gambette, Berry and Paul regarding the complexity of reconstructing a level-1 network from a dense quartet set.

Cited by

• Bounds on the sequence length sufficient to reconstruct binary level-1 phylogenetic networks under the CFN model

Related

• Fast error-tolerant quartet phylogeny algorithms
• A Practical Algorithm for Reconstructing Level-1 Phylogenetic Networks
• Level-k Phylogenetic Network can be Constructed from a Dense Triplet Set in Polynomial Time
• Constructing a Minimum-Level Phylogenetic Network from a Dense Triplet Set in Polynomial Time
• Constructing the Simplest Possible Phylogenetic Network from Triplets