A stochastic local search algorithm for distance-based phylogeny reconstruction.
In many interesting cases, the reconstruction of a correct phylogeny is blurred by high mutation rates and/or horizontal transfer events. As a consequence, a divergence arises between the true evolutionary distances and the differences between pairs of taxa as inferred from available data, making the phylogenetic reconstruction a challenging problem. Mathematically, this divergence translates in a loss of additivity of the actual distances between taxa. In distance-based reconstruction methods, two properties of additive distances have been extensively exploited as antagonist criteria to drive phylogeny reconstruction: On the one hand, a local property of quartets, that is, sets of four taxa in a tree, the four-points condition; on the other hand, a recently proposed formula that allows to write the tree length as a function of the distances between taxa, Pauplin's formula. Here, we introduce a new reconstruction scheme that exploits in a unified framework both the four-points condition and the Pauplin's formula. We propose, in particular, a new general class of distance-based Stochastic Local Search algorithms, which reduces in a limit case to the minimization of Pauplin's length. When tested on artificially generated phylogenies, our Stochastic Big-Quartet Swapping algorithmic scheme significantly outperforms state-of-art distance-based algorithms in cases of deviation from additivity due to high rate of back mutations. A significant improvement is also observed with respect to the state-of-art algorithms in the case of high rate of horizontal transfer.
Tria
Francesca
F
Institute for Scientific Interchange, Torino, Italy. tria@isi.it
Caglioti
Emanuele
E
Loreto
Vittorio
V
Pagnani
Andrea
A
D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D022761:Gene Transfer, Horizontal / Q000235:genetics; D009154:Mutation / Q000235:genetics; D010802:Phylogeny; D013269:Stochastic Processes