Context Navigation

dnapenny.html

Visit:

Last change on this file was 2176, checked in by westram, 21 years ago
* empty log message *
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 30.5 KB

Line
1	<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
2	<HTML>
3	<HEAD>
4	<TITLE>dnapenny</TITLE>
5	<META NAME="description" CONTENT="dnapenny">
6	<META NAME="keywords" CONTENT="dnapenny">
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>DNAPENNY - Branch and bound to find<BR>
18	all most parsimonious trees<BR>
19	for nucleic acid sequence parsimony criteria</H1>
20	</DIV>
21	<P>
22	© Copyright 1986-2002 by The University of
23	Washington. Written by Joseph Felsenstein. Permission is granted to copy
24	this document provided that no fee is charged for it and that this copyright
25	notice is not removed.
26	<P>
27	DNAPENNY is a program that will find all of the most parsimonious trees
28	implied by your data when the nucleic acid sequence parsimony criterion is
29	employed. It does so not by examining all possible trees,
30	but by using the more sophisticated "branch and bound" algorithm, a
31	standard computer science search strategy first applied to
32	phylogenetic inference by Hendy and Penny (1982). (J. S. Farris
33	[personal communication, 1975] had also suggested that this strategy,
34	which is well-known in computer science, might
35	be applied to phylogenies, but he did not publish this suggestion).
36	<P>
37	There is, however, a price to be paid for the certainty that one has
38	found all members of the set of most parsimonious trees. The problem of
39	finding these has been shown (Graham and Foulds, 1982; Day, 1983) to be
40	NP-complete, which is equivalent to saying that there is no
41	fast algorithm that is guaranteed to solve the problem in all cases
42	(for a discussion of NP-completeness, see the Scientific American
43	article by Lewis and Papadimitriou, 1978). The result is that this program,
44	despite its algorithmic sophistication, is VERY SLOW.
45	<P>
46	The program should be slower than the other tree-building programs
47	in the package, but useable up to about ten species. Above this it will
48	bog down rapidly, but exactly when depends on the data and on how much
49	computer time you have (it may be more effective in the hands of someone
50	who can let a microcomputer grind all night than for someone who
51	has the "benefit" of paying for time on the campus mainframe computer). IT
52	IS VERY IMPORTANT FOR YOU TO GET A FEEL FOR HOW LONG THE PROGRAM
53	WILL TAKE ON YOUR DATA. This can be done by running it on subsets
54	of the species, increasing the number of species in the run until you
55	either are able to treat the full data set or know that the program
56	will take unacceptably long on it. (Making a plot of the logarithm of
57	run time against species number may help to project run times).
58	<P>
59	<H2>The Algorithm</H2>
60	<P>
61	The search strategy used by DNAPENNY starts by making a tree consisting of the
62	first two species (the first three if the tree is to be unrooted). Then
63	it tries to add the next species in all possible places (there are three
64	of these). For each of the resulting trees it evaluates the number of
65	base substitutions. It adds the next species to each of these, again in all
66	possible spaces. If this process would continue it would simply
67	generate all possible trees, of which there are a very large number even
68	when the number of species is moderate (34,459,425 with 10 species). Actually
69	it does not do this, because the trees are generated in a
70	particular order and some of them are never generated.
71	<P>
72	This is because the order in which trees are generated is not quite as implied
73	above, but is a "depth-first search". This means that first one adds the third
74	species in the first possible place, then the fourth species in its first
75	possible place, then the fifth and so on until the first possible tree has
76	been produced. For each tree the number of steps is evaluated. Then one
77	"backtracks" by trying the alternative placements of the last species. When
78	these are exhausted one tries the next placement of the next-to-last
79	species. The order of placement in a depth-first search is like this for a
80	four-species case (parentheses enclose monophyletic groups):
81	<P>
82	Make tree of first two species:     (A,B)<BR>
83	Add C in first place:     ((A,B),C)<BR>
84	Add D in first place:     (((A,D),B),C)<BR>
85	Add D in second place:     ((A,(B,D)),C)<BR>
86	Add D in third place:     (((A,B),D),C)<BR>
87	Add D in fourth place:     ((A,B),(C,D))<BR>
88	Add D in fifth place:     (((A,B),C),D)<BR>
89	Add C in second place:     ((A,C),B)<BR>
90	Add D in first place:     (((A,D),C),B)<BR>
91	Add D in second place:     ((A,(C,D)),B)<BR>
92	Add D in third place:     (((A,C),D),B)<BR>
93	Add D in fourth place:     ((A,C),(B,D))<BR>
94	Add D in fifth place:     (((A,C),B),D)<BR>
95	Add C in third place:     (A,(B,C))<BR>
96	Add D in first place:     ((A,D),(B,C))<BR>
97	Add D in second place:     (A,((B,D),C))<BR>
98	Add D in third place:     (A,(B,(C,D)))<BR>
99	Add D in fourth place:     (A,((B,C),D))<BR>
100	Add D in fifth place:     ((A,(B,C)),D)<BR>
101	<P>
102	Among these fifteen trees you will find all of the four-species
103	rooted trees, each exactly once (the parentheses each enclose
104	a monophyletic group). As displayed above, the backtracking
105	depth-first search algorithm is just another way of producing all
106	possible trees one at a time. The branch and bound algorithm
107	consists of this with one change. As each tree is constructed,
108	including the partial trees such as (A,(B,C)), its number of steps
109	is evaluated. In addition a prediction is made as to how many
110	steps will be added, at a minimum, as further species are added.
111	<P>
112	This is done by counting how many sites which are invariant in the data up the
113	most recent species added will ultimately show variation when further species
114	are added. Thus if 20 sites vary among species A, B, and C and their root,
115	and if tree ((A,C),B) requires 24 steps, then if there are 8 more sites which
116	will be seen to vary when species D is added, we can immediately say that no
117	matter how we add D, the resulting tree can have no less than 24 + 8 = 32
118	steps. The point of all this is that if a previously-found tree such as
119	((A,B),(C,D)) required only 30 steps, then we know that there is no point in
120	even trying to add D to ((A,C),B). We have computed the bound that enables us
121	to cut off a whole line of inquiry (in this case five trees) and avoid going
122	down that particular branch any farther.
123	<P>
124	The branch-and-bound algorithm thus allows us to find all most parsimonious
125	trees without generating all possible trees. How much of a saving this
126	is depends strongly on the data. For very clean (nearly "Hennigian")
127	data, it saves much time, but on very messy data it will still take
128	a very long time.
129	<P>
130	The algorithm in the program differs from the one outlined here
131	in some essential details: it investigates possibilities in the
132	order of their apparent promise. This applies to the order of addition
133	of species, and to the places where they are added to the tree. After
134	the first two-species tree is constructed, the program tries adding
135	each of the remaining species in turn, each in the best possible place it
136	can find. Whichever of those species adds (at a minimum) the most
137	additional steps is taken to be the one to be added next to the tree. When
138	it is added, it is added in turn to places which cause the fewest
139	additional steps to be added. This sounds a bit complex, but it is done
140	with the intention of eliminating regions of the search of all possible
141	trees as soon as possible, and lowering the bound on tree length as quickly
142	as possible. This process of evaluating which species to add in which
143	order goes on the first time the search makes a tree; thereafter it uses that
144	order.
145	<P>
146	The program keeps a list of all the most parsimonious
147	trees found so far. Whenever it finds one that has fewer losses than
148	these, it clears out the list and
149	restarts it with that tree. In the process the bound tightens and
150	fewer possibilities need be investigated. At the end the list contains
151	all the shortest trees. These are then printed out. It should be
152	mentioned that the program CLIQUE for finding all largest cliques
153	also works by branch-and-bound. Both problems are NP-complete but for
154	some reason CLIQUE runs far faster. Although their worst-case behavior
155	is bad for both programs, those worst cases occur far more frequently
156	in parsimony problems than in compatibility problems.
157	<P>
158	<H2>Controlling Run Times</H2>
159	<P>
160	Among the quantities available to be set from the menu of
161	DNAPENNY, two (howoften and howmany) are of particular
162	importance. As DNAPENNY goes along it will keep count of how many
163	trees it has examined. Suppose that howoften is 100 and howmany is 1000,
164	the default settings. Every time 100 trees have been examined, DNAPENNY
165	will print out a line saying how many multiples of 100 trees have now been
166	examined, how many steps the most parsimonious tree found so far has,
167	how many trees of with that number of steps have been found, and a very
168	rough estimate of what fraction of all trees have been looked at so far.
169	<P>
170	When the number of these multiples printed out reaches the number howmany
171	(say 1000), the whole algorithm aborts and prints out that it has not
172	found all most parsimonious trees, but prints out what is has got so far
173	anyway. These trees need not be any of the most parsimonious trees: they are
174	simply the most parsimonious ones found so far. By setting the product
175	(howoften times howmany) large you can make
176	the algorithm less likely to abort, but then you risk getting bogged
177	down in a gigantic computation. You should adjust these constants so that
178	the program cannot go beyond examining the number of trees you are reasonably
179	willing to pay for (or wait for). In their initial setting the program will
180	abort after looking at 100,000 trees. Obviously you may want to adjust
181	howoften in order to get more or fewer lines of intermediate notice of how
182	many trees have been looked at so far. Of course, in small cases you may
183	never even reach the first multiple of howoften, and nothing will be printed
184	out except some headings and then the final trees.
185	<P>
186	The indication of the approximate percentage of trees searched so far will
187	be helpful in judging how much farther you would have to go to get the full
188	search. Actually, since that fraction is the fraction of the set of all
189	possible trees searched or ruled out so far, and since the search becomes
190	progressively more efficient, the approximate fraction printed out will
191	usually be an underestimate of how far along the program is, sometimes a
192	serious underestimate.
193	<P>
194	A constant
195	at the beginning of the program that affects the result is
196	"maxtrees",
197	which controls the
198	maximum number of trees that can be stored. Thus if maxtrees is 25,
199	and 32 most parsimonious trees are found, only the first 25 of these are
200	stored and printed out. If maxtrees is increased, the program does not
201	run any slower but requires a little
202	more intermediate storage space. I recommend
203	that maxtrees be kept as large as you can, provided you are willing to
204	look at an output with that many trees on it! Initially, maxtrees is set
205	to 100 in the distribution copy.
206	<P>
207	<H2>Method and Options</H2>
208	<P>
209	The counting of the length of trees is done by an algorithm nearly
210	identical to the corresponding algorithms in DNAPARS, and thus the remainder
211	of this document will be nearly identical to the DNAPARS document.
212	<P>
213	This program carries out unrooted parsimony (analogous to Wagner
214	trees) (Eck and Dayhoff, 1966; Kluge and Farris, 1969) on DNA
215	sequences. The method of Fitch (1971) is used to count the number of
216	changes of base needed on a given tree. The assumptions of this
217	method are exactly analogous to those of DNAPARS:
218	<OL>
219	<LI>Each site evolves independently.
220	<LI>Different lineages evolve independently.
221	<LI>The probability of a base substitution at a given site is
222	small over the lengths of time involved in
223	a branch of the phylogeny.
224	<LI>The expected amounts of change in different branches of the phylogeny
225	do not vary by so much that two changes in a high-rate branch
226	are more probable than one change in a low-rate branch.
227	<LI>The expected amounts of change do not vary enough among sites that two
228	changes in one site are more probable than one change in another.
229	</OL>
230	<P>
231	Change from an occupied site to a deletion is counted as one
232	change. Reversion from a deletion to an occupied site is allowed and is also
233	counted as one change.
234	<P>
235	That these are the assumptions of parsimony methods has been documented
236	in a series of papers of mine: (1973a, 1978b, 1979, 1981b,
237	1983b, 1988b). For an
238	opposing view arguing that the parsimony methods make no substantive
239	assumptions such as these, see the papers by Farris (1983) and Sober (1983a,
240	1983b), but also read the exchange between Felsenstein and Sober (1986).
241	<P>
242	Change from an occupied site to a deletion is counted as one
243	change. Reversion from a deletion to an occupied site is allowed and is also
244	counted as one change. Note that this in effect assumes that a deletion
245	N bases long is N separate events.
246	<P>
247	The input data is standard. The first line of the input file contains the
248	number of species and the number of sites. If the Weights option is being
249	used, there must also be a W in this first line to signal its presence.
250	There are only two options requiring information to be present in the input
251	file, W (Weights) and U (User tree). All options other than W (including U) are
252	invoked using the menu.
253	<P>
254	Next come the species data. Each
255	sequence starts on a new line, has a ten-character species name
256	that must be blank-filled to be of that length, followed immediately
257	by the species data in the one-letter code. The sequences must either
258	be in the "interleaved" or "sequential" formats
259	described in the Molecular Sequence Programs document. The I option
260	selects between them. The sequences can have internal
261	blanks in the sequence but there must be no extra blanks at the end of the
262	terminated line. Note that a blank is not a valid symbol for a deletion.
263	<P>
264	The options are selected using an interactive menu. The menu looks like this:
265	<P>
266	<TABLE><TR><TD BGCOLOR=white>
267	<PRE>
268
269	Penny algorithm for DNA, version 3.6a3
270	branch-and-bound to find all most parsimonious trees
271
272	Settings for this run:
273	H How many groups of 100 trees: 1000
274	F How often to report, in trees: 100
275	S Branch and bound is simple? Yes
276	O Outgroup root? No, use as outgroup species 1
277	T Use Threshold parsimony? No, use ordinary parsimony
278	W Sites weighted? No
279	M Analyze multiple data sets? No
280	I Input sequences interleaved? Yes
281	0 Terminal type (IBM PC, ANSI, none)? (none)
282	1 Print out the data at start of run No
283	2 Print indications of progress of run Yes
284	3 Print out tree Yes
285	4 Print out steps in each site No
286	5 Print sequences at all nodes of tree No
287	6 Write out trees onto tree file? Yes
288
289	Are these settings correct? (type Y or the letter for one to change)
290
291	</PRE>
292	</TD></TR></TABLE>
293	<P>
294	The user either types "Y" (followed, of course, by a carriage-return)
295	if the settings shown are to be accepted, or the letter or digit corresponding
296	to an option that is to be changed.
297	<P>
298	The options O, T, W, M, and 0 are the usual ones. They are described in the
299	main documentation file of this package. Option I is the same as in
300	other molecular sequence programs and is described in the documentation file
301	for the sequence programs.
302	<P>
303	The T (threshold) option allows a continuum of methods
304	between parsimony and compatibility. Thresholds less than or equal to 1.0 do
305	not have any meaning and should
306	not be used: they will result in a tree dependent only on the input
307	order of species and not at all on the data!
308	<P>
309	The W (Weights) option allows only weights of 0 or 1.
310	<P>
311	The M (Multiple data sets) option for this program does not allow multiple
312	sets of weights. We hope to change this soon.
313	<P>
314	The options H, F, and S are not found in the other molecular sequence programs.
315	H (How many) allows the user to set the quantity howmany, which we have
316	already seen controls number of times that the program
317	will report on its progress. F allows the user to set the quantity howoften,
318	which sets how often it will report -- after scanning how many trees.
319	<P>
320	The S (Simple) option alters a step in DNAPENNY which reconsiders the
321	order in which species are added to the tree. Normally the decision as to
322	what species to add to the tree next is made as the first tree is being
323	constructed; that ordering of species is not altered subsequently. The S
324	option causes it to be continually reconsidered. This will probably
325	result in a substantial increase in run time, but on some data sets of
326	intermediate messiness it may help. It is included in case it might prove
327	of use on some data sets.
328	<P>
329	Output is standard: if option 1 is toggled on, the data is printed out,
330	with the convention that "." means "the same as in the first species".
331	Then comes a list of equally parsimonious trees, and (if option 2 is
332	toggled on) a table of the
333	number of changes of state required in each character. If option 5 is toggled
334	on, a table is printed
335	out after each tree, showing for each branch whether there are known to be
336	changes in the branch, and what the states are inferred to have been at the
337	top end of the branch. If the inferred state is a "?" or one of the IUB
338	ambiguity symbols, there will be multiple
339	equally-parsimonious assignments of states; the user must work these out for
340	themselves by hand. A "?" in the reconstructed states means that in
341	addition to one or more bases, a deletion may or may not be present. If
342	option 6 is left in its default state the trees
343	found will be written to a tree file, so that they are available to be used
344	in other programs.
345	<P>
346	<HR><H3>TEST DATA SET</H3>
347	<P>
348	<TABLE><TR><TD BGCOLOR=white>
349	<PRE>
350	8 6
351	Alpha1 AAGAAG
352	Alpha2 AAGAAG
353	Beta1 AAGGGG
354	Beta2 AAGGGG
355	Gamma1 AGGAAG
356	Gamma2 AGGAAG
357	Delta GGAGGA
358	Epsilon GGAAAG
359	</PRE>
360	</TD></TR></TABLE>
361	<P>
362	<HR>
363	<H3>CONTENTS OF OUTPUT FILE (if all numerical options are on)</H3>
364	<P>
365	<TABLE><TR><TD BGCOLOR=white>
366	<PRE>
367
368	Penny algorithm for DNA, version 3.6a3
369	branch-and-bound to find all most parsimonious trees
370
371
372	requires a total of 8.000
373
374	9 trees in all found
375
376
377
378
379	+--------------------Alpha1
380	!
381	! +--Delta
382	! +--3
383	! +--7 +--Epsilon
384	1 ! !
385	! +-----6 +-----Gamma2
386	! ! !
387	! +--4 +--------Gamma1
388	! ! !
389	! ! ! +--Beta2
390	+--2 +-----------5
391	! +--Beta1
392	!
393	+-----------------Alpha2
394
395	remember: this is an unrooted tree!
396
397
398	steps in each site:
399	0 1 2 3 4 5 6 7 8 9
400	*-----------------------------------------
401	0\| 1 1 1 2 2 1
402
403	From To Any Steps? State at upper node
404
405	1 AAGAAG
406	1 Alpha1 no AAGAAG
407	1 2 no AAGAAG
408	2 4 no AAGAAG
409	4 6 yes AGGAAG
410	6 7 no AGGAAG
411	7 3 yes GGAAAG
412	3 Delta yes GGAGGA
413	3 Epsilon no GGAAAG
414	7 Gamma2 no AGGAAG
415	6 Gamma1 no AGGAAG
416	4 5 yes AAGGGG
417	5 Beta2 no AAGGGG
418	5 Beta1 no AAGGGG
419	2 Alpha2 no AAGAAG
420
421
422
423
424
425	+--------------------Alpha1
426	!
427	! +--Delta
428	! +-----3
429	! ! +--Epsilon
430	1 +-----6
431	! ! ! +--Gamma2
432	! ! +-----7
433	! +--4 +--Gamma1
434	! ! !
435	! ! ! +--Beta2
436	+--2 +-----------5
437	! +--Beta1
438	!
439	+-----------------Alpha2
440
441	remember: this is an unrooted tree!
442
443
444	steps in each site:
445	0 1 2 3 4 5 6 7 8 9
446	*-----------------------------------------
447	0\| 1 1 1 2 2 1
448
449	From To Any Steps? State at upper node
450
451	1 AAGAAG
452	1 Alpha1 no AAGAAG
453	1 2 no AAGAAG
454	2 4 no AAGAAG
455	4 6 yes AGGAAG
456	6 3 yes GGAAAG
457	3 Delta yes GGAGGA
458	3 Epsilon no GGAAAG
459	6 7 no AGGAAG
460	7 Gamma2 no AGGAAG
461	7 Gamma1 no AGGAAG
462	4 5 yes AAGGGG
463	5 Beta2 no AAGGGG
464	5 Beta1 no AAGGGG
465	2 Alpha2 no AAGAAG
466
467
468
469
470
471	+--------------------Alpha1
472	!
473	! +--Delta
474	! +--3
475	! +--6 +--Epsilon
476	1 ! !
477	! +-----7 +-----Gamma1
478	! ! !
479	! +--4 +--------Gamma2
480	! ! !
481	! ! ! +--Beta2
482	+--2 +-----------5
483	! +--Beta1
484	!
485	+-----------------Alpha2
486
487	remember: this is an unrooted tree!
488
489
490	steps in each site:
491	0 1 2 3 4 5 6 7 8 9
492	*-----------------------------------------
493	0\| 1 1 1 2 2 1
494
495	From To Any Steps? State at upper node
496
497	1 AAGAAG
498	1 Alpha1 no AAGAAG
499	1 2 no AAGAAG
500	2 4 no AAGAAG
501	4 7 yes AGGAAG
502	7 6 no AGGAAG
503	6 3 yes GGAAAG
504	3 Delta yes GGAGGA
505	3 Epsilon no GGAAAG
506	6 Gamma1 no AGGAAG
507	7 Gamma2 no AGGAAG
508	4 5 yes AAGGGG
509	5 Beta2 no AAGGGG
510	5 Beta1 no AAGGGG
511	2 Alpha2 no AAGAAG
512
513
514
515
516
517	+--------------------Alpha1
518	!
519	! +--Delta
520	! +--3
521	1 +--7 +--Epsilon
522	! ! !
523	! +--------6 +-----Gamma2
524	! ! !
525	! ! +--------Gamma1
526	+--2
527	! +--Beta2
528	! +--5
529	+-----------4 +--Beta1
530	!
531	+-----Alpha2
532
533	remember: this is an unrooted tree!
534
535
536	steps in each site:
537	0 1 2 3 4 5 6 7 8 9
538	*-----------------------------------------
539	0\| 1 1 1 2 2 1
540
541	From To Any Steps? State at upper node
542
543	1 AAGAAG
544	1 Alpha1 no AAGAAG
545	1 2 no AAGAAG
546	2 6 yes AGGAAG
547	6 7 no AGGAAG
548	7 3 yes GGAAAG
549	3 Delta yes GGAGGA
550	3 Epsilon no GGAAAG
551	7 Gamma2 no AGGAAG
552	6 Gamma1 no AGGAAG
553	2 4 no AAGAAG
554	4 5 yes AAGGGG
555	5 Beta2 no AAGGGG
556	5 Beta1 no AAGGGG
557	4 Alpha2 no AAGAAG
558
559
560
561
562
563	+--------------------Alpha1
564	!
565	! +--Delta
566	! +-----3
567	1 ! +--Epsilon
568	! +--------6
569	! ! ! +--Gamma2
570	! ! +-----7
571	+--2 +--Gamma1
572	!
573	! +--Beta2
574	! +--5
575	+-----------4 +--Beta1
576	!
577	+-----Alpha2
578
579	remember: this is an unrooted tree!
580
581
582	steps in each site:
583	0 1 2 3 4 5 6 7 8 9
584	*-----------------------------------------
585	0\| 1 1 1 2 2 1
586
587	From To Any Steps? State at upper node
588
589	1 AAGAAG
590	1 Alpha1 no AAGAAG
591	1 2 no AAGAAG
592	2 6 yes AGGAAG
593	6 3 yes GGAAAG
594	3 Delta yes GGAGGA
595	3 Epsilon no GGAAAG
596	6 7 no AGGAAG
597	7 Gamma2 no AGGAAG
598	7 Gamma1 no AGGAAG
599	2 4 no AAGAAG
600	4 5 yes AAGGGG
601	5 Beta2 no AAGGGG
602	5 Beta1 no AAGGGG
603	4 Alpha2 no AAGAAG
604
605
606
607
608
609	+--------------------Alpha1
610	!
611	! +--Delta
612	! +--3
613	1 +--6 +--Epsilon
614	! ! !
615	! +--------7 +-----Gamma1
616	! ! !
617	! ! +--------Gamma2
618	+--2
619	! +--Beta2
620	! +--5
621	+-----------4 +--Beta1
622	!
623	+-----Alpha2
624
625	remember: this is an unrooted tree!
626
627
628	steps in each site:
629	0 1 2 3 4 5 6 7 8 9
630	*-----------------------------------------
631	0\| 1 1 1 2 2 1
632
633	From To Any Steps? State at upper node
634
635	1 AAGAAG
636	1 Alpha1 no AAGAAG
637	1 2 no AAGAAG
638	2 7 yes AGGAAG
639	7 6 no AGGAAG
640	6 3 yes GGAAAG
641	3 Delta yes GGAGGA
642	3 Epsilon no GGAAAG
643	6 Gamma1 no AGGAAG
644	7 Gamma2 no AGGAAG
645	2 4 no AAGAAG
646	4 5 yes AAGGGG
647	5 Beta2 no AAGGGG
648	5 Beta1 no AAGGGG
649	4 Alpha2 no AAGAAG
650
651
652
653
654
655	+--------------------Alpha1
656	!
657	! +--Delta
658	! +--3
659	! +--7 +--Epsilon
660	1 ! !
661	! +--6 +-----Gamma2
662	! ! !
663	! +-----2 +--------Gamma1
664	! ! !
665	+--4 +-----------Alpha2
666	!
667	! +--Beta2
668	+--------------5
669	+--Beta1
670
671	remember: this is an unrooted tree!
672
673
674	steps in each site:
675	0 1 2 3 4 5 6 7 8 9
676	*-----------------------------------------
677	0\| 1 1 1 2 2 1
678
679	From To Any Steps? State at upper node
680
681	1 AAGAAG
682	1 Alpha1 no AAGAAG
683	1 4 no AAGAAG
684	4 2 no AAGAAG
685	2 6 yes AGGAAG
686	6 7 no AGGAAG
687	7 3 yes GGAAAG
688	3 Delta yes GGAGGA
689	3 Epsilon no GGAAAG
690	7 Gamma2 no AGGAAG
691	6 Gamma1 no AGGAAG
692	2 Alpha2 no AAGAAG
693	4 5 yes AAGGGG
694	5 Beta2 no AAGGGG
695	5 Beta1 no AAGGGG
696
697
698
699
700
701	+--------------------Alpha1
702	!
703	! +--Delta
704	! +-----3
705	! ! +--Epsilon
706	1 +--6
707	! ! ! +--Gamma2
708	! +-----2 +-----7
709	! ! ! +--Gamma1
710	! ! !
711	+--4 +-----------Alpha2
712	!
713	! +--Beta2
714	+--------------5
715	+--Beta1
716
717	remember: this is an unrooted tree!
718
719
720	steps in each site:
721	0 1 2 3 4 5 6 7 8 9
722	*-----------------------------------------
723	0\| 1 1 1 2 2 1
724
725	From To Any Steps? State at upper node
726
727	1 AAGAAG
728	1 Alpha1 no AAGAAG
729	1 4 no AAGAAG
730	4 2 no AAGAAG
731	2 6 yes AGGAAG
732	6 3 yes GGAAAG
733	3 Delta yes GGAGGA
734	3 Epsilon no GGAAAG
735	6 7 no AGGAAG
736	7 Gamma2 no AGGAAG
737	7 Gamma1 no AGGAAG
738	2 Alpha2 no AAGAAG
739	4 5 yes AAGGGG
740	5 Beta2 no AAGGGG
741	5 Beta1 no AAGGGG
742
743
744
745
746
747	+--------------------Alpha1
748	!
749	! +--Delta
750	! +--3
751	! +--6 +--Epsilon
752	1 ! !
753	! +--7 +-----Gamma1
754	! ! !
755	! +-----2 +--------Gamma2
756	! ! !
757	+--4 +-----------Alpha2
758	!
759	! +--Beta2
760	+--------------5
761	+--Beta1
762
763	remember: this is an unrooted tree!
764
765
766	steps in each site:
767	0 1 2 3 4 5 6 7 8 9
768	*-----------------------------------------
769	0\| 1 1 1 2 2 1
770
771	From To Any Steps? State at upper node
772
773	1 AAGAAG
774	1 Alpha1 no AAGAAG
775	1 4 no AAGAAG
776	4 2 no AAGAAG
777	2 7 yes AGGAAG
778	7 6 no AGGAAG
779	6 3 yes GGAAAG
780	3 Delta yes GGAGGA
781	3 Epsilon no GGAAAG
782	6 Gamma1 no AGGAAG
783	7 Gamma2 no AGGAAG
784	2 Alpha2 no AAGAAG
785	4 5 yes AAGGGG
786	5 Beta2 no AAGGGG
787	5 Beta1 no AAGGGG
788
789
790	</PRE>
791	</TD></TR></TABLE>
792	</BODY>
793	</HTML>

Note: See TracBrowser for help on using the repository browser.

Context Navigation

source: trunk/GDE/PHYLIP/doc/dnapenny.html

Download in other formats: