Minimizing Contradictions on Circular Order of Phylogenic Trees

Distance-based approaches to phylogeny use estimations of the evolutionary distance between sequences to reconstruct an evolution tree. If the evolution can be represented by an X-tree, the different sequences can be ordered so that the distance matrix [Formula: see text] , representing the distance from a leaf n to the path (i, j), is perfectly ordered meaning that [Formula: see text] and [Formula: see text] for i ≤ j ≤ k. After ordering of the sequences, the distance matrix [Formula: see text] permits to visualize phylogenetic relationships between taxa and to localize deviations from perfect order. The effect of perturbations resulting from lateral gene transfer or crossover can be modeled probabilistically. The order is shown to be quite robust against many perturbations. We have developed algorithms to minimize the level of contradiction in the order of the sequences. These algorithms are tested on the SSU rRNA data for Archaea. The degree of contradiction after optimization is for most taxa quite low. Regions in the taxa space with deviations from perfect order were identified.