src/jalview/analysis/NJTree.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 Neighbour
  30  * Joining tree
  31  */
  32 public class NJTree extends TreeBuilder
  33 {
  34   /**
  35    * Constructor given a viewport, tree type and score model
  36    *
  37    * @param av
  38    *          the current alignment viewport
  39    * @param sm
  40    *          a distance or similarity score model to use to compute the tree
  41    * @param scoreParameters
  42    */
  43   public NJTree(AlignmentViewport av, ScoreModelI sm,
  44           SimilarityParamsI scoreParameters)
  45   {
  46     super(av, sm, scoreParameters);
  47   }
  48
  49   /**
  50    * {@inheritDoc}
  51    */
  52   @Override
  53   protected double findMinDistance()
  54   {
  55     double min = Double.MAX_VALUE;
  56
  57     for (int i = 0; i < (noseqs - 1); i++)
  58     {
  59       for (int j = i + 1; j < noseqs; j++)
  60       {
  61         if (!done.get(i) && !done.get(j))
  62         {
  63           double tmp = distances.getValue(i, j)
  64                   - (findr(i, j) + findr(j, i));
  65
  66           if (tmp < min)
  67           {
  68             mini = i;
  69             minj = j;
  70
  71             min = tmp;
  72           }
  73         }
  74       }
  75     }
  76
  77     return min;
  78   }
  79
  80   /**
  81    * {@inheritDoc}
  82    */
  83   @Override
  84   protected void findNewDistances(SequenceNode nodei, SequenceNode nodej,
  85           double dist)
  86   {
  87     nodei.dist = ((dist + ri) - rj) / 2;
  88     nodej.dist = (dist - nodei.dist);
  89
  90     if (nodei.dist < 0)
  91     {
  92       nodei.dist = 0;
  93     }
  94
  95     if (nodej.dist < 0)
  96     {
  97       nodej.dist = 0;
  98     }
  99   }
 100
 101   /**
 102    * Calculates and saves the distance between the combination of cluster(i) and
 103    * cluster(j) and all other clusters. The new distance to cluster k is
 104    * calculated as the average of the distances from i to k and from j to k,
 105    * less half the distance from i to j.
 106    *
 107    * @param i
 108    * @param j
 109    */
 110   @Override
 111   protected
 112   void findClusterDistance(int i, int j)
 113   {
 114     // New distances from cluster i to others
 115     double[] newdist = new double[noseqs];
 116
 117     double ijDistance = distances.getValue(i, j);
 118     for (int l = 0; l < noseqs; l++)
 119     {
 120       if ((l != i) && (l != j))
 121       {
 122         newdist[l] = (distances.getValue(i, l) + distances.getValue(j, l) - ijDistance) / 2;
 123       }
 124       else
 125       {
 126         newdist[l] = 0;
 127       }
 128     }
 129
 130     for (int ii = 0; ii < noseqs; ii++)
 131     {
 132       distances.setValue(i, ii, newdist[ii]);
 133       distances.setValue(ii, i, newdist[ii]);
 134     }
 135   }
 136 }