| ## EMBOSS: PHYLIP

# Original PHYLIP neighbor documentation.

This is the original PHYLIP documentation and includes information on the old menu driven program which is now replaced with the EMBOSS acd file.

                                                                       version 3.5c

                    NEIGHBOR -- Neighbor-Joining and UPGMA methods

    (c) Copyright  1991-1993  by  Joseph  Felsenstein  and  by  the  University  of
    Washington.  Written by Joseph Felsenstein.  Permission is granted to copy this
    document provided that no fee is charged for it and that this copyright  notice
    is not removed.

         This program implements the Neighbor-Joining  method  of  Nei  and  Saitou
    (1987)  and  the  UPGMA  method of clustering.  The program was written by Mary
    Kuhner and Jon Yamato, using some code from program FITCH.  An  important  part
    of  the code was translated from FORTRAN code from the neighbor-joining program
    written by Naruya Saitou and by Li Jin, and is used with the kind permission of
    Dr. Saitou.

         NEIGHBOR constructs a tree by successive clustering of  lineages,  setting
    branch  lengths  as  the lineages join.  The tree is not rearranged thereafter.
    The tree does not assume an evolutionary clock, so that  it  is  in  effect  an
    unrooted  tree.   It  should be somewhat similar to the tree obtained by FITCH.
    The program cannot evaluate a User tree, nor can it prevent branch lengths from
    becoming  negative.   However the algorithm is far faster than FITCH or KITSCH.
    This will make it particularly effective in their place for  large  studies  or
    for  bootstrap  or  jackknife resampling studies which require runs on multiple
    data sets.

         The  UPGMA  option  constructs  a  tree  by   successive   (agglomerative)
    clustering  using  an  average-linkage  method  of  clustering.   It  has  some
    relationship to KITSCH, in that when the tree topology turns out the same,  the
    branch lengths with UPGMA will turn out to be the same as with the P = 0 option
    of KITSCH.

         The options for NEIGHBOR are selected through the menu, which  looks  like
    this:

    Neighbor-Joining/UPGMA method version 3.5

    Settings for this run:
      N       Neighbor-joining or UPGMA tree?  Neighbor-joining
      O                        Outgroup root?  No, use as outgroup species  1
      L         Lower-triangular data matrix?  No
      R         Upper-triangular data matrix?  No
      S                        Subreplicates?  No
      J     Randomize input order of species?  No. Use input order
      M           Analyze multiple data sets?  No
      0   Terminal type (IBM PC, VT52, ANSI)?  ANSI
      1    Print out the data at start of run  No
      2  Print indications of progress of run  Yes
      3                        Print out tree  Yes
      4       Write out trees onto tree file?  Yes

    Are these settings correct? (type Y or the letter for one to change)

    Most of the input options (L, R, S, J, and M) are  as  given  in  the  Distance
    Matrix  Programs  documentation  file, that file, and their input format is the
    same as given there.   The  O  (Outgroup)  option  is  described  in  the  main
    documentation  file of this package.  It is not available when the UPGMA option
    is selected.  The Jumble option (J) does not allow multiple jumbles (as most of
    the  other  programs that have it do), as there is no objective way of choosing
    which of the multiple results is best, there being no  explicit  criterion  for
    optimality of the tree.

         Option N chooses between the Neighbor-Joining and UPGMA methods. Option  S
    is the usual Subreplication option.  Here, however, it is present only to allow
    NEIGHBOR to read the input data: the number of replicates is actually  ignored,
    even though it is read in.  Note that this means that one cannot use it to have
    missing data in the input file, if NEIGHBOR is to be used.

         The output consists of an tree (rooted if  UPGMA,  unrooted  if  Neighbor-
    Joining)  and  the  lengths  of  the  interior  segments.   The Average Percent
    Standard Deviation is not computed or  printed  out.   If  the  tree  found  by
    Neighbor is fed into FITCH as a User Tree, it will compute this quantity if one
    also selects the N option of FITCH to ensure that none of the branch lengths is
    re-estimated.

         As NEIGHBOR runs it prints out an account  of  the  successive  clustering
    levels,  if  you  allow  it  to.   This  is  mostly  for reassurance and can be
    suppressed using menu option 2.  In this printout of cluster  levels  the  word
    "OTU"  refers  to a tip species, and the word "NODE" to an interior node of the
    resulting tree.

         The constants available for modification at the beginning of  the  program
    are  "namelength"  which  gives  the  length  of  a species name, and the usual
    boolean constants that initiliaze the  terminal  type.   There  is  no  feature
    saving multiply trees tied for best, partly because we do not expect exact ties
    except in cases where the branch lengths make the nature of the tie obvious, as
    when a branch is of zero length.

         The major advantage of NEIGHBOR is its speed:  it  requires  a  time  only
    proportional  to  the  square  of the number of species.  By contrast FITCH and
    KITSCH require a time that rises as the fourth power of the number of  species.
    Thus  NEIGHBOR  is well-suited to bootstrapping studies and to analysis of very
    large trees.  Our  simulation  studies  (Kuhner,  Yamato  and  Felsenstein,  in
    preparation)  show  that,  contrary  to statements in the literature by others,
    NEIGHBOR does not get as accurate an estimate of the phylogeny as  does  FITCH.
    However  it  does  nearly as well, and in view of its speed this will make it a
    quite useful program.

    -----------------------------TEST DATA SET------------------------------

        5
    Alpha      0.000 1.000 2.000 3.000 3.000
    Beta       1.000 0.000 2.000 3.000 3.000
    Gamma      2.000 2.000 0.000 3.000 3.000
    Delta      3.000 3.000 3.000 0.000 1.000
    Epsilon    3.000 3.000 3.000 1.000 0.000

    ------ OUTPUT FROM TEST DATA SET (with all numerical options on) -----------

       5 Populations

    Neighbor-Joining/UPGMA method version 3.5

     Neighbor-joining method

     Negative branch lengths allowed

    Name                       Distances
    ----                       ---------

    Alpha         0.00000   1.00000   2.00000   3.00000   3.00000
    Beta          1.00000   0.00000   2.00000   3.00000   3.00000
    Gamma         2.00000   2.00000   0.00000   3.00000   3.00000
    Delta         3.00000   3.00000   3.00000   0.00000   1.00000
    Epsilon       3.00000   3.00000   3.00000   1.00000   0.00000

      +-------------------Gamma
      !
      !                             +---------Delta
    --3-----------------------------1
      !                             +---------Epsilon
      !
      !         +---------Alpha
      +---------2
                +---------Beta

    remember: this is an unrooted tree!

    Between        And            Length
    -------        ---            ------
       3          Gamma             1.00000
       3             1              1.50000
       1          Delta             0.50000
       1          Epsilon           0.50000
       3             2              0.50000
       2          Alpha             0.50000
       2          Beta              0.50000