2010/02/04 by Francesca Tria, Emanuele Caglioti, Tria, F. +5
Biochemistry, Genetics and Molecular Biology · #FOS: Biological sciences #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Genomics and Rare Diseases #Populations and Evolution (q-bio.PE)
paper · pdf · doi:10.48550/arxiv.1002.1100
openalex publication_date 2010/02/04 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
In many interesting cases the reconstruction of a correct phylogeny is\nblurred by high mutation rates and/or horizontal transfer events. As a\nconsequence a divergence arises between the true evolutionary distances and the\ndifferences between pairs of taxa as inferred from available data, making the\nphylogenetic reconstruction a challenging problem. Mathematically this\ndivergence translates in a loss of additivity of the actual distances between\ntaxa. In distance-based reconstruction methods, two properties of additive\ndistances were extensively exploited as antagonist criteria to drive phylogeny\nreconstruction: on the one hand a local property of quartets, i.e., sets of\nfour taxa in a tree, the four-points condition; on the other hand a recently\nproposed formula that allows to write the tree length as a function of the\ndistances between taxa, the Pauplin's formula. Here we introduce a new\nreconstruction scheme, that exploits in a unified framework both the\nfour-points condition and the Pauplin's formula. We propose, in particular, a\nnew general class of distance-based Stochastic Local Search algorithms, which\nreduces in a limit case to the minimization of the Pauplin's length. When\ntested on artificially generated phylogenies our Stochastic Big-Quartet\nSwapping algorithmic scheme significantly outperforms state-of-art\ndistance-based algorithms in cases of deviation from additivity due to high\nrate of back mutations. A significant improvement is also observed with respect\nto the state-of-art algorithms in case of high rate of horizontal transfer.\n