Inferring a level-1 phylogenetic network from a dense set of rooted triplets

DOI10.1016/j.tcs.2006.06.022zbMath1110.68032OpenAlexW2066429145MaRDI QIDQ860812

Wing-Kin Sung, Jesper Jansson

Publication date: 9 January 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.06.022

zbMATH Keywords

algorithmsorting networkrooted tripletphylogenetic network construction

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05)

Related Items

Identifiability of species network topologies from genomic sequences using the logDet distance ⋮ Encoding and constructing 1-nested phylogenetic networks with trinets ⋮ Do branch lengths help to locate a tree in a phylogenetic network? ⋮ How far is my network from being edge-based? Proximity measures for edge-basedness of unrooted phylogenetic networks ⋮ Phylogenetic Networks ⋮ Caterpillars on three and four leaves are sufficient to binary normal networks ⋮ On encodings of phylogenetic networks of bounded level ⋮ Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable ⋮ Reconstructing a phylogenetic level-1 network from quartets ⋮ Trinets encode orchard phylogenetic networks ⋮ New heuristics for rooted triplet consistency ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ The matroid structure of representative triple sets and triple-closure computation ⋮ Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets ⋮ Constructing the simplest possible phylogenetic network from triplets ⋮ Reconstructing tree-child networks from reticulate-edge-deleted subnetworks ⋮ When two trees go to war ⋮ Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks ⋮ New results on optimizing rooted triplets consistency ⋮ All that glisters is not galled ⋮ NCHB: a method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization ⋮ Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks ⋮ Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time ⋮ The Structure of Level-k Phylogenetic Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing evolution of sequences subject to recombination using parsimony
• Rooted maximum agreement supertrees
• The complexity of reconstructing trees from qualitative characters and subtrees
• Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
• On the complexity of constructing evolutionary trees
• Constructing the maximum consensus tree from rooted Triples
• Computing the maximum agreement of phylogenetic networks
• A Polynomial Time Approximation Scheme for Inferring Evolutionary Trees from Quartet Topologies and Its Application
• Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions
• Analytic Solutions for Three-Taxon MLMC Trees with Variable Rates Across Sites
• Determining the Evolutionary Tree Using Experiments
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity