Comparison of additive trees using circular orders

It has been postulated that existing species have been linked in the past i n a way that can be described using an additive tree structure. Any such tr ee structure reflecting species relationships is associated with a matrix o f distances between the species considered which is called a distance matri x or a tree metric matrix, A circular order of elements of X corresponds to a circular (clockwise) scanning of the subset X of vertices of a tree draw n on a plane. This paper describes an optimal algorithm using circular orde rs to compare the topology of two trees given by their distance matrices, T his algorithm allows us to compute the Robinson and Foulds topologic distan ce between two trees, It employs circular order tree reconstruction to comp ute an ordered bipartition table of the tree edges for both given distance matrices, These bipartition tables are then compared to determine the Robin son and Foulds topologic distance, known to be an important criterion of tr ee similarity. The described algorithm has optimal time complexity, requiri ng O (n(2)) time when performed on two n x It distance matrices. It can be generalized to get another optimal algorithm, which enables the strict cons ensus tree of k unrooted trees, given their distance matrices, to be constr ucted in O (kn(2)) time.