Circular orders of tree metrics, and their uses for the reconstruction and fitting of phylogenetic trees

TL;DRAbstract

The circular orders associated with the planar drawings of an X-tree (or phylogenetic tree) have been studied by several authors. They allow an encoding of an Xtree by 2n-3 numbers (where n is the number of elements of X), the lengths of some paths between leaves of the tree. It is shown here that circular orders are the same as those obtained from the table of a tree metric by a construction due to Yushmanov [28]. It is also observed that this construction applies to any dissimilarity, tree metric or not. Several fast algorithms (of complexity O(n2)) are derived from these results: for the determination of a Yushmanov order; for the reconstruction of the valued X-tree represention of a tree metric; for the recognition of a tree metric; and for the fitting of a tree metric to a given dissimilarity; the fitting method is based on successive local least squares approximations. Tested on various experimental and real data, it gives satisfactory results. RESUME. Plusieurs auteurs ont etudi

Chat with Paper

AI Agents for this Paper