GENEALOGY-DNA-L Archives

Archiver > GENEALOGY-DNA > 2006-12 > 1167431577


From: valery <>
Subject: Re: [DNA] Tree Algorithms
Date: Fri, 29 Dec 2006 22:32:57 +0000
References: <000801c729e8$357c5280$6400a8c0@Ken1><7678E4A4-14AA-4F80-BC85-3A800E7F385B@vizachero.com>


> It sounds like you are describing a neighbor joining or UPGMA
> algorithm, and these are not generally considered to be reliable at
> producing accurate phylogenies (though the clusters they produce at
> the tips of the tree are often reasonable). They do have the
> advantage of speed, making it possible to use them on very large
> datasets. Other methods are often impossible to use on more than a
> few
> hundred taxa without access to a supercomputer cluster. Their speed
> also makes bootstrapping possible, which helps alert users to
> unreliable clusters.


Vincent, Bandelt's MJ has better performance than NJ, more precisely,
it is between N^2 and N^3 and the power of N can be decreased. My own
implementation of MJ is approximately 10-15 times faster than one by
Fluxus on datasets I used to compare them. The problem is that MJ is a
kind of heuristic, not a tool to make Steiner trees. However, it is a
perfectly customizable tool which can generate graphs pretty close to
the union of all MP trees, and sometimes the difference between MP and
MJ (with epsilon = 0) appears to be less than one between MJ results
for different weighting tables. That is a reason why now I prefer MJ.

btw, if a dataset is fully binary, MJ with high epsilon followed by the
Steiner postprocessing may outperform traditional PAUP-like ways. In
this case, there is at least one MP tree within the full network, so
further processing refines a subset of all-MP-trees-union.


Valery

This thread: