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><title>Tree Calculation</title></head>
  23 <body>
  24 <p><strong>Calculation of trees from alignments</strong></p>
  25 <p>Trees are calculated on either the complete alignment, or just the
  26 currently selected group of sequences, using the functions in the
  27 <strong>Calculate&#8594;Calculate tree</strong> submenu.
  28 Once calculated, trees are displayed in a new <a
  29 href="../calculations/treeviewer.html">tree viewing window</a>. There are
  30 four different calculations, using one of two distance measures and
  31 constructing the tree from one of two algorithms :
  32 </p>
  33 <p><strong>Distance Measures</strong></p>
  34 <p>Trees are calculated on the basis of a measure of similarity
  35 between each pair of sequences in the alignment :
  36         <ul>
  37                 <li><strong>PID</strong><br>The percentage identity between
  38                         the two sequences at each aligned position.
  39                         <ul>
  40                                 <li>PID = Number of equivalent aligned non-gap symbols * 100 /
  41                                         Smallest number of non-gap positions in either of both sequences<br>
  42                                 <em>This is essentially the 'number of identical bases (or
  43                                                 residues) per 100 base pairs (or residues)'.</em>
  44                                 </li>
  45                         </ul>
  46                 <li><strong>BLOSUM62, PAM250, DNA</strong><br>These options
  47                         use one of the available substitution matrices to compute a sum of
  48                         scores for the residue pairs at each aligned position. For details
  49                         about each model, see the <a href="scorematrices.html">list of
  50                                 built-in score matrices.</a></li>
  51     <li><strong>Sequence Feature Similarity</strong><br>Trees
  52       are constructed from a distance matrix formed from Jaccard
  53       distances between sequence features observed at each column of the
  54       alignment.
  55       <ul>
  56         <li>Similarity at column <em>i</em> = (Total number of
  57           features displayed - Sum of number of features in common at <em>i</em>)
  58           <br />Similarities are summed over all columns and divided by
  59           the number of columns. <br />Since the total number of
  60           feature types is constant over all columns of the alignment,
  61           we do not scale the matrix, so tree distances can be
  62           interpreted as the average number of features that differ over
  63           all sites in the aligned region.
  64         </li>
  65
  66       </ul> Distances are computed based on the currently displayed feature
  67       types. Sequences with similar distributions of features of the
  68       same type will be grouped together in trees computed with this
  69       metric. <em>This measure was introduced in Jalview 2.9</em></li>
  70   </ul>
  71         </p>
  72         <p><strong>Tree Construction Methods</strong></p>
  73 <p>Jalview currently supports two kinds of agglomerative clustering
  74 methods. These are not intended to substitute for rigorous
  75 phylogenetic tree construction, and may fail on very large alignments.
  76 <ul>
  77 <li><strong>UPGMA tree</strong><br>
  78   UPGMA stands for Unweighted Pair-Group Method using Arithmetic
  79   averages. Clusters are iteratively formed and extended by finding a
  80   non-member sequence with the lowest average dissimilarity over the
  81   cluster members.
  82 <p></p>
  83 </li>
  84 <li><strong>Neighbour Joining tree</strong><br>
  85   First described in 1987 by Saitou and Nei, this method applies a
  86   greedy algorithm to find the tree with the shortest branch
  87   lengths.<br>
  88   This method, as implemented in Jalview, is considerably more
  89   expensive than UPGMA.
  90 </li>
  91 </ul>
  92 </p>
  93 <p>A newly calculated tree will be displayed in a new <a
  94 href="../calculations/treeviewer.html">tree viewing window</a>. In
  95 addition, a new entry with the same tree viewer window name will be added in the Sort
  96 menu so that the alignment can be reordered to reflect the ordering of
  97 the leafs of the tree. If the tree was calculated on a selected region
  98 of the alignment, then the title of the tree view will reflect this.</p>
  99
 100 <p><strong>External Sources for Phylogenetic Trees</strong></p>
 101   <p>A number of programs exist for the reliable construction of
 102   phylogenetic trees, which can cope with large numbers of sequences,
 103   use better distance methods and can perform bootstrapping. Jalview
 104   can read <a
 105   href="http://evolution.genetics.washington.edu/phylip/newick_doc.html">Newick</a>
 106   format tree files using the 'Load Associated Tree' entry of the
 107   alignment's File menu. Sequences in the alignment will be
 108   automatically associated to nodes in the tree, by matching Sequence
 109   IDs to the tree's leaf names.
 110   </p>
 111
 112
 113 </body>
 114 </html>