src/jalview/analysis/TreeEngine.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 java.util.BitSet;
  24 import java.util.Vector;
  25
  26 import jalview.datamodel.BinaryNode;
  27 import jalview.datamodel.SequenceNode;
  28 import jalview.math.MatrixI;
  29
  30 public abstract class TreeEngine
  31 {
  32
  33   protected Vector<BitSet> clusters;
  34
  35   protected BitSet done;
  36
  37   protected int noseqs;
  38
  39   protected int noClus;
  40
  41   protected MatrixI distances;
  42
  43   protected double ri;
  44
  45   protected double rj;
  46
  47   protected Vector<BinaryNode> node;
  48
  49   BinaryNode maxdist;
  50
  51   double maxDistValue;
  52
  53   protected int mini;
  54
  55   protected int minj;
  56
  57   protected BinaryNode top;
  58
  59   protected int ycount;
  60
  61   double maxheight;
  62
  63   /**
  64    * Calculates and returns r, whatever that is
  65    *
  66    * @param i
  67    * @param j
  68    *
  69    * @return
  70    */
  71   protected double findr(int i, int j)
  72   {
  73     double tmp = 1;
  74
  75     for (int k = 0; k < noseqs; k++)
  76     {
  77       if ((k != i) && (k != j) && (!done.get(k)))
  78       {
  79         tmp = tmp + distances.getValue(i, k);
  80       }
  81     }
  82
  83     if (noClus > 2)
  84     {
  85       tmp = tmp / (noClus - 2);
  86     }
  87
  88     return tmp;
  89   }
  90
  91   /**
  92    * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
  93    *
  94    * @param i
  95    * @param j
  96    */
  97   protected void joinClusters(final int i, final int j)
  98   {
  99     double dist = distances.getValue(i, j);
 100
 101     ri = findr(i, j);
 102     rj = findr(j, i);
 103
 104     findClusterDistance(i, j);
 105
 106     BinaryNode sn = new BinaryNode();
 107
 108     sn.setLeft((node.elementAt(i)));
 109     sn.setRight((node.elementAt(j)));
 110
 111     BinaryNode tmpi = (node.elementAt(i));
 112     BinaryNode tmpj = (node.elementAt(j));
 113
 114     findNewDistances(tmpi, tmpj, dist);
 115
 116     tmpi.setParent(sn);
 117     tmpj.setParent(sn);
 118
 119     node.setElementAt(sn, i);
 120
 121     /*
 122      * move the members of cluster(j) to cluster(i)
 123      * and mark cluster j as out of the game
 124      */
 125     clusters.get(i).or(clusters.get(j));
 126     clusters.get(j).clear();
 127     done.set(j);
 128   }
 129
 130   protected abstract void findNewDistances(BinaryNode nodei,
 131           BinaryNode nodej, double previousDistance);
 132
 133   /**
 134    * Calculates and saves the distance between the combination of cluster(i) and
 135    * cluster(j) and all other clusters. The form of the calculation depends on
 136    * the tree clustering method being used.
 137    *
 138    * @param i
 139    * @param j
 140    */
 141   protected abstract void findClusterDistance(int i, int j);
 142
 143   /**
 144    * Finds the node, at or below the given node, with the maximum distance, and
 145    * saves the node and the distance value
 146    *
 147    * @param nd
 148    */
 149   protected void findMaxDist(BinaryNode nd)
 150   {
 151     if (nd == null)
 152     {
 153       return;
 154     }
 155
 156     if ((nd.left() == null) && (nd.right() == null))
 157     {
 158       double dist = nd.dist;
 159
 160       if (dist > maxDistValue)
 161       {
 162         maxdist = nd;
 163         maxDistValue = dist;
 164       }
 165     }
 166     else
 167     {
 168       findMaxDist((BinaryNode) nd.left());
 169       findMaxDist((BinaryNode) nd.right());
 170     }
 171   }
 172
 173   /**
 174    * Form clusters by grouping sub-clusters, starting from one sequence per
 175    * cluster, and finishing when only two clusters remain
 176    */
 177   protected void cluster()
 178   {
 179     while (noClus > 2)
 180     {
 181       findMinDistance();
 182
 183       joinClusters(mini, minj);
 184
 185       noClus--;
 186     }
 187
 188     int rightChild = done.nextClearBit(0);
 189     int leftChild = done.nextClearBit(rightChild + 1);
 190
 191     joinClusters(leftChild, rightChild);
 192     top = (node.elementAt(leftChild));
 193
 194     reCount(top);
 195     findHeight(top);
 196     findMaxDist(top);
 197   }
 198
 199   /**
 200    * Returns the minimum distance between two clusters, and also sets the
 201    * indices of the clusters in fields mini and minj
 202    *
 203    * @return
 204    */
 205   protected abstract double findMinDistance();
 206
 207   /**
 208    * DOCUMENT ME!
 209    *
 210    * @param nd
 211    *          DOCUMENT ME!
 212    */
 213   protected void _reCount(BinaryNode nd)
 214   {
 215     // if (_lycount<_lylimit)
 216     // {
 217     // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
 218     // number of
 219     // nodes.");
 220     // }
 221     if (nd == null)
 222     {
 223       return;
 224     }
 225     // _lycount++;
 226
 227     if ((nd.left() != null) && (nd.right() != null))
 228     {
 229
 230       _reCount(nd.left());
 231       _reCount((BinaryNode) nd.right());
 232
 233       BinaryNode l = nd.left();
 234       BinaryNode r = nd.right();
 235
 236       nd.count = l.count + r.count;
 237       nd.ycount = (l.ycount + r.ycount) / 2;
 238     }
 239     else
 240     {
 241       nd.count = 1;
 242       nd.ycount = ycount++;
 243     }
 244     // _lycount--;
 245   }
 246
 247   /**
 248    * DOCUMENT ME!
 249    *
 250    * @param nd
 251    *          DOCUMENT ME!
 252    *
 253    * @return DOCUMENT ME!
 254    */
 255   double findHeight(BinaryNode nd)
 256   {
 257     if (nd == null)
 258     {
 259       return maxheight;
 260     }
 261
 262     if ((nd.left() == null) && (nd.right() == null))
 263     {
 264       nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 265
 266       if (nd.height > maxheight)
 267       {
 268         return nd.height;
 269       }
 270       else
 271       {
 272         return maxheight;
 273       }
 274     }
 275     else
 276     {
 277       if (nd.parent() != null)
 278       {
 279         nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
 280       }
 281       else
 282       {
 283         maxheight = 0;
 284         nd.height = (float) 0.0;
 285       }
 286
 287       maxheight = findHeight((BinaryNode) (nd.left()));
 288       maxheight = findHeight((BinaryNode) (nd.right()));
 289     }
 290
 291     return maxheight;
 292   }
 293
 294   /**
 295    * DOCUMENT ME!
 296    *
 297    * @param nd
 298    *          DOCUMENT ME!
 299    */
 300   void reCount(BinaryNode nd)
 301   {
 302     ycount = 0;
 303     // _lycount = 0;
 304     // _lylimit = this.node.size();
 305     _reCount(nd);
 306   }
 307
 308   /**
 309    * DOCUMENT ME!
 310    *
 311    * @return DOCUMENT ME!
 312    */
 313   public BinaryNode getTopNode()
 314   {
 315     return top;
 316   }
 317
 318 }