Phylogenetic Tree

An unrooted phylogenetic tree on a finite set of taxa is a tree whose tree leaves are in bijection with , with the elements of serving as leaf labels, and which has no vertices of vertex degree 2. Two such trees are considered the same when there is a graph isomorphism between them that fixes every leaf label. The leaves usually represent observed taxa; without a root, the tree records branching relationships but not an ancestral direction (Semple and Steel 2003).

A rooted phylogenetic tree is defined similarly using a rooted tree, with every internal vertex having at least two children. A rooted phylogenetic tree is binary when every internal vertex has exactly two children, while an unrooted phylogenetic tree is binary when every internal vertex has degree 3. The root determines an ancestral direction, and internal vertices represent hypothetical common ancestors. For , the number of rooted binary phylogenetic trees is for , while the number of unrooted binary phylogenetic trees is for , where denotes the double factorial (Semple and Steel 2003).

The illustration above shows a stylized rooted binary phylogenetic tree whose leaves are labeled by scientific names. Four colors distinguish groups of related taxa. Horizontal positions show branching order only. The branch lengths are schematic and do not represent evolutionary time.

Assigning a nonnegative length to every edge gives an edge-weighted phylogenetic tree. Assuming distinct leaves have positive distance, the length of the unique graph path between leaves and defines

The resulting metric is called a tree metric. Conversely, a finite metric has an edge-weighted tree representation iff it satisfies the four-point condition: for every , , , and in , the maximum of , , and is attained at least twice (Buneman 1971). This characterization connects phylogenetic reconstruction from pairwise dissimilarities with distance matrices.