src/jalview/analysis/AverageDistanceTree.java

   1 package jalview.analysis;
   2
   3 import jalview.api.analysis.ScoreModelI;
   4 import jalview.api.analysis.SimilarityParamsI;
   5 import jalview.datamodel.SequenceNode;
   6 import jalview.viewmodel.AlignmentViewport;
   7
   8 /**
   9  * This class implements distance calculations used in constructing a Average
  10  * Distance tree (also known as UPGMA)
  11  */
  12 public class AverageDistanceTree extends TreeBuilder
  13 {
  14   /**
  15    * Constructor
  16    *
  17    * @param av
  18    * @param sm
  19    * @param scoreParameters
  20    */
  21   public AverageDistanceTree(AlignmentViewport av, ScoreModelI sm,
  22           SimilarityParamsI scoreParameters)
  23   {
  24     super(av, sm, scoreParameters);
  25   }
  26
  27   /**
  28    * Calculates and saves the distance between the combination of cluster(i) and
  29    * cluster(j) and all other clusters. An average of the distances from
  30    * cluster(i) and cluster(j) is calculated, weighted by the sizes of each
  31    * cluster.
  32    *
  33    * @param i
  34    * @param j
  35    */
  36   @Override
  37   protected void findClusterDistance(int i, int j)
  38   {
  39     int noi = clusters.elementAt(i).cardinality();
  40     int noj = clusters.elementAt(j).cardinality();
  41
  42     // New distances from cluster i to others
  43     double[] newdist = new double[noseqs];
  44
  45     for (int l = 0; l < noseqs; l++)
  46     {
  47       if ((l != i) && (l != j))
  48       {
  49         newdist[l] = ((distances.getValue(i, l) * noi) + (distances
  50                 .getValue(j, l) * noj)) / (noi + noj);
  51       }
  52       else
  53       {
  54         newdist[l] = 0;
  55       }
  56     }
  57
  58     for (int ii = 0; ii < noseqs; ii++)
  59     {
  60       distances.setValue(i, ii, newdist[ii]);
  61       distances.setValue(ii, i, newdist[ii]);
  62     }
  63   }
  64
  65   /**
  66    * {@inheritDoc}
  67    */
  68   @Override
  69   protected double findMinDistance()
  70   {
  71     double min = Double.MAX_VALUE;
  72
  73     for (int i = 0; i < (noseqs - 1); i++)
  74     {
  75       for (int j = i + 1; j < noseqs; j++)
  76       {
  77         if (!done.get(i) && !done.get(j))
  78         {
  79           if (distances.getValue(i, j) < min)
  80           {
  81             mini = i;
  82             minj = j;
  83
  84             min = distances.getValue(i, j);
  85           }
  86         }
  87       }
  88     }
  89     return min;
  90   }
  91
  92   /**
  93    * {@inheritDoc}
  94    */
  95   @Override
  96   protected void findNewDistances(SequenceNode nodei, SequenceNode nodej,
  97           double dist)
  98   {
  99     double ih = 0;
 100     double jh = 0;
 101
 102     SequenceNode sni = nodei;
 103     SequenceNode snj = nodej;
 104
 105     while (sni != null)
 106     {
 107       ih = ih + sni.dist;
 108       sni = (SequenceNode) sni.left();
 109     }
 110
 111     while (snj != null)
 112     {
 113       jh = jh + snj.dist;
 114       snj = (SequenceNode) snj.left();
 115     }
 116
 117     nodei.dist = ((dist / 2) - ih);
 118     nodej.dist = ((dist / 2) - jh);
 119   }
 120
 121 }