src/jalview/analysis/AverageDistanceTree.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
   3  * Copyright (C) $$Year-Rel$$ The Jalview Authors
   4  *
   5  * This file is part of Jalview.
   6  *
   7  * Jalview is free software: you can redistribute it and/or
   8  * modify it under the terms of the GNU General Public License
   9  * as published by the Free Software Foundation, either version 3
  10  * of the License, or (at your option) any later version.
  11  *
  12  * Jalview is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty
  14  * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
  15  * PURPOSE.  See the GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with Jalview.  If not, see <http://www.gnu.org/licenses/>.
  19  * The Jalview Authors are detailed in the 'AUTHORS' file.
  20  */
  21 package jalview.analysis;
  22
  23 import jalview.api.analysis.ScoreModelI;
  24 import jalview.api.analysis.SimilarityParamsI;
  25 import jalview.datamodel.SequenceNode;
  26 import jalview.viewmodel.AlignmentViewport;
  27
  28 /**
  29  * This class implements distance calculations used in constructing a Average
  30  * Distance tree (also known as UPGMA)
  31  */
  32 public class AverageDistanceTree extends TreeBuilder
  33 {
  34   /**
  35    * Constructor
  36    *
  37    * @param av
  38    * @param sm
  39    * @param scoreParameters
  40    */
  41   public AverageDistanceTree(AlignmentViewport av, ScoreModelI sm,
  42           SimilarityParamsI scoreParameters)
  43   {
  44     super(av, sm, scoreParameters);
  45   }
  46
  47   /**
  48    * Calculates and saves the distance between the combination of cluster(i) and
  49    * cluster(j) and all other clusters. An average of the distances from
  50    * cluster(i) and cluster(j) is calculated, weighted by the sizes of each
  51    * cluster.
  52    *
  53    * @param i
  54    * @param j
  55    */
  56   @Override
  57   protected void findClusterDistance(int i, int j)
  58   {
  59     int noi = clusters.elementAt(i).cardinality();
  60     int noj = clusters.elementAt(j).cardinality();
  61
  62     // New distances from cluster i to others
  63     double[] newdist = new double[noseqs];
  64
  65     for (int l = 0; l < noseqs; l++)
  66     {
  67       if ((l != i) && (l != j))
  68       {
  69         newdist[l] = ((distances.getValue(i, l) * noi)
  70                 + (distances.getValue(j, l) * noj)) / (noi + noj);
  71       }
  72       else
  73       {
  74         newdist[l] = 0;
  75       }
  76     }
  77
  78     for (int ii = 0; ii < noseqs; ii++)
  79     {
  80       distances.setValue(i, ii, newdist[ii]);
  81       distances.setValue(ii, i, newdist[ii]);
  82     }
  83   }
  84
  85   /**
  86    * {@inheritDoc}
  87    */
  88   @Override
  89   protected double findMinDistance()
  90   {
  91     double min = Double.MAX_VALUE;
  92
  93     for (int i = 0; i < (noseqs - 1); i++)
  94     {
  95       for (int j = i + 1; j < noseqs; j++)
  96       {
  97         if (!done.get(i) && !done.get(j))
  98         {
  99           if (distances.getValue(i, j) < min)
 100           {
 101             mini = i;
 102             minj = j;
 103
 104             min = distances.getValue(i, j);
 105           }
 106         }
 107       }
 108     }
 109     return min;
 110   }
 111
 112   /**
 113    * {@inheritDoc}
 114    */
 115   @Override
 116   protected void findNewDistances(SequenceNode nodei, SequenceNode nodej,
 117           double dist)
 118   {
 119     double ih = 0;
 120     double jh = 0;
 121
 122     SequenceNode sni = nodei;
 123     SequenceNode snj = nodej;
 124
 125     while (sni != null)
 126     {
 127       ih = ih + sni.dist;
 128       sni = (SequenceNode) sni.left();
 129     }
 130
 131     while (snj != null)
 132     {
 133       jh = jh + snj.dist;
 134       snj = (SequenceNode) snj.left();
 135     }
 136
 137     nodei.dist = ((dist / 2) - ih);
 138     nodej.dist = ((dist / 2) - jh);
 139   }
 140
 141 }