Edge lengths of trees from sequence data (Q1101042)

Used as an indication of relative time intervals, there is a need to determine lengths, associated with each edge of a phylogenetic tree constructed from sequence data of r characters, for u taxa. An edge length can be determined from the differences between the inferred sequences of the end vertices of that edge. As these inferred sequences are often not uniquely defined, a range of possible sequences is possible, at a given internal vertex. This paper introduces an efficient [O(r\(\times n)]\) algorithm, calculating the range of lengths on any edge, over all the minimal labellings, and significantly reduces the number of potential cases to be considered to obtain an objective measure of edge length.