On the Generalised Character Compatibility Problem for Non-branching Character Trees

DOI10.1007/978-3-642-02882-3_27zbMATH Open1248.68254OpenAlexW1523916760MaRDI QIDQ5323073FDOQ5323073

Authors: Ján Maňuch, Murray Patterson, Arvind Kumar Gupta 

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10281/217385

Recommendations

• Optimizing tree and character compatibility across several phylogenetic trees
• Two strikes against perfect phylogeny
• A novel insight into the perfect phylogeny problem
• Tree Compatibility and Inferring Evolutionary History
• Finding a maximum compatible tree is NP-hard for sequences and trees

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Triangulating Vertex-Colored Graphs
• The complexity of reconstructing trees from qualitative characters and subtrees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Total Ordering Problem
• Inferring Evolutionary History From DNA Sequences
• A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
• Building PQR trees in almost-linear time
• Title not available (Why is that?)

Cited In (3)

• Character-based phylogeny construction and its application to tumor evolution
• A colored graph approach to perfect phylogeny with persistent characters
• Trees, taxonomy, and strongly compatible multi-state characters

This page was built for publication: On the Generalised Character Compatibility Problem for Non-branching Character Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5323073)