## EMBOSS: PHYLIP

# Original PHYLIP dnacomp 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

                         DNACOMP -- DNA Compatibility Program

    (c) Copyright  1986-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 compatibility method for  DNA  sequence  data.
    For a four-state character without a character-state tree, as in DNA sequences,
    the usual clique theorems cannot  be  applied.   The  approach  taken  in  this
    program  is  to  directly  evaluate  each  tree  topology  by counting how many
    substitutions are needed in each site, comparing this  to  the  minimum  number
    that might be needed (one less than the number of bases observed at that site),
    and then evaluating the number of sites which achieve the minimum number.  This
    is  the  evaluation  of  the  tree  (the  number  of compatible sites), and the
    topology is chosen so as to maximize that number.

         Compatibility methods originated with Le Quesne's (1969)  suggestion  that
    one  ought  to  look  for  trees  supported  by the largest number of perfectly
    fitting (compatible) characters.  Fitch (1975) showed  by  counterexample  that
    one could not use the pairwise compatibility methods used in CLIQUE to discover
    the largest clique of jointly compatible characters.

         The assumptions of this method are similar to those of CLIQUE.  In a paper
    in  the Biological Journal of the Linnean Society (1981b) I discuss this matter
    extensively.  In effect, the assumptions are that:

         1.  Each character evolves independently.

         2.  Different lineages evolve independently.

         3.  The ancestral base at each site is unknown.

         4.  The rates of change in most sites over the time spans involved in  the
    the divergence of the group are very small.

         5.  A few of the sites have very high rates of change.

         6.  We do not know in advance which are the high and which  the  low  rate
    sites.

    That these are the assumptions of compatibility methods has been documented  in
    a  series of papers of mine: (1973a, 1978b, 1979, 1981b, 1983b, 1988b).  For an
    opposing view arguing  that  arguments  such  as  mine  are  invalid  and  that
    parsimony  (and  perhaps compatibility) methods make no substantive assumptions
    such as these, see the papers by Farris (1983) and Sober (1983a, 1983b,  1988),
    but also read the exchange between Felsenstein and Sober (1986).

         There is, however, some reason to believe that the  present  criterion  is
    not the proper way to correct for the presence of some sites with high rates of
    change in nucleotide sequence data.  It can be argued that sites  showing  more
    than  two nucleotide states, even if those are compatible with the other sites,
    are also candidates for sites with high rates of change.  It might then be more
    proper to use DNAPARS with the Threshold option with a threshold value of 2.

         Change from an occupied site to a gap is counted as one change.  Reversion
    from  a  gap  to an occupied site is allowed and is also counted as one change.
    Note that this in effect assumes that a gap N bases long is N separate  events.
    This  may  be  an  overcorrection.   When we have nonoverlapping gaps, we could
    instead code a gap as a single event by changing all but the first "-"  in  the
    gap into "?" characters.  In this way only the first base of the gap causes the
    program to infer a change.

         The input data is standard.  The first line of the input file contains the
    number  of  species  and  the  number of sites.  If the Weights option is being
    used, there must also be a W in this first line to signal its presence.   There
    are  only  two options requiring information to be present in the input file, W
    (Weights) and U (User tree).  All options other than W are  invoked  using  the
    menu.

         Next come the species data.  Each sequence starts on a  new  line,  has  a
    ten-character  species  name  that  must  be blank-filled to be of that length,
    followed immediately by the species data in the one-letter code.  The sequences
    must  either  be  in the "interleaved" or "sequential" formats described in the
    Molecular Sequence Programs document.  The I option selects between them.   The
    sequences  can  have internal blanks in the sequence but there must be no extra
    blanks at the end of the terminated line.  Note that a blank  is  not  a  valid
    symbol for a deletion.

         The options are selected using an interactive menu.  The menu  looks  like
    this:

    DNA compatibility algorithm, version 3.5c

    Settings for this run:
      U                 Search for best tree?  Yes
      J   Randomize input order of sequences?  No. Use input order
      O                        Outgroup root?  No, use as outgroup species  1
      M           Analyze multiple data sets?  No
      I          Input sequences interleaved?  Yes
      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  Print steps & compatibility at sites  No
      5  Print sequences at all nodes of tree  No
      6       Write out trees onto tree file?  Yes

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

    The user either types "Y" (followed, of course, by a  carriage-return)  if  the
    settings  shown  are to be accepted, or the letter or digit corresponding to an
    option that is to be changed.

         The options U, J, O, M, and 0 are the usual ones.  They are  described  in
    the  main documentation file of this package.  Option I is the same as in other
    molecular sequence programs and is described in the documentation file for  the
    sequence programs.

         The O (outgroup) option has no effect if the U (user-defined tree)  option
    is  in  effect.   The  user-defined  trees  (option  U) fed in must be strictly
    bifurcating, with a two-way split at their base.

         The interpretation of weights (option W) in the case  of  a  compatibility
    method  is that they count how many times the character (in this case the site)
    is counted in the analysis.  Thus a character can be dropped from the  analysis
    by  assigning it zero weight.  On the other hand, giving it a weight of 5 means
    that in any clique it is in, it is counted as 5 characters when the size of the
    clique is evaluated.

         Output is standard: if option 1 is toggled on, the data  is  printed  out,
    with  the  convention  that "." means "the same as in the first species".  Then
    comes a list of equally parsimonious trees, and (if option 2 is toggled  on)  a
    table  of the number of changes of state required in each character.  If option
    5 is toggled on, a table is printed out  after  each  tree,  showing  for  each
    branch whether there are known to be changes in the branch, and what the states
    are inferred to have been at the top end of the branch.  If the inferred  state
    is  a  "?" or one of the IUB ambiguity symbols, there will be multiple equally-
    parsimonious assignments of states; the user must work these out for themselves
    by  hand.   A  "?" in the reconstructed states means that in addition to one or
    more bases, a gap may or may not be present.   If  option  6  is  left  in  its
    default  state the trees found will be written to a tree file, so that they are
    available to be used in other programs.

         If the U (User Tree) option is used and more than one  tree  is  supplied,
    the program also performs a statistical test of each of these trees against the
    best tree.  This test, which  is  a  version  of  the  test  proposed  by  Alan
    Templeton  (1983)  and  evaluated  in a test case by me (1985a).  It is closely
    parallel to a test using log likelihood differences due to Kishino and Hasegawa
    (1989),  and  uses  the mean and variance of weighted compatibility differences
    between trees, taken across sites.  If the mean  is  more  than  1.96  standard
    deviations  different then the trees are declared significantly different.  The
    program  prints  out  a  table  of  the  compatibilities  for  each  tree,  the
    differences  of  each  from  the  highest one, the variance of that quantity as
    determined  by  the  compatibility  differences  at  individual  sites,  and  a
    conclusion  as  to  whether that tree is or is not significantly worse than the
    best one.

         The algorithm is a straightforward modification of DNAPARS, but with  some
    extra  machinery  added  to  calculate, as each species is added, how many base
    changes are the minimum which could be required at that site.  The program runs
    fairly quickly.

         The constants which can be changed at the beginning of  the  program  are:
    the  name  length  "nmlngth", "maxtrees", the maximum number of trees which the
    program will store for output, and "maxuser", the maximum number of user  trees
    that can be used in the paired sites test.

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

        5   13
    Alpha     AACGUGGCCAAAU
    Beta      AAGGUCGCCAAAC
    Gamma     CAUUUCGUCACAA
    Delta     GGUAUUUCGGCCU
    Epsilon   GGGAUCUCGGCCC

    --- Contents of output file (if all numerical options are turned on) ---

    DNA compatibility algorithm, version 3.5c

    Name            Sequences
    ----            ---------

    Alpha        AACGUGGCCA AAU
    Beta         ..G..C.... ..C
    Gamma        C.UU.C.U.. C.A
    Delta        GGUA.UU.GG CC.

    Epsilon      GGGA.CU.GG CCC

    One most parsimonious tree found:

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

      remember: this is an unrooted tree!

    total number of compatible sites is       11.0

     steps in each site:
             0   1   2   3   4   5   6   7   8   9
         *-----------------------------------------
        0!       2   1   3   2   0   2   1   1   1
       10!   1   1   1   3

     compatibility (Y or N) of each site with this tree:

          0123456789
         *----------
       0 ! YYNYYYYYY
      10 !YYYN

    From    To     Any Steps?    State at upper node
                                 ( . means same as in the node below it on tree)

              1                AABGTSGCCA AAY
       1      2        maybe   .....C.... ...
       2      3         yes    V.KD...... C..
       3      4         yes    GG.A..T.GG .C.
       4   Epsilon     maybe   ..G....... ..C
       4   Delta        yes    ..T..T.... ..T
       3   Gamma        yes    C.TT...T.. ..A
       2   Beta        maybe   ..G....... ..C
       1   Alpha       maybe   ..C..G.... ..T