| 1 | <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN"> |
|---|
| 2 | <HTML> |
|---|
| 3 | <HEAD> |
|---|
| 4 | <TITLE>kitsch</TITLE> |
|---|
| 5 | <META NAME="description" CONTENT="kitsch"> |
|---|
| 6 | <META NAME="keywords" CONTENT="kitsch"> |
|---|
| 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>KITSCH -- Fitch-Margoliash and Least Squares Methods<BR> |
|---|
| 18 | with Evolutionary Clock</H1> |
|---|
| 19 | </DIV> |
|---|
| 20 | <P> |
|---|
| 21 | © Copyright 1986-2002 by the University of |
|---|
| 22 | Washington. Written by Joseph Felsenstein. Permission is granted to copy |
|---|
| 23 | this document provided that no fee is charged for it and that this copyright |
|---|
| 24 | notice is not removed. |
|---|
| 25 | <P> |
|---|
| 26 | This program carries out the Fitch-Margoliash and Least Squares methods, |
|---|
| 27 | plus a variety of others of the same family, with the assumption that all |
|---|
| 28 | tip species are contemporaneous, and that there is an evolutionary clock |
|---|
| 29 | (in effect, a molecular clock). This means that branches of the tree cannot |
|---|
| 30 | be of arbitrary length, but are constrained so that the total |
|---|
| 31 | length from the root of |
|---|
| 32 | the tree to any species is the same. The quantity minimized is the same |
|---|
| 33 | weighted sum of squares described in the Distance Matrix Methods documentation |
|---|
| 34 | file. |
|---|
| 35 | <P> |
|---|
| 36 | The options are set using the menu: |
|---|
| 37 | <P> |
|---|
| 38 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 39 | <PRE> |
|---|
| 40 | |
|---|
| 41 | Fitch-Margoliash method with contemporary tips, version 3.6a3 |
|---|
| 42 | |
|---|
| 43 | Settings for this run: |
|---|
| 44 | D Method (F-M, Minimum Evolution)? Fitch-Margoliash |
|---|
| 45 | U Search for best tree? Yes |
|---|
| 46 | P Power? 2.00000 |
|---|
| 47 | - Negative branch lengths allowed? No |
|---|
| 48 | L Lower-triangular data matrix? No |
|---|
| 49 | R Upper-triangular data matrix? No |
|---|
| 50 | S Subreplicates? No |
|---|
| 51 | J Randomize input order of species? No. Use input order |
|---|
| 52 | M Analyze multiple data sets? No |
|---|
| 53 | 0 Terminal type (IBM PC, ANSI, none)? (none) |
|---|
| 54 | 1 Print out the data at start of run No |
|---|
| 55 | 2 Print indications of progress of run Yes |
|---|
| 56 | 3 Print out tree Yes |
|---|
| 57 | 4 Write out trees onto tree file? Yes |
|---|
| 58 | |
|---|
| 59 | Y to accept these or type the letter for one to change |
|---|
| 60 | |
|---|
| 61 | </PRE> |
|---|
| 62 | </TD></TR></TABLE> |
|---|
| 63 | <P> |
|---|
| 64 | Most of the options are described in the Distance Matrix Programs documentation |
|---|
| 65 | file. |
|---|
| 66 | <P> |
|---|
| 67 | The D (methods) option allows choice between the Fitch-Margoliash |
|---|
| 68 | criterion and the Minimum Evolution method (Kidd and Sgaramella-Zonta, 1971; |
|---|
| 69 | Rzhetsky and Nei, 1993). Minimum Evolution (not to be confused with |
|---|
| 70 | parsimony) uses the Fitch-Margoliash criterion to fit branch lengths to each |
|---|
| 71 | topology, but then chooses topologies based on their total branch length |
|---|
| 72 | (rather than the goodness of fit sum of squares). There is no |
|---|
| 73 | constraint on negative branch lengths in the Minimum Evolution method; |
|---|
| 74 | it sometimes gives rather strange results, as it can like solutions |
|---|
| 75 | that have large negative branch lengths, as these reduce the total |
|---|
| 76 | sum of branch lengths! |
|---|
| 77 | <P> |
|---|
| 78 | Note that the User Trees (used by option U) must be |
|---|
| 79 | rooted trees (with a bifurcation at their base). If you take a user |
|---|
| 80 | tree from FITCH and try to evaluate it in KITSCH, it must first be |
|---|
| 81 | rooted. This can be done using RETREE. Of the options |
|---|
| 82 | available in FITCH, the O option is |
|---|
| 83 | not available, as KITSCH estimates a rooted tree which cannot be |
|---|
| 84 | rerooted, and the G option is not |
|---|
| 85 | available, as global rearrangement is the default condition anyway. It |
|---|
| 86 | is also not possible to specify that specific branch lengths of a user tree |
|---|
| 87 | be retained when it is read into KITSCH, unless all of them are present. In |
|---|
| 88 | that case the tree should be properly clocklike. Readers who wonder why |
|---|
| 89 | we have not provided the feature of holding some of the user tree branch |
|---|
| 90 | lengths constant while iterating others are invited to tell us how they |
|---|
| 91 | would do it. As you consider particular possible patterns of branch |
|---|
| 92 | lengths you will find that the matter is not at all simple. |
|---|
| 93 | <P> |
|---|
| 94 | If you use a User Tree (option U) with branch lengths with KITSCH, and the |
|---|
| 95 | tree is not clocklike, when two branch lengths give conflicting positions |
|---|
| 96 | for a node, KITSCH will use the first of them and ignore the other. Thus |
|---|
| 97 | the user tree: |
|---|
| 98 | <P> |
|---|
| 99 | <PRE> |
|---|
| 100 | ((A:0.1,B:0.2):0.4,(C:0.06,D:0.01):43); |
|---|
| 101 | </PRE> |
|---|
| 102 | <P> |
|---|
| 103 | is nonclocklike, so it will be treated as if it were actually the tree: |
|---|
| 104 | <P> |
|---|
| 105 | <PRE> |
|---|
| 106 | ((A:0.1,B:0.1):0.4,(C:0.06,D:0.06):44); |
|---|
| 107 | </PRE> |
|---|
| 108 | <P> |
|---|
| 109 | The input is exactly the same as described in the Distance Matrix Methods |
|---|
| 110 | documentation file. The output is a rooted tree, together with the sum of |
|---|
| 111 | squares, the number of tree topologies searched, and, if the power P is at |
|---|
| 112 | its default value of 2.0, the Average Percent Standard Deviation is also |
|---|
| 113 | supplied. The lengths of the branches of the tree are given in a table, |
|---|
| 114 | that also shows for each branch the time at the upper end of the |
|---|
| 115 | branch. "Time" here really means cumulative branch length from the root, going |
|---|
| 116 | upwards (on the printed diagram, rightwards). For each branch, the |
|---|
| 117 | "time" given is for the node at the right (upper) end of the branch. It |
|---|
| 118 | is important to realize that the branch lengths are not exactly proportional to |
|---|
| 119 | the lengths drawn on the printed tree diagram! In particular, short |
|---|
| 120 | branches are exaggerated in the length on that diagram so that they are |
|---|
| 121 | more visible. |
|---|
| 122 | <P> |
|---|
| 123 | The method may be considered as providing an estimate of the |
|---|
| 124 | phylogeny. Alternatively, it can be considered as a phenetic clustering of |
|---|
| 125 | the tip species. This method minimizes an objective function, the sum of |
|---|
| 126 | squares, |
|---|
| 127 | not only setting the levels of the clusters so as to do so, but rearranging |
|---|
| 128 | the hierarchy of clusters to try to find alternative clusterings that |
|---|
| 129 | give a lower overall sum of squares. When the power option P is set to a |
|---|
| 130 | value of <EM>P = 0.0</EM>, so that we are minimizing a simple sum of squares |
|---|
| 131 | of the differences between the observed distance matrix and the expected one, |
|---|
| 132 | the method is very close in spirit to Unweighted Pair Group Arithmetic Average |
|---|
| 133 | Clustering (UPGMA), also called Average-Linkage Clustering. If the topology of |
|---|
| 134 | the tree is fixed and there turn out to be no branches of negative length, its |
|---|
| 135 | result should be the same as UPGMA in that case. But since it tries |
|---|
| 136 | alternative topologies and (unless |
|---|
| 137 | the N option is set) it combines nodes that otherwise could result in a reversal |
|---|
| 138 | of levels, it is possible for it to give a different, and better, result than |
|---|
| 139 | simple sequential clustering. Of course UPGMA itself is available as an |
|---|
| 140 | option in program NEIGHBOR. |
|---|
| 141 | <P> |
|---|
| 142 | The U (User Tree) option requires a bifurcating tree, unlike FITCH, which |
|---|
| 143 | requires an unrooted tree with a trifurcation at its base. Thus the tree |
|---|
| 144 | shown below would be written: |
|---|
| 145 | <P> |
|---|
| 146 | ((D,E),(C,(A,B))); |
|---|
| 147 | <P> |
|---|
| 148 | If a tree with a trifurcation at the base is by mistake fed into the U option |
|---|
| 149 | of KITSCH then some of its species (the entire rightmost furc, in fact) will be |
|---|
| 150 | ignored and too small a tree read in. This should result in an error message |
|---|
| 151 | and the program should stop. It is important to understand the |
|---|
| 152 | difference between the User Tree formats for KITSCH and FITCH. You may want |
|---|
| 153 | to use RETREE to convert a user tree that is suitable for FITCH into one |
|---|
| 154 | suitable for KITSCH or vice versa. |
|---|
| 155 | <P> |
|---|
| 156 | An important use of this method will be to do a formal statistical test of |
|---|
| 157 | the evolutionary clock hypothesis. This can be done by comparing the sums |
|---|
| 158 | of squares achieved by FITCH and by KITSCH, BUT SOME CAVEATS ARE |
|---|
| 159 | NECESSARY. First, the assumption is that the observed distances are truly |
|---|
| 160 | independent, that no original data item contributes to more than one of them |
|---|
| 161 | (not counting the two reciprocal distances from i to j and from j to i). THIS |
|---|
| 162 | WILL NOT HOLD IF THE DISTANCES ARE OBTAINED FROM GENE FREQUENCIES, FROM |
|---|
| 163 | MORPHOLOGICAL CHARACTERS, OR FROM MOLECULAR SEQUENCES. It may be invalid even |
|---|
| 164 | for immunological distances and levels of DNA hybridization, provided that the |
|---|
| 165 | use of common standard for all members of a row or column allows an error in |
|---|
| 166 | the measurement of the standard to affect all these distances |
|---|
| 167 | simultaneously. It will also be invalid if the numbers have been collected in |
|---|
| 168 | experimental groups, each measured by taking differences from a common standard |
|---|
| 169 | which itself is measured with error. Only if the numbers in different cells |
|---|
| 170 | are measured from independent standards can we depend on the statistical |
|---|
| 171 | model. The details of the test and the assumptions are discussed in my review |
|---|
| 172 | paper on distance methods (Felsenstein, 1984a). For further and sometimes |
|---|
| 173 | irrelevant controversy on these matters see the papers by Farris (1981, |
|---|
| 174 | 1985, 1986) and myself (Felsenstein, 1986, 1988b). |
|---|
| 175 | <P> |
|---|
| 176 | A second caveat is that the distances must be expected to rise linearly with |
|---|
| 177 | time, not according to any other curve. Thus it may be necessary to transform |
|---|
| 178 | the distances to achieve an expected linearity. If the distances have an upper |
|---|
| 179 | limit beyond which they could not go, this is a signal that linearity may |
|---|
| 180 | not hold. It is also VERY important to choose the power <EM>P</EM> at a value |
|---|
| 181 | that results in the standard deviation of the variation of the observed from the |
|---|
| 182 | expected distances being the <EM>P/2</EM>-th power of the expected distance. |
|---|
| 183 | <P> |
|---|
| 184 | To carry out the test, fit the same data with both FITCH and KITSCH, |
|---|
| 185 | and record the two sums of squares. If the topology has turned out the |
|---|
| 186 | same, we have <EM>N = n(n-1)/2</EM> distances which have been fit with |
|---|
| 187 | <EM>2n-3</EM> |
|---|
| 188 | parameters in FITCH, and with <EM>n-1</EM> parameters in KITSCH. Then the |
|---|
| 189 | difference between <EM>S(K)</EM> and <EM>S(F)</EM> has <EM>d<SUB>1</SUB> = n-2</EM> |
|---|
| 190 | degrees of freedom. It is |
|---|
| 191 | statistically independent of the value of <EM>S(F)</EM>, which has |
|---|
| 192 | <EM>d<SUB>2</SUB> = N-(2n-3)</EM> |
|---|
| 193 | degrees of freedom. The ratio of mean squares |
|---|
| 194 | <P> |
|---|
| 195 | <PRE> |
|---|
| 196 | [S(K)-S(F)]/d<SUB>1</SUB> |
|---|
| 197 | ---------------- |
|---|
| 198 | S(F)/d<SUB>2</SUB> |
|---|
| 199 | </PRE> |
|---|
| 200 | <P> |
|---|
| 201 | should, under the |
|---|
| 202 | evolutionary clock, have an F distribution with <EM>n-2</EM> and |
|---|
| 203 | <EM>N-(2n-3)</EM> degrees of |
|---|
| 204 | freedom respectively. The test desired is that the F ratio is in the upper |
|---|
| 205 | tail (say the upper 5%) of its distribution. If the S (subreplication) |
|---|
| 206 | option is in |
|---|
| 207 | effect, the above degrees of freedom must be modified by noting that |
|---|
| 208 | N is not <EM>n(n-1)/2</EM> but is the sum of the numbers of replicates of all |
|---|
| 209 | cells in the distance matrix read in, which may be either square or |
|---|
| 210 | triangular. A further explanation of the |
|---|
| 211 | statistical test of the clock is given in a paper of mine (Felsenstein, 1986). |
|---|
| 212 | <P> |
|---|
| 213 | The program uses a similar tree construction method to the other programs |
|---|
| 214 | in the package and, like them, is not guaranteed to give the best-fitting |
|---|
| 215 | tree. The assignment of the branch lengths for a given topology is a |
|---|
| 216 | least squares fit, subject to the constraints against negative branch lengths, |
|---|
| 217 | and should not be able to be improved upon. KITSCH runs more quickly than |
|---|
| 218 | FITCH. |
|---|
| 219 | <P> |
|---|
| 220 | The constant |
|---|
| 221 | available for modification at the beginning of the program is |
|---|
| 222 | "epsilon", which defines a small quantity needed in |
|---|
| 223 | some of the calculations. There is no feature saving multiply trees |
|---|
| 224 | tied for best, |
|---|
| 225 | because exact ties are not expected, except in cases where it should be |
|---|
| 226 | obvious from the tree printed out what is the nature of the tie (as when an |
|---|
| 227 | interior branch is of length zero). |
|---|
| 228 | <P> |
|---|
| 229 | <HR> |
|---|
| 230 | <P> |
|---|
| 231 | <H3>TEST DATA SET</H3> |
|---|
| 232 | <P> |
|---|
| 233 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 234 | <PRE> |
|---|
| 235 | 7 |
|---|
| 236 | Bovine 0.0000 1.6866 1.7198 1.6606 1.5243 1.6043 1.5905 |
|---|
| 237 | Mouse 1.6866 0.0000 1.5232 1.4841 1.4465 1.4389 1.4629 |
|---|
| 238 | Gibbon 1.7198 1.5232 0.0000 0.7115 0.5958 0.6179 0.5583 |
|---|
| 239 | Orang 1.6606 1.4841 0.7115 0.0000 0.4631 0.5061 0.4710 |
|---|
| 240 | Gorilla 1.5243 1.4465 0.5958 0.4631 0.0000 0.3484 0.3083 |
|---|
| 241 | Chimp 1.6043 1.4389 0.6179 0.5061 0.3484 0.0000 0.2692 |
|---|
| 242 | Human 1.5905 1.4629 0.5583 0.4710 0.3083 0.2692 0.0000 |
|---|
| 243 | </PRE> |
|---|
| 244 | </TD></TR></TABLE> |
|---|
| 245 | <P> |
|---|
| 246 | <HR> |
|---|
| 247 | <P> |
|---|
| 248 | <H3>TEST SET OUTPUT FILE (with all numerical options on)</H3> |
|---|
| 249 | <P> |
|---|
| 250 | <TABLE><TR><TD BGCOLOR=white> |
|---|
| 251 | <PRE> |
|---|
| 252 | |
|---|
| 253 | 7 Populations |
|---|
| 254 | |
|---|
| 255 | Fitch-Margoliash method with contemporary tips, version 3.6a3 |
|---|
| 256 | |
|---|
| 257 | __ __ 2 |
|---|
| 258 | \ \ (Obs - Exp) |
|---|
| 259 | Sum of squares = /_ /_ ------------ |
|---|
| 260 | 2 |
|---|
| 261 | i j Obs |
|---|
| 262 | |
|---|
| 263 | negative branch lengths not allowed |
|---|
| 264 | |
|---|
| 265 | |
|---|
| 266 | Name Distances |
|---|
| 267 | ---- --------- |
|---|
| 268 | |
|---|
| 269 | Bovine 0.00000 1.68660 1.71980 1.66060 1.52430 1.60430 |
|---|
| 270 | 1.59050 |
|---|
| 271 | Mouse 1.68660 0.00000 1.52320 1.48410 1.44650 1.43890 |
|---|
| 272 | 1.46290 |
|---|
| 273 | Gibbon 1.71980 1.52320 0.00000 0.71150 0.59580 0.61790 |
|---|
| 274 | 0.55830 |
|---|
| 275 | Orang 1.66060 1.48410 0.71150 0.00000 0.46310 0.50610 |
|---|
| 276 | 0.47100 |
|---|
| 277 | Gorilla 1.52430 1.44650 0.59580 0.46310 0.00000 0.34840 |
|---|
| 278 | 0.30830 |
|---|
| 279 | Chimp 1.60430 1.43890 0.61790 0.50610 0.34840 0.00000 |
|---|
| 280 | 0.26920 |
|---|
| 281 | Human 1.59050 1.46290 0.55830 0.47100 0.30830 0.26920 |
|---|
| 282 | 0.00000 |
|---|
| 283 | |
|---|
| 284 | |
|---|
| 285 | +-------Human |
|---|
| 286 | +-6 |
|---|
| 287 | +----5 +-------Chimp |
|---|
| 288 | ! ! |
|---|
| 289 | +---4 +---------Gorilla |
|---|
| 290 | ! ! |
|---|
| 291 | +------------------------3 +--------------Orang |
|---|
| 292 | ! ! |
|---|
| 293 | +----2 +------------------Gibbon |
|---|
| 294 | ! ! |
|---|
| 295 | --1 +-------------------------------------------Mouse |
|---|
| 296 | ! |
|---|
| 297 | +------------------------------------------------Bovine |
|---|
| 298 | |
|---|
| 299 | |
|---|
| 300 | Sum of squares = 0.107 |
|---|
| 301 | |
|---|
| 302 | Average percent standard deviation = 5.16213 |
|---|
| 303 | |
|---|
| 304 | From To Length Height |
|---|
| 305 | ---- -- ------ ------ |
|---|
| 306 | |
|---|
| 307 | 6 Human 0.13460 0.81285 |
|---|
| 308 | 5 6 0.02836 0.67825 |
|---|
| 309 | 6 Chimp 0.13460 0.81285 |
|---|
| 310 | 4 5 0.07638 0.64990 |
|---|
| 311 | 5 Gorilla 0.16296 0.81285 |
|---|
| 312 | 3 4 0.06639 0.57352 |
|---|
| 313 | 4 Orang 0.23933 0.81285 |
|---|
| 314 | 2 3 0.42923 0.50713 |
|---|
| 315 | 3 Gibbon 0.30572 0.81285 |
|---|
| 316 | 1 2 0.07790 0.07790 |
|---|
| 317 | 2 Mouse 0.73495 0.81285 |
|---|
| 318 | 1 Bovine 0.81285 0.81285 |
|---|
| 319 | |
|---|
| 320 | </PRE> |
|---|
| 321 | </TD></TR></TABLE> |
|---|
| 322 | </BODY> |
|---|
| 323 | </HTML> |
|---|
