src/jalview/analysis/AverageDistanceEngine.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.AlignmentAnnotation;
  27 import jalview.datamodel.BinaryNode;
  28 import jalview.datamodel.ContactListI;
  29 import jalview.datamodel.ContactMatrixI;
  30 import jalview.math.Matrix;
  31 import jalview.viewmodel.AlignmentViewport;
  32
  33 /**
  34  * This class implements distance calculations used in constructing a Average
  35  * Distance tree (also known as UPGMA)
  36  */
  37 public class AverageDistanceEngine extends TreeEngine
  38 {
  39   ContactMatrixI cm;
  40   AlignmentViewport av;
  41   AlignmentAnnotation aa;
  42   /**
  43    * compute cosine distance matrix for a given contact matrix and create a UPGMA tree
  44    * @param cm
  45    */
  46   public AverageDistanceEngine(AlignmentViewport av, AlignmentAnnotation aa, ContactMatrixI cm)
  47   {
  48     this.av =av;
  49     this.aa = aa;
  50     this.cm=cm;
  51     node = new Vector<BinaryNode>();
  52     clusters = new Vector<BitSet>();
  53     distances = new Matrix(new double[cm.getWidth()][cm.getWidth()]);
  54     noseqs=cm.getWidth();
  55     done  = new BitSet();
  56     for (int i=0;i<cm.getWidth();i++)
  57     {
  58       // init the tree engine node for this column
  59       BinaryNode cnode = new BinaryNode();
  60       cnode.setElement(Integer.valueOf(i));
  61       cnode.setName("c"+i);
  62       node.addElement(cnode);
  63       BitSet bs = new BitSet();
  64       bs.set(i);
  65       clusters.addElement(bs);
  66
  67       // compute distance matrix element
  68       ContactListI ith=cm.getContactList(i);
  69       for (int j=0;j<i;j++)
  70       {
  71         ContactListI jth = cm.getContactList(j);
  72         double prd=0;
  73         for (int indx=0;indx<cm.getHeight();indx++)
  74         {
  75           prd+=ith.getContactAt(indx)*jth.getContactAt(indx);
  76         }
  77         distances.setValue(i, j, prd);
  78         distances.setValue(j, i, prd);
  79       }
  80     }
  81
  82     noClus = clusters.size();
  83     cluster();
  84
  85   }
  86   /**
  87    * Calculates and saves the distance between the combination of cluster(i) and
  88    * cluster(j) and all other clusters. An average of the distances from
  89    * cluster(i) and cluster(j) is calculated, weighted by the sizes of each
  90    * cluster.
  91    *
  92    * @param i
  93    * @param j
  94    */
  95   @Override
  96   protected void findClusterDistance(int i, int j)
  97   {
  98     int noi = clusters.elementAt(i).cardinality();
  99     int noj = clusters.elementAt(j).cardinality();
 100
 101     // New distances from cluster i to others
 102     double[] newdist = new double[noseqs];
 103
 104     for (int l = 0; l < noseqs; l++)
 105     {
 106       if ((l != i) && (l != j))
 107       {
 108         newdist[l] = ((distances.getValue(i, l) * noi)
 109                 + (distances.getValue(j, l) * noj)) / (noi + noj);
 110       }
 111       else
 112       {
 113         newdist[l] = 0;
 114       }
 115     }
 116
 117     for (int ii = 0; ii < noseqs; ii++)
 118     {
 119       distances.setValue(i, ii, newdist[ii]);
 120       distances.setValue(ii, i, newdist[ii]);
 121     }
 122   }
 123
 124   /**
 125    * {@inheritDoc}
 126    */
 127   @Override
 128   protected double findMinDistance()
 129   {
 130     double min = Double.MAX_VALUE;
 131
 132     for (int i = 0; i < (noseqs - 1); i++)
 133     {
 134       for (int j = i + 1; j < noseqs; j++)
 135       {
 136         if (!done.get(i) && !done.get(j))
 137         {
 138           if (distances.getValue(i, j) < min)
 139           {
 140             mini = i;
 141             minj = j;
 142
 143             min = distances.getValue(i, j);
 144           }
 145         }
 146       }
 147     }
 148     return min;
 149   }
 150
 151   /**
 152    * {@inheritDoc}
 153    */
 154   @Override
 155   protected void findNewDistances(BinaryNode nodei, BinaryNode nodej,
 156           double dist)
 157   {
 158     double ih = 0;
 159     double jh = 0;
 160
 161     BinaryNode sni = nodei;
 162     BinaryNode snj = nodej;
 163
 164     while (sni != null)
 165     {
 166       ih = ih + sni.dist;
 167       sni = (BinaryNode) sni.left();
 168     }
 169
 170     while (snj != null)
 171     {
 172       jh = jh + snj.dist;
 173       snj = (BinaryNode) snj.left();
 174     }
 175
 176     nodei.dist = ((dist / 2) - ih);
 177     nodej.dist = ((dist / 2) - jh);
 178   }
 179
 180 }