version 3.5c


                 PROTPARS -- Protein Sequence Parsimony Method


(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 infers an unrooted phylogeny from protein sequences, using  a
new  method  intermediate  between the approaches of Eck and Dayhoff (1966) and
Fitch (1971).  Eck and Dayhoff (1966) allowed any amino acid to change  to  any
other,  and  counted  the  number  of such changes needed to evolve the protein
sequences on each given  phylogeny.   This  has  the  problem  that  it  allows
replacements  which  are  not  consistent  with the genetic code, counting them
equally with replacements that are  consistent.   Fitch,  on  the  other  hand,
counted  the minimum number of nucleotide substitutions that would be needed to
achieve the given protein sequences.  This counts silent changes  equally  with
those that change the amino acid.

     The present method insists that any changes of amino  acid  be  consistent
with  the  genetic  code  so  that, for example, lysine is allowed to change to
methionine but not to proline.  However, changes between two amino acids via  a
third are allowed and counted as two changes if each of the two replacements is
individually allowed.  This sometimes allows changes that at  first  sight  you
would  think  should  be  outlawed.   Thus  we can change from phenylalanine to
glutamine via leucine in two steps total.  Consulting  the  genetic  code,  you
will  find  that  there  is  a leucine codon one step away from a phenylalanine
codon, and a leucine codon one step away from glutamine.  But they are not  the
same  leucine  codon.   It  actually takes three base substitutions to get from
either of the phenylalanine codons UUU and  UUC  to  either  of  the  glutamine
codons  CAA  or CAG.  Why then does this program count only two?  The answer is
that recent DNA sequence comparisons seem to show that synonymous  changes  are
considerably  faster  and  easier than ones that change the amino acid.  We are
assuming that, in effect, synonymous changes occur so much  more  readily  that
they  need  not  be  counted.  Thus, in the chain of changes  UUU (Phe) --> CUU
(Leu) --> CUA (Leu) --> CAA (Glu), the middle one is  not  counted  because  it
does not change the amino acid (leucine).

     To maintain consistency with the genetic code, it  is  necessary  for  the
program internally to treat serine as two separate states (ser1 and ser2) since
the two groups of serine codons are not adjacent in the code.  Changes  to  the
state  "deletion"  are  counted  as  three  steps to prevent the algorithm from
assuming unnecessary deletions.  The state "unknown" is simply  taken  to  mean
that  the  amino acid, which has not been determined, will in each tree that is
evaluated be assumed be whichever one causes the fewest steps.

     The assumptions of this method  (which  has  not  been  described  in  the
literature), are thus something like this:

       1.  Change in different sites is independent.

       2.  Change in different lineages is independent.

       3.  The probability of a base substitution that changes the  amino  acid
          sequence  is  small  over the lengths of time involved in a branch of
          the phylogeny.

       4.  The  expected  amounts  of  change  in  different  branches  of  the


          phylogeny  do  not  vary  by  so much that two changes in a high-rate
          branch are more probable than one change in a low-rate branch.

       5.  The expected amounts of change do not vary enough among  sites  that
          two changes in one site are more probable than one change in another.

       6.  The probability of a base change that is synonymous is  much  higher
          than the probability of a change that is not synonymous.

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

     The input for the program is fairly standard.  The first line contains the
number  of  species  and  the number of amino acid positions (counting any stop
codons that you want to include).  These are followed on the same line  by  the
options.  The only options which need information in the input file are U (User
Tree) and W (Weights).  They are as described in the main  documentation  file.
If  the  W  (Weights) option is used there must be a W in the first line of the
input file.  For the U option the tree provided must be  a  rooted  bifurcating
tree,  with  the  root placed anywhere you want, since that root placement does
not affect anything.

     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 protein sequences are given by the one-letter code used  by  described
in  the  Molecular  Sequence  Programs  documentation  file.   Note that if two
polypeptide chains are being used that are of different  length  owing  to  one
terminating before the other, they should be coded as (say)

             HIINMA*????
             HIPNMGVWABT

since after the stop codon we do not definitely know  that  there  has  been  a
deletion,  and  do  not  know  what  amino  acid would have been there.  If DNA
studies tell us that there is DNA sequence in that region, then  we  could  use
"X" rather than "?".  Note that "X" means an unknown amino acid, but definitely
an amino acid, while "?" could mean either that or a deletion.  The distinction
is  often  significant  in  regions  where there are deletions: one may want to
encode a six-base deletion as "-?????" since that way  the  program  will  only
count  one  deletion,  not  six  deletion  events,  when  the  deletion arises.
However, if there are overlapping deletions it may not be so easy to know  what
coding is correct.

     One will usually want to use "?" after a stop codon, if one does not  know
what  amino  acid  is  there.  If the DNA sequence has been observed there, one
probably ought to resist putting in the amino acids that this  DNA  would  code
for,  and one should use "X" instead, because under the assumptions implicit in
this parsimony method, changes to any noncoding sequence are much  easier  than
changes  in  a coding region that change the amino acid, so that they shouldn't
be counted anyway!



     The options that require information in the input file are the W (Weights)
and  U  (User  Tree) options.  The form of this information is the standard one
described in the main documentation file.  For the U option the  tree  provided
must  be  a  rooted  bifurcating  tree, with the root placed anywhere you want,
since that root placement does not affect anything.

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


Protein parsimony algorithm, version 3.5c

Setting 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
  T              Use Threshold parsimony?  No, use ordinary parsimony
  C               Use which genetic code?  Universal
  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 out steps in each site  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, T, 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.  Option C allows the user to select among various
nuclear and mitochondrial genetic codes.  There is no provision for coping with
data where different genetic codes have been used in different organisms.

     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 position.  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
"?" there will be multiple equally-parsimonious assignments of states; the user
must work these out for themselves by hand.  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 step differences between trees, taken
across positions.  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 steps for each tree, the differences of each from  the  best  one,
the  variance  of  that  quantity  as  determined  by  the  step differences at
individual positions, and a conclusion as to whether that tree  is  or  is  not
significantly worse than the best one.

     The program is  derived  from  MIX  but  has  had  some  rather  elaborate
bookkeeping using sets of bits installed.  It is not a very fast program but is
speeded up substantially over version 3.2.


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

     5    10
Alpha     ABCDEFGHIK
Beta      AB--EFGHIK
Gamma     ?BCDSFG.??
Delta     CIKDEFGHIK
Epsilon   DIKDEFGHIK

---------CONTENTS OF OUTPUT FILE (with all numerical options on) ----------

Protein parsimony algorithm, version 3.5c

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

Alpha        ABCDEFGHIK
Beta         ..--......
Gamma        ?...S...??
Delta        CIK.......
Epsilon      DIK.......




     3 trees in all found




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

  remember: this is an unrooted tree!


requires a total of     14.000

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



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


         1                ANCDEFGHIK
  1      2         no     ..........
  2   Gamma        yes    ?B..S...??
  2      3         yes    ..?.......
  3      4         yes    ?IK.......
  4   Epsilon     maybe   D.........
  4   Delta        yes    C.........
  3   Beta         yes    .B--......
  1   Alpha       maybe   .B........





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

  remember: this is an unrooted tree!


requires a total of     14.000

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

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


         1                ANCDEFGHIK
  1      2         no     ..........
  2      3        maybe   ?.........
  3      4         yes    .IK.......
  4   Epsilon     maybe   D.........
  4   Delta        yes    C.........
  3   Gamma        yes    ?B..S...??
  2   Beta         yes    .B--......
  1   Alpha       maybe   .B........





           +--Epsilon
     +-----4
     !     +--Delta
  +--3


  !  !     +--Gamma
--1  +-----2
  !        +--Beta
  !
  +-----------Alpha

  remember: this is an unrooted tree!


requires a total of     14.000

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

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


         1                ANCDEFGHIK
  1      3         no     ..........
  3      4         yes    ?IK.......
  4   Epsilon     maybe   D.........
  4   Delta        yes    C.........
  3      2         no     ..........
  2   Gamma        yes    ?B..S...??
  2   Beta         yes    .B--......
  1   Alpha       maybe   .B........