JAL-1961 added link to GFF3 format as well as GFF2
[jalview.git] / help / html / calculations / tree.html
1 <html>
2 <!--
3  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
4  * Copyright (C) $$Year-Rel$$ The Jalview Authors
5  * 
6  * This file is part of Jalview.
7  * 
8  * Jalview is free software: you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License 
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *  
13  * Jalview is distributed in the hope that it will be useful, but 
14  * WITHOUT ANY WARRANTY; without even the implied warranty 
15  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR 
16  * PURPOSE.  See the GNU General Public License for more details.
17  * 
18  * You should have received a copy of the GNU General Public License
19  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
20  * The Jalview Authors are detailed in the 'AUTHORS' file.
21  -->
22 <head>
23 <title>Tree Calculation</title>
24 </head>
25 <body>
26   <p>
27     <strong>Calculation of trees from alignments</strong>
28   </p>
29   <p>
30     Trees are calculated on either the complete alignment, or just the
31     currently selected group of sequences, using the functions in the <strong>Calculate&#8594;Calculate
32       tree</strong> submenu. Once calculated, trees are displayed in a new <a
33       href="../calculations/treeviewer.html">tree viewing
34       window</a>. There are four different calculations, using one of two
35     distance measures and constructing the tree from one of two
36     algorithms :
37   </p>
38   <p>
39     <strong>Distance Measures</strong>
40   </p>
41   <p>Trees are calculated on the basis of a measure of similarity
42     between each pair of sequences in the alignment :
43   <ul>
44     <li><strong>PID</strong><br>The percentage identity
45       between the two sequences at each aligned position.
46       <ul>
47         <li>PID = Number of equivalent aligned non-gap symbols *
48           100 / Smallest number of non-gap positions in either of both
49           sequences<br> <em>This is essentially the 'number of
50             identical bases (or residues) per 100 base pairs (or
51             residues)'.</em>
52         </li>
53       </ul>
54     <li><strong>BLOSUM62, PAM250, DNA</strong><br />These options
55       use one of the available substitution matrices to compute a sum of
56       scores for the residue pairs at each aligned position.
57       <ul>
58         <li>For details about each model, see the <a
59           href="scorematrices.html">list of built-in score
60             matrices</a>.
61         </li>
62       </ul></li>
63     <li><strong>Sequence Feature Similarity</strong><br>Trees
64       are constructed from a distance matrix formed from Jaccard
65       distances between sequence features observed at each column of the
66       alignment.
67       <ul>
68         <li>Similarity at column <em>i</em> = (Total number of
69           features displayed - Sum of number of features in common at <em>i</em>)
70           <br />Similarities are summed over all columns and divided by
71           the number of columns. <br />Since the total number of
72           feature types is constant over all columns of the alignment,
73           we do not scale the matrix, so tree distances can be
74           interpreted as the average number of features that differ over
75           all sites in the aligned region.
76         </li>
77
78       </ul> Distances are computed based on the currently displayed feature
79       types. Sequences with similar distributions of features of the
80       same type will be grouped together in trees computed with this
81       metric. <em>This measure was introduced in Jalview 2.9</em></li>
82   </ul>
83   <p>
84     <strong>Tree Construction Methods</strong>
85   </p>
86   <p>Jalview currently supports two kinds of agglomerative
87     clustering methods. These are not intended to substitute for
88     rigorous phylogenetic tree construction, and may fail on very large
89     alignments.
90   <ul>
91     <li><strong>UPGMA tree</strong><br> UPGMA stands for
92       Unweighted Pair-Group Method using Arithmetic averages. Clusters
93       are iteratively formed and extended by finding a non-member
94       sequence with the lowest average dissimilarity over the cluster
95       members.
96       <p></p></li>
97     <li><strong>Neighbour Joining tree</strong><br> First
98       described in 1987 by Saitou and Nei, this method applies a greedy
99       algorithm to find the tree with the shortest branch lengths.<br>
100       This method, as implemented in Jalview, is considerably more
101       expensive than UPGMA.</li>
102   </ul>
103   <p>
104     A newly calculated tree will be displayed in a new <a
105       href="../calculations/treeviewer.html">tree viewing
106       window</a>. In addition, a new entry with the same tree viewer window
107     name will be added in the Sort menu so that the alignment can be
108     reordered to reflect the ordering of the leafs of the tree. If the
109     tree was calculated on a selected region of the alignment, then the
110     title of the tree view will reflect this.
111   </p>
112
113   <p>
114     <strong>External Sources for Phylogenetic Trees</strong>
115   </p>
116   <p>
117     A number of programs exist for the reliable construction of
118     phylogenetic trees, which can cope with large numbers of sequences,
119     use better distance methods and can perform bootstrapping. Jalview
120     can read <a
121       href="http://evolution.genetics.washington.edu/phylip/newick_doc.html">Newick</a>
122     format tree files using the 'Load Associated Tree' entry of the
123     alignment's File menu. Sequences in the alignment will be
124     automatically associated to nodes in the tree, by matching Sequence
125     IDs to the tree's leaf names.
126   </p>
127
128
129 </body>
130 </html>