FastME is a fast phylogeny reconstruction program based on the minimum evolution method. Among distance methods, FastME has shown better topological accuracy than Neighbor Joining, BIONJ, WEIGHBOR and FITCH, in all evolutionary conditions we have tested, including large range deviations from molecular clock and substitution rates. When the number of taxa is high, its superiority over NJ, BIONJ and WEIGHBOR becomes important, while FITCH remains close to FastME but becomes hard to use due to its slowness. FastME is very fast, even faster than NJ, and can easily be applied to very large data sets (> 1000 taxa).  A PHYLIP compatible version can be downloaded from this web page.

FastME was developed by Richard Desper (NCBI, Bethesda, USA) and Olivier Gascuel (LIRMM, Montpellier, France).

FastME first builds an initial tree, using either GME or BME algorithms, and then improves this tree by tree swapping, using either FASTNNI or BNNI algorithms. GME and FASTNNI optimize the ordinary least-squares (OLS) version of the minimum-evolution principle, while BME and BNNI optimize the balanced version. All simulations indicate that the balanced version is much more appropriate. But the initial tree has not much influence on the final tree that is obtained after tree swapping. So the default options are GME (faster than BME) and BNNI (much more accurate than FASTNNI). We suggest using these default options in all practical situations, at least when using evolutionary distances estimated from sequences. More explanations about the algorithms and their range of use are given in the papers above.

Distance matrices must be in the square PHYLIP format. If the input file contains several matrices given one after the other, as obtained when combining SEQBOOT and DNADIST or PROTDIST to perform a bootstrap analysis, FastME returns the same number of trees, written one after the other in the output file; this file may be given to CONSENSE to obtain the bootstrap tree.

FastME runs from a MS-DOS or Unix window with the following options:

-b specify method for building initial tree: GME(default) or BME. Not used if -t is used.

-i filename of distance matrix(ces).

-n number of matrices/trees (default = 1)

-o filename for tree output

-s specify type of tree swapping (NNI): (b)alanced, (O)LS, or (n)one. (default is balanced.)

-t (optional) filename of starting tree topology

-v provides the progress of run (can be wrong with some systems)

-help to get the options

For example, assuming that the datatest file (downloaded from this web page, see above) is in the C:\ directory, the line command:

  fastme –i C:\datatest –n 3 –o C:\outputtree

will construct 3 trees and write them (Newick format) into the file outputtree, in the C:\ directory. If something is wrong (e.g. the input file name), you will get the list of all options.

• Desper, R., Gascuel, O. (2002). Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle, Proceedings of the 2^nd Workshop on Algorithms in Bioinformatics (WABI), Roma, Lecture Notes in Computer Science.
A longer version, including algorithmic details and mathematical proofs:
• Desper, R., Gascuel, O. (2002). Fast and Accurate Phylogeny Reconstruction Algorithms Based on the Minimum-Evolution Principle, Journal of Computational Biology 19(5), pp. 687-705.

Disclaimer      Privacy statement

Revised October 22, 2002