| 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> |
|---|
| 2 | <HTML> |
|---|
| 3 | <HEAD> |
|---|
| 4 | <TITLE>fitch</TITLE> |
|---|
| 5 | <META NAME="description" CONTENT="fitch"> |
|---|
| 6 | <META NAME="keywords" CONTENT="fitch"> |
|---|
| 7 | <META NAME="resource-type" CONTENT="document"> |
|---|
| 8 | <META NAME="distribution" CONTENT="global"> |
|---|
| 9 | <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1"> |
|---|
| 10 | </HEAD> |
|---|
| 11 | <BODY BGCOLOR="#ccffff"> |
|---|
| 12 | <DIV ALIGN=RIGHT> |
|---|
| 13 | version 3.6 |
|---|
| 14 | </DIV> |
|---|
| 15 | <P> |
|---|
| 16 | <DIV ALIGN=CENTER> |
|---|
| 17 | <H1>FITCH -- Fitch-Margoliash and Least-Squares Distance Methods</H1> |
|---|
| 18 | </DIV> |
|---|
| 19 | <P> |
|---|
| 20 | © Copyright 1986-2002 by the University of |
|---|
| 21 | Washington. Written by Joseph Felsenstein. Permission is granted to copy |
|---|
| 22 | this document provided that no fee is charged for it and that this copyright |
|---|
| 23 | notice is not removed. |
|---|
| 24 | <P> |
|---|
| 25 | This program carries out Fitch-Margoliash, Least Squares, |
|---|
| 26 | and a number of similar methods as described in the documentation |
|---|
| 27 | file for distance methods. |
|---|
| 28 | <P> |
|---|
| 29 | The options for FITCH are selected through the menu, which looks like |
|---|
| 30 | this: |
|---|
| 31 | <P> |
|---|
| 32 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 33 | <PRE> |
|---|
| 34 | |
|---|
| 35 | Fitch-Margoliash method version 3.6a3 |
|---|
| 36 | |
|---|
| 37 | Settings for this run: |
|---|
| 38 | D Method (F-M, Minimum Evolution)? Fitch-Margoliash |
|---|
| 39 | U Search for best tree? Yes |
|---|
| 40 | P Power? 2.00000 |
|---|
| 41 | - Negative branch lengths allowed? No |
|---|
| 42 | O Outgroup root? No, use as outgroup species 1 |
|---|
| 43 | L Lower-triangular data matrix? No |
|---|
| 44 | R Upper-triangular data matrix? No |
|---|
| 45 | S Subreplicates? No |
|---|
| 46 | G Global rearrangements? No |
|---|
| 47 | J Randomize input order of species? No. Use input order |
|---|
| 48 | M Analyze multiple data sets? No |
|---|
| 49 | 0 Terminal type (IBM PC, ANSI, none)? (none) |
|---|
| 50 | 1 Print out the data at start of run No |
|---|
| 51 | 2 Print indications of progress of run Yes |
|---|
| 52 | 3 Print out tree Yes |
|---|
| 53 | 4 Write out trees onto tree file? Yes |
|---|
| 54 | |
|---|
| 55 | Y to accept these or type the letter for one to change |
|---|
| 56 | |
|---|
| 57 | </PRE> |
|---|
| 58 | <P> |
|---|
| 59 | </TD></TR></TABLE> |
|---|
| 60 | <P> |
|---|
| 61 | Most of the input options |
|---|
| 62 | (U, P, -, O, L, R, S, J, and M) are as given in |
|---|
| 63 | the documentation page for distance matrix programs, and their input format is |
|---|
| 64 | the same as given there. The |
|---|
| 65 | U (User Tree) option has one additional feature when the N (Lengths) |
|---|
| 66 | option is used. This menu option will appear only if the U (User Tree) |
|---|
| 67 | option is selected. If N (Lengths) is set to "Yes" then if any branch |
|---|
| 68 | in the user tree has a branch length, that branch will not have its |
|---|
| 69 | length iterated. Thus you can prevent all branches from having their |
|---|
| 70 | lengths changed by giving them all lengths in the user tree, or hold |
|---|
| 71 | only one length unchanged by giving only that branch a length (such |
|---|
| 72 | as, for example, 0.00). You may find program RETREE useful for |
|---|
| 73 | adding and removing branch lengths from a tree. This option can |
|---|
| 74 | also be used to compute the Average Percent Standard Deviation for a |
|---|
| 75 | tree obtained from NEIGHBOR, for comparison with trees obtained by |
|---|
| 76 | FITCH or KITSCH. |
|---|
| 77 | <P> |
|---|
| 78 | The D (methods) option allows choice between the Fitch-Margoliash |
|---|
| 79 | criterion and the Minimum Evolution method (Kidd and Sgaramella-Zonta, 1971; |
|---|
| 80 | Rzhetsky and Nei, 1993). Minimum Evolution (not to be confused with |
|---|
| 81 | parsimony) uses the Fitch-Margoliash criterion to fit branch lengths to each |
|---|
| 82 | topology, but then chooses topologies based on their total branch length |
|---|
| 83 | (rather than the goodness of fit sum of squares). There is no |
|---|
| 84 | constraint on negative branch lengths in the Minimum Evolution method; |
|---|
| 85 | it sometimes gives rather strange results, as it can like solutions |
|---|
| 86 | that have large negative branch lengths, as these reduce the total |
|---|
| 87 | sum of branch lengths! |
|---|
| 88 | </PRE> |
|---|
| 89 | <P> |
|---|
| 90 | Another input option available in FITCH that is not available in KITSCH |
|---|
| 91 | or NEIGHBOR |
|---|
| 92 | is the G (Global) option. G is the |
|---|
| 93 | Global search option. This causes, after the last species is added to |
|---|
| 94 | the tree, each possible group to be removed and re-added. This improves the |
|---|
| 95 | result, since the position of every species is reconsidered. It |
|---|
| 96 | approximately triples the run-time of the program. It is not an option in |
|---|
| 97 | KITSCH because it is the default and is always in force there. The |
|---|
| 98 | O (Outgroup) option is described in the main |
|---|
| 99 | documentation file of this package. The O option has no effect if the |
|---|
| 100 | tree is a user-defined tree (if the U option is in effect). The |
|---|
| 101 | U (User Tree) option requires an unrooted tree; that is, it require |
|---|
| 102 | that the tree have a trifurcation at its base: |
|---|
| 103 | <P> |
|---|
| 104 | ((A,B),C,(D,E)); |
|---|
| 105 | <P> |
|---|
| 106 | The output consists of an unrooted tree and the lengths of the |
|---|
| 107 | interior segments. The sum of squares is printed out, and if <EM>P = 2.0</EM> |
|---|
| 108 | Fitch and Margoliash's "average percent standard deviation" is also computed |
|---|
| 109 | and printed out. This is the sum of squares, divided by |
|---|
| 110 | N-2, and |
|---|
| 111 | then square-rooted and then multiplied by 100 (n is the number of |
|---|
| 112 | species on the tree): |
|---|
| 113 | <P> |
|---|
| 114 | APSD = ( SSQ / (N-2) )<SUP>1/2</SUP> x 100. |
|---|
| 115 | <P> |
|---|
| 116 | where <EM>N</EM> is the total number of off-diagonal distance measurements that |
|---|
| 117 | are in the (square) distance matrix. If the S (subreplication) option |
|---|
| 118 | is in force it is instead the sum of the numbers of replicates in all the |
|---|
| 119 | non-diagonal |
|---|
| 120 | cells of the distance matrix. But if the L or R option is also in effect, so |
|---|
| 121 | that the distance matrix read in is lower- or upper-triangular, then the |
|---|
| 122 | sum of replicates is only over those cells actually read in. If S is not in |
|---|
| 123 | force, the number of replicates in |
|---|
| 124 | each cell is assumed to be 1, so that <EM>N</EM> is <EM>n(n-1)</EM>, |
|---|
| 125 | where <EM>n</EM> is the number |
|---|
| 126 | of species. The <EM>APSD</EM> gives an indication of the average percentage |
|---|
| 127 | error. The number of trees examined is also printed out. |
|---|
| 128 | <P> |
|---|
| 129 | The constants |
|---|
| 130 | available for modification at the beginning of the program are: |
|---|
| 131 | "smoothings", which gives the number of passes through |
|---|
| 132 | the algorithm which adjusts the lengths of the segments of the tree so |
|---|
| 133 | as to minimize the sum of squares, "delta", which controls the size of |
|---|
| 134 | improvement in sum of squares that is used to control the number of |
|---|
| 135 | iterations improving branch lengths, |
|---|
| 136 | and "epsilonf", |
|---|
| 137 | which defines a small quantity needed in |
|---|
| 138 | some of the calculations. There is no feature saving multiply trees |
|---|
| 139 | tied for best, |
|---|
| 140 | partly because we do not expect exact ties except in cases where the branch |
|---|
| 141 | lengths make the nature of the tie obvious, as when a branch is of zero |
|---|
| 142 | length. |
|---|
| 143 | <P> |
|---|
| 144 | The algorithm can be slow. As the number of species |
|---|
| 145 | rises, so does the number of distances from each species to the others. The |
|---|
| 146 | speed of this algorithm will thus rise as the fourth power of the |
|---|
| 147 | number of species, rather than as the third power as do most of the |
|---|
| 148 | others. Hence it is expected to get very slow as the number of species |
|---|
| 149 | is made larger. |
|---|
| 150 | <P> |
|---|
| 151 | <HR> |
|---|
| 152 | <P> |
|---|
| 153 | <H3>TEST DATA SET</H3> |
|---|
| 154 | <P> |
|---|
| 155 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 156 | <PRE> |
|---|
| 157 | 7 |
|---|
| 158 | Bovine 0.0000 1.6866 1.7198 1.6606 1.5243 1.6043 1.5905 |
|---|
| 159 | Mouse 1.6866 0.0000 1.5232 1.4841 1.4465 1.4389 1.4629 |
|---|
| 160 | Gibbon 1.7198 1.5232 0.0000 0.7115 0.5958 0.6179 0.5583 |
|---|
| 161 | Orang 1.6606 1.4841 0.7115 0.0000 0.4631 0.5061 0.4710 |
|---|
| 162 | Gorilla 1.5243 1.4465 0.5958 0.4631 0.0000 0.3484 0.3083 |
|---|
| 163 | Chimp 1.6043 1.4389 0.6179 0.5061 0.3484 0.0000 0.2692 |
|---|
| 164 | Human 1.5905 1.4629 0.5583 0.4710 0.3083 0.2692 0.0000 |
|---|
| 165 | </PRE> |
|---|
| 166 | </TD></TR></TABLE> |
|---|
| 167 | <P> |
|---|
| 168 | <HR> |
|---|
| 169 | <P> |
|---|
| 170 | <H3>OUTPUT FROM TEST DATA SET (with all numerical options on)</H3> |
|---|
| 171 | <P> |
|---|
| 172 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 173 | <PRE> |
|---|
| 174 | |
|---|
| 175 | 7 Populations |
|---|
| 176 | |
|---|
| 177 | Fitch-Margoliash method version 3.6a3 |
|---|
| 178 | |
|---|
| 179 | __ __ 2 |
|---|
| 180 | \ \ (Obs - Exp) |
|---|
| 181 | Sum of squares = /_ /_ ------------ |
|---|
| 182 | 2 |
|---|
| 183 | i j Obs |
|---|
| 184 | |
|---|
| 185 | Negative branch lengths not allowed |
|---|
| 186 | |
|---|
| 187 | |
|---|
| 188 | Name Distances |
|---|
| 189 | ---- --------- |
|---|
| 190 | |
|---|
| 191 | Bovine 0.00000 1.68660 1.71980 1.66060 1.52430 1.60430 |
|---|
| 192 | 1.59050 |
|---|
| 193 | Mouse 1.68660 0.00000 1.52320 1.48410 1.44650 1.43890 |
|---|
| 194 | 1.46290 |
|---|
| 195 | Gibbon 1.71980 1.52320 0.00000 0.71150 0.59580 0.61790 |
|---|
| 196 | 0.55830 |
|---|
| 197 | Orang 1.66060 1.48410 0.71150 0.00000 0.46310 0.50610 |
|---|
| 198 | 0.47100 |
|---|
| 199 | Gorilla 1.52430 1.44650 0.59580 0.46310 0.00000 0.34840 |
|---|
| 200 | 0.30830 |
|---|
| 201 | Chimp 1.60430 1.43890 0.61790 0.50610 0.34840 0.00000 |
|---|
| 202 | 0.26920 |
|---|
| 203 | Human 1.59050 1.46290 0.55830 0.47100 0.30830 0.26920 |
|---|
| 204 | 0.00000 |
|---|
| 205 | |
|---|
| 206 | |
|---|
| 207 | +---------------------------------------------Mouse |
|---|
| 208 | ! |
|---|
| 209 | ! +------Human |
|---|
| 210 | ! +--5 |
|---|
| 211 | ! +-4 +--------Chimp |
|---|
| 212 | ! ! ! |
|---|
| 213 | ! +--3 +---------Gorilla |
|---|
| 214 | ! ! ! |
|---|
| 215 | 1------------------------2 +-----------------Orang |
|---|
| 216 | ! ! |
|---|
| 217 | ! +---------------------Gibbon |
|---|
| 218 | ! |
|---|
| 219 | +------------------------------------------------------Bovine |
|---|
| 220 | |
|---|
| 221 | |
|---|
| 222 | remember: this is an unrooted tree! |
|---|
| 223 | |
|---|
| 224 | Sum of squares = 0.01375 |
|---|
| 225 | |
|---|
| 226 | Average percent standard deviation = 1.85418 |
|---|
| 227 | |
|---|
| 228 | Between And Length |
|---|
| 229 | ------- --- ------ |
|---|
| 230 | 1 Mouse 0.76985 |
|---|
| 231 | 1 2 0.41983 |
|---|
| 232 | 2 3 0.04986 |
|---|
| 233 | 3 4 0.02121 |
|---|
| 234 | 4 5 0.03695 |
|---|
| 235 | 5 Human 0.11449 |
|---|
| 236 | 5 Chimp 0.15471 |
|---|
| 237 | 4 Gorilla 0.15680 |
|---|
| 238 | 3 Orang 0.29209 |
|---|
| 239 | 2 Gibbon 0.35537 |
|---|
| 240 | 1 Bovine 0.91675 |
|---|
| 241 | |
|---|
| 242 | |
|---|
| 243 | </PRE> |
|---|
| 244 | </TD></TR></TABLE> |
|---|
| 245 | <P> |
|---|
| 246 | </BODY> |
|---|
| 247 | </HTML> |
|---|
