fclique

 

Function

Largest clique program

Description

Finds the largest clique of mutually compatible characters, and the phylogeny which they recommend, for discrete character data with two states. The largest clique (or all cliques within a given size range of the largest one) are found by a very fast branch and bound search method. The method does not allow for missing data. For such cases the T (Threshold) option of PARS or MIX may be a useful alternative. Compatibility methods are particular useful when some characters are of poor quality and the rest of good quality, but when it is not known in advance which ones are which.

Algorithm

This program uses the compatibility method for unrooted two-state characters to obtain the largest cliques of characters and the trees which they suggest. This approach originated in the work of Le Quesne (1969), though the algorithms were not precisely specified until the later work of Estabrook, Johnson, and McMorris (1976a, 1976b). These authors proved the theorem that a group of two-state characters which were pairwise compatible would be jointly compatible. This program uses an algorithm inspired by the Kent Fiala - George Estabrook program CLINCH, though closer in detail to the algorithm of Bron and Kerbosch (1973). I am indebted to Kent Fiala for pointing out that paper to me, and to David Penny for decribing to me his branch-and-bound approach to finding largest cliques, from which I have also borrowed. I am particularly grateful to Kent Fiala for catching a bug in versions 2.0 and 2.1 which resulted in those versions failing to find all of the cliques which they should. The program computes a compatibility matrix for the characters, then uses a recursive procedure to examine all possible cliques of characters.

After one pass through all possible cliques, the program knows the size of the largest clique, and during a second pass it prints out the cliques of the right size. It also, along with each clique, prints out the tree suggested by that clique.

ASSUMPTIONS

Basically the following assumptions are made:
  1. Each character evolves independently.
  2. Different lineages evolve independently.
  3. The ancestral state is not known.
  4. Each character has a small chance of being one which evolves so rapidly, or is so thoroughly misinterpreted, that it provides no information on the tree.
  5. The probability of a single change in a character (other than in the high rate characters) is low but not as low as the probability of being one of these "bad" characters.
  6. The probability of two changes in a low-rate character is much less than the probability that it is a high-rate character.
  7. The true tree has segments which are not so unequal in length that two changes in a long are as easy to envisage as one change in a short segment.

The assumptions of compatibility methods have been treated in several of my papers (1978b, 1979, 1981b, 1988b), especially the 1981 paper. For an opposing view arguing that the parsimony methods make no substantive assumptions such as these, see the papers by Farris (1983) and Sober (1983a, 1983b), but also read the exchange between Felsenstein and Sober (1986).

A constant available for alteration at the beginning of the program is the form width, "FormWide", which you may want to change to make it as large as possible consistent with the page width available on your output device, so as to avoid the output of cliques and of trees getting wrapped around unnecessarily.

Usage

Here is a sample session with fclique 


% fclique 
Largest clique program
Phylip discrete states file: clique.dat
Phylip clique program output file [clique.fclique]: 


Output written to file "clique.fclique"

Tree written on file "clique.treefile"

Done.

Go to the input files for this example
Go to the output files for this example

Command line arguments 

   Standard (Mandatory) qualifiers:
  [-infile]            discretestates Phylip discrete states file
  [-outfile]           outfile    [*.fclique] Phylip clique program output
                                  file

   Additional (Optional) qualifiers (* if not always prompted):
   -ancfile            properties Phylip ancestral states file (optional)
   -factorfile         properties Phylip multistate factors file (optional)
   -weights            properties Phylip weights file (optional)
   -cliqmin            integer    [0] Minimum clique size (Integer 0 or more)
   -outgrno            integer    [0] Species number to use as outgroup
                                  (Integer 0 or more)
   -[no]trout          toggle     [Y] Write out trees to tree file
*  -outtreefile        outfile    [*.fclique] Phylip tree output file
                                  (optional)
   -printdata          boolean    [N] Print data at start of run
   -[no]progress       boolean    [Y] Print indications of progress of run
   -[no]treeprint      boolean    [Y] Print out tree
   -printcomp          boolean    [N] Print out compatibility matrix

   Advanced (Unprompted) qualifiers: (none)
   Associated qualifiers:

   "-outfile" associated qualifiers
   -odirectory2        string     Output directory

   "-outtreefile" associated qualifiers
   -odirectory         string     Output directory

   General qualifiers:
   -auto               boolean    Turn off prompts
   -stdout             boolean    Write first file to standard output
   -filter             boolean    Read first file from standard input, write
                                  first file to standard output
   -options            boolean    Prompt for standard and additional values
   -debug              boolean    Write debug output to program.dbg
   -verbose            boolean    Report some/full command line options
   -help               boolean    Report command line options. More
                                  information on associated and general
                                  qualifiers can be found with -help -verbose
   -warning            boolean    Report warnings
   -error              boolean    Report errors
   -fatal              boolean    Report fatal errors
   -die                boolean    Report dying program messages

Standard (Mandatory) qualifiers Allowed values Default
[-infile]
(Parameter 1)		 Phylip discrete states file Discrete states file  
[-outfile]
(Parameter 2)		 Phylip clique program output file Output file <*>.fclique
Additional (Optional) qualifiers Allowed values Default
-ancfile Phylip ancestral states file (optional) Property value(s)  
-factorfile Phylip multistate factors file (optional) Property value(s)  
-weights Phylip weights file (optional) Property value(s)  
-cliqmin Minimum clique size Integer 0 or more 0
-outgrno Species number to use as outgroup Integer 0 or more 0
-[no]trout Write out trees to tree file Toggle value Yes/No Yes
-outtreefile Phylip tree output file (optional) Output file <*>.fclique
-printdata Print data at start of run Boolean value Yes/No No
-[no]progress Print indications of progress of run Boolean value Yes/No Yes
-[no]treeprint Print out tree Boolean value Yes/No Yes
-printcomp Print out compatibility matrix Boolean value Yes/No No
Advanced (Unprompted) qualifiers Allowed values Default
(none)

Input file format

Input to the algorithm is standard, but the "?", "P", and "B" states are not allowed. This is a serious limitation of this program. If you want to find large cliques in data that have "?" states, I recommend that you use fmix instead with the -Threshold option and the value of the threshold set to 2.0. The theory underlying this is given in my paper on character weighting (Felsenstein, 1981b).

fclique reads discrete character data with 2 states.

Input files for usage example

File: clique.dat

     5    6
Alpha     110110
Beta      110000
Gamma     100110
Delta     001001
Epsilon   001110

Output file format

fclique writes the cliques to the text output file and a tree to a separate output file

Output files for usage example

File: clique.fclique


Largest clique program, version 3.67




Largest Cliques
------- -------


Characters: (  1  2  3  6)


  Tree and characters:

     2  1  3  6
     0  0  1  1

             +1-Delta     
       +0--1-+
  +--0-+     +--Epsilon   
  !    !
  !    +--------Gamma     
  !
  +-------------Alpha     
  !
  +-------------Beta      

remember: this is an unrooted tree!

File: clique.treefile

(((Delta,Epsilon),Gamma),Alpha,Beta);

Data files

None

Notes

None.

References

None.

Warnings

None.

Diagnostic Error Messages

None.

Exit status

It always exits with status 0.

Known bugs

None.

See also

Program name Description
eclique Largest clique program
edollop Dollo and polymorphism parsimony algorithm
edolpenny Penny algorithm Dollo or polymorphism
efactor Multistate to binary recoding program
emix Mixed parsimony algorithm
epenny Penny algorithm, branch-and-bound
fdollop Dollo and polymorphism parsimony algorithm
fdolpenny Penny algorithm Dollo or polymorphism
ffactor Multistate to binary recoding program
fmix Mixed parsimony algorithm
fmove Interactive mixed method parsimony
fpars Discrete character parsimony
fpenny Penny algorithm, branch-and-bound

Author(s)

This program is an EMBOSS conversion of a program written by Joe Felsenstein as part of his PHYLIP package.

Although we take every care to ensure that the results of the EMBOSS version are identical to those from the original package, we recommend that you check your inputs give the same results in both versions before publication.

Please report all bugs in the EMBOSS version to the EMBOSS bug team, not to the original author.

History

Written (2004) - Joe Felsenstein, University of Washington.

Converted (August 2004) to an EMBASSY program by the EMBOSS team.

Target users

This program is intended to be used by everyone and everything, from naive users to embedded scripts.