Merge remote-tracking branch 'origin/tasks/JAL-3035_remove_dasobert_dependency' into...
[jalview.git] / 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 }