uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Recovering trees from well-separated multi-state characters
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, The Linnaeus Centre for Bioinformatics.
2004 (English)In: Discrete Mathematics, Vol. 278, no 1-3, 151-164 p.Article in journal (Refereed) Published
Abstract [en]

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.
Keyword [en]
well-separated character, relation graph, phylogenetic tree, convexly defined, z(5)-edge coloring, partitions, graphs
URN: urn:nbn:se:uu:diva-71871OAI: oai:DiVA.org:uu-71871DiVA: diva2:99782
Available from: 2005-05-13 Created: 2005-05-13 Last updated: 2011-01-12

Open Access in DiVA

No full text

By organisation
The Linnaeus Centre for Bioinformatics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 157 hits
ReferencesLink to record
Permanent link

Direct link