A Stochastic Local Search algorithm for distance-based phylogeny reconstruction

Details A Stochastic Local Search algorithm for distance-based phylogeny reconstruction A Stochastic Local Search algorithm for distance-based phylogeny reconstruction

2010-02-04

arxiv.org/abs/1002.1100v1

Biology

Quantitative Biology

Populations and Evolution

13 pages, 8 figures

Scientific paper

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 were extensively exploited as antagonist criteria to drive phylogeny reconstruction: on the one hand a local property of quartets, i.e., 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, the 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 the 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 case of high rate of horizontal transfer.

Affiliated with

Also associated with

No associations

Rating

A Stochastic Local Search algorithm for distance-based phylogeny reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Stochastic Local Search algorithm for distance-based phylogeny reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Stochastic Local Search algorithm for distance-based phylogeny reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-534394