Tree reconstruction from multi-state characters

DOI10.1006/aama.2001.0772zbMath0995.92033MaRDI QIDQ696854

Charles Semple, Mike A. Steel

Publication date: 12 September 2002

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/9ff7919a105a724737ebc57aeb6528ff496c57b2

zbMATH Keywords

chordal graph; phylogeny; evolutionary history; bifurcating trees; character compatibility

Mathematics Subject Classification ID

05C05: Trees

92D15: Problems related to evolution

05C90: Applications of graph theory

Related Items

Defining a Phylogenetic Tree with the Minimum Number of $r$-State Characters, Linear pencils of tropical plane curves, Recovering trees from well-separated multi-state characters., A phase transition for a random cluster model on phylogenetic trees., Phylogenetic information complexity: is testing a tree easier than finding it?, Combinatorial Scoring of Phylogenetic Networks

Cites Work

• The complexity of reconstructing trees from qualitative characters and subtrees
• A characterization for a set of partial partitions to define an \(X\)-tree
• A characterisation of rigid circuit graphs
• On the Distribution of Lengths of Evolutionary Trees
• Triangulating Vertex-Colored Graphs
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• A Fast Algorithm for the Computation and Enumeration of Perfect Phylogenies