Recovering trees from well-separated multi-state characters
2004 (English)In: Discrete Mathematics, Vol. 278, no 1-3, 151-164 p.Article in journal (Refereed) Published
Recently, by studying Z(5)-edge colorings of bifurcating phylogenetic trees, Semple and Steel showed that every such tree can be convexly defined by at most five characters. The investigation of the rich structure of such edge colorings led us to the definition of a set of well-separated characters on a phylogenetic tree T that covers T which we study here. In particular, we show that such a set W of characters convexly defines a bifurcating phylogenetic tree T and that, provided this cover is sparse, the so called relation graph associated to W coincides with T. As a consequence of our results, it follows that T can be reconstructed. from W in polynomial time.
Place, publisher, year, edition, pages
2004. Vol. 278, no 1-3, 151-164 p.
well-separated character, relation graph, phylogenetic tree, convexly defined, z(5)-edge coloring, partitions, graphs
IdentifiersURN: urn:nbn:se:uu:diva-71871OAI: oai:DiVA.org:uu-71871DiVA: diva2:99782