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

DOI10.1007/978-3-642-02882-3_27MaRDI QIDQ5323073zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)