X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FTreeBuilder.java;h=0601dd93b177ccce184b7429a0e2552c72673e17;hb=da1ce6ca071deb35b983a41f6eeed43f30b3c3b2;hp=5347ba23cb8a9723b8f2d31ab49d05561c92bc85;hpb=a58c1f3005f962f3d48043e38fd5e621081eb9b0;p=jalview.git
diff --git a/src/jalview/analysis/TreeBuilder.java b/src/jalview/analysis/TreeBuilder.java
index 5347ba2..0601dd9 100644
--- a/src/jalview/analysis/TreeBuilder.java
+++ b/src/jalview/analysis/TreeBuilder.java
@@ -1,9 +1,27 @@
+/*
+ * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
+ * Copyright (C) $$Year-Rel$$ The Jalview Authors
+ *
+ * This file is part of Jalview.
+ *
+ * Jalview is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation, either version 3
+ * of the License, or (at your option) any later version.
+ *
+ * Jalview is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty
+ * of MERCHANTABILITY or FITNESS FOR A PARTICULAR
+ * PURPOSE. See the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Jalview. If not, see .
+ * The Jalview Authors are detailed in the 'AUTHORS' file.
+ */
package jalview.analysis;
-import jalview.api.analysis.DistanceScoreModelI;
import jalview.api.analysis.ScoreModelI;
import jalview.api.analysis.SimilarityParamsI;
-import jalview.api.analysis.SimilarityScoreModelI;
import jalview.datamodel.AlignmentView;
import jalview.datamodel.CigarArray;
import jalview.datamodel.SeqCigar;
@@ -81,8 +99,8 @@ public abstract class TreeBuilder
{
start = av.getSelectionGroup().getStartRes();
end = av.getSelectionGroup().getEndRes() + 1;
- this.sequences = av.getSelectionGroup().getSequencesInOrder(
- av.getAlignment());
+ this.sequences = av.getSelectionGroup()
+ .getSequencesInOrder(av.getAlignment());
}
init(seqStrings, start, end);
@@ -109,11 +127,11 @@ public abstract class TreeBuilder
{
return maxheight;
}
-
+
if ((nd.left() == null) && (nd.right() == null))
{
nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
-
+
if (nd.height > maxheight)
{
return nd.height;
@@ -134,11 +152,11 @@ public abstract class TreeBuilder
maxheight = 0;
nd.height = (float) 0.0;
}
-
+
maxheight = findHeight((SequenceNode) (nd.left()));
maxheight = findHeight((SequenceNode) (nd.right()));
}
-
+
return maxheight;
}
@@ -166,23 +184,24 @@ public abstract class TreeBuilder
{
// if (_lycount<_lylimit)
// {
- // System.err.println("Warning: depth of _recount greater than number of nodes.");
+ // System.err.println("Warning: depth of _recount greater than number of
+ // nodes.");
// }
if (nd == null)
{
return;
}
// _lycount++;
-
+
if ((nd.left() != null) && (nd.right() != null))
{
-
+
_reCount((SequenceNode) nd.left());
_reCount((SequenceNode) nd.right());
-
+
SequenceNode l = (SequenceNode) nd.left();
SequenceNode r = (SequenceNode) nd.right();
-
+
nd.count = l.count + r.count;
nd.ycount = (l.ycount + r.ycount) / 2;
}
@@ -236,23 +255,29 @@ public abstract class TreeBuilder
while (noClus > 2)
{
findMinDistance();
-
+
joinClusters(mini, minj);
-
+
noClus--;
}
-
+
int rightChild = done.nextClearBit(0);
int leftChild = done.nextClearBit(rightChild + 1);
-
+
joinClusters(leftChild, rightChild);
top = (node.elementAt(leftChild));
-
+
reCount(top);
findHeight(top);
findMaxDist(top);
}
+ /**
+ * Returns the minimum distance between two clusters, and also sets the
+ * indices of the clusters in fields mini and minj
+ *
+ * @return
+ */
protected abstract double findMinDistance();
/**
@@ -270,35 +295,20 @@ public abstract class TreeBuilder
*/
protected void computeTree(ScoreModelI sm, SimilarityParamsI scoreOptions)
{
- if (sm instanceof DistanceScoreModelI)
- {
- distances = ((DistanceScoreModelI) sm).findDistances(seqData,
- scoreOptions);
- }
- else if (sm instanceof SimilarityScoreModelI)
- {
- /*
- * compute similarity and invert it to give a distance measure
- * reverseRange(true) converts maximum similarity to zero distance
- */
- MatrixI result = ((SimilarityScoreModelI) sm).findSimilarities(
- seqData, scoreOptions);
- result.reverseRange(true);
- distances = result;
- }
-
+ distances = sm.findDistances(seqData, scoreOptions);
+
makeLeaves();
-
+
noClus = clusters.size();
-
+
cluster();
}
/**
- * DOCUMENT ME!
+ * Finds the node, at or below the given node, with the maximum distance, and
+ * saves the node and the distance value
*
* @param nd
- * DOCUMENT ME!
*/
void findMaxDist(SequenceNode nd)
{
@@ -306,11 +316,11 @@ public abstract class TreeBuilder
{
return;
}
-
+
if ((nd.left() == null) && (nd.right() == null))
{
double dist = nd.dist;
-
+
if (dist > maxDistValue)
{
maxdist = nd;
@@ -325,19 +335,17 @@ public abstract class TreeBuilder
}
/**
- * DOCUMENT ME!
+ * Calculates and returns r, whatever that is
*
* @param i
- * DOCUMENT ME!
* @param j
- * DOCUMENT ME!
*
- * @return DOCUMENT ME!
+ * @return
*/
protected double findr(int i, int j)
{
double tmp = 1;
-
+
for (int k = 0; k < noseqs; k++)
{
if ((k != i) && (k != j) && (!done.get(k)))
@@ -345,12 +353,12 @@ public abstract class TreeBuilder
tmp = tmp + distances.getValue(i, k);
}
}
-
+
if (noClus > 2)
{
tmp = tmp / (noClus - 2);
}
-
+
return tmp;
}
@@ -372,14 +380,14 @@ public abstract class TreeBuilder
sdata.addOperation(CigarArray.M, end - start + 1);
this.seqData = new AlignmentView(sdata, start);
}
-
+
/*
* count the non-null sequences
*/
noseqs = 0;
-
+
done = new BitSet();
-
+
for (SequenceI seq : sequences)
{
if (seq != null)
@@ -398,27 +406,27 @@ public abstract class TreeBuilder
void joinClusters(final int i, final int j)
{
double dist = distances.getValue(i, j);
-
+
ri = findr(i, j);
rj = findr(j, i);
-
+
findClusterDistance(i, j);
-
+
SequenceNode sn = new SequenceNode();
-
+
sn.setLeft((node.elementAt(i)));
sn.setRight((node.elementAt(j)));
-
+
SequenceNode tmpi = (node.elementAt(i));
SequenceNode tmpj = (node.elementAt(j));
-
+
findNewDistances(tmpi, tmpj, dist);
-
+
tmpi.setParent(sn);
tmpj.setParent(sn);
-
+
node.setElementAt(sn, i);
-
+
/*
* move the members of cluster(j) to cluster(i)
* and mark cluster j as out of the game
@@ -428,8 +436,12 @@ public abstract class TreeBuilder
done.set(j);
}
- protected abstract void findNewDistances(SequenceNode tmpi, SequenceNode tmpj,
- double dist);
+ /*
+ * Computes and stores new distances for nodei and nodej, given the previous
+ * distance between them
+ */
+ protected abstract void findNewDistances(SequenceNode nodei,
+ SequenceNode nodej, double previousDistance);
/**
* Calculates and saves the distance between the combination of cluster(i) and
@@ -447,11 +459,11 @@ public abstract class TreeBuilder
void makeLeaves()
{
clusters = new Vector();
-
+
for (int i = 0; i < noseqs; i++)
{
SequenceNode sn = new SequenceNode();
-
+
sn.setElement(sequences[i]);
sn.setName(sequences[i].getName());
node.addElement(sn);