The Structure of Level-k Phylogenetic Networks

DOI10.1007/978-3-642-02441-2_26zbMath1247.92018OpenAlexW1527128109WikidataQ58172957 ScholiaQ58172957MaRDI QIDQ3637120

Christophe Paul, Vincent Berry, Philippe Gambette

Publication date: 7 July 2009

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02441-2_26

Mathematics Subject Classification ID

Problems related to evolution (92D15) Complexity and performance of numerical algorithms (65Y20) Systems biology, networks (92C42)

Related Items

Transforming phylogenetic networks: moving beyond tree space, Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations, Do branch lengths help to locate a tree in a phylogenetic network?, The SNPR neighbourhood of tree-child networks, A branching process approach to level‐k phylogenetic networks, On encodings of phylogenetic networks of bounded level, Counting phylogenetic networks of level 1 and 2, Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable, Trinets encode tree-child and level-2 phylogenetic networks

Uses Software

• OEIS
• Recodon

Cites Work

• Unnamed Item
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Inferring a level-1 phylogenetic network from a dense set of rooted triplets
• Seeing the trees and their branches in the network is hard
• Graph isomorphism problem
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Logical description of context-free graph languages
• On the complexity of polytope isomorphism problems
• Computing the maximum agreement of phylogenetic networks
• Properties of a neutral allele model with intragenic recombination
• Worst-case optimal approximation algorithms for maximizing triplet consistency within phylogenetic networks
• Constructing the Simplest Possible Phylogenetic Network from Triplets
• Level-k Phylogenetic Networks Are Constructable from a Dense Triplet Set in Polynomial Time
• Research in Computational Molecular Biology