The length of a leaf coloration on a random binary tree

An assignment of colors to objects induces a natural integer weight on each tree that has these objects as leaves. This weight is called "parsimony length" in biostatistics and is the basis of the "maximum parsimony" technique for reconstructing evolutionary trees. Equations for...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 1997-08, Vol.10 (3), p.359-372
Main Authors: HAMEL, A. M, STEEL, M. A
Format: Article
Language:English
Subjects:
Color
Combinatorics
Combinatorics. Ordered structures
Exact sciences and technology
Graph theory
Leaves
Mathematics
Sciences and techniques of general use
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An assignment of colors to objects induces a natural integer weight on each tree that has these objects as leaves. This weight is called "parsimony length" in biostatistics and is the basis of the "maximum parsimony" technique for reconstructing evolutionary trees. Equations for the average value (over all binary trees) of the parsimony length of both fixed and random colorations are derived using generating function techniques. This leads to asymptotic results that extend earlier results confined to just two colors. A potential application to DNA sequence analysis is outlined briefly.
ISSN:0895-4801
1095-7146
DOI:10.1137/S0895480194271591