The Geometry of the Neighbor-Joining Algorithm for Small Trees

Details The Geometry of the Neighbor-Joining Algorithm for Small Trees The Geometry of the Neighbor-Joining Algorithm for Small Trees

2009-08-01

arxiv.org/abs/0908.0098v1

It is published in the proceedings of Algebraic Biology, Springer LNC Series (2008), p82-96

Mathematics

Combinatorics

15 pages

Scientific paper

In 2007, Eickmeyer et al. showed that the tree topologies outputted by the Neighbor-Joining (NJ) algorithm and the balanced minimum evolution (BME) method for phylogenetic reconstruction are each determined by a polyhedral subdivision of the space of dissimilarity maps ${\R}^{n \choose 2}$, where $n$ is the number of taxa. In this paper, we will analyze the behavior of the Neighbor-Joining algorithm on five and six taxa and study the geometry and combinatorics of the polyhedral subdivision of the space of dissimilarity maps for six taxa as well as hyperplane representations of each polyhedral subdivision. We also study simulations for one of the questions stated by Eickmeyer et al., that is, the robustness of the NJ algorithm to small perturbations of tree metrics, with tree models which are known to be hard to be reconstructed via the NJ algorithm.

Affiliated with

Also associated with

No associations

Rating

The Geometry of the Neighbor-Joining Algorithm for Small Trees 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 The Geometry of the Neighbor-Joining Algorithm for Small Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Geometry of the Neighbor-Joining Algorithm for Small Trees will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-579627