X-Git-Url: http://source.jalview.org/gitweb/?a=blobdiff_plain;f=src%2Fjalview%2Fanalysis%2FTreeBuilder.java;h=61f65ff097104e233d68590be578512c4a0c9850;hb=cd5f5840fc9dbf8edc58b010ab1caae9a695c5fe;hp=78dc37f8a9341f9140e9a299b1d0e6f46289dafd;hpb=fe68da05540c32386ec63bd3beeadf8b9d624a16;p=jalview.git diff --git a/src/jalview/analysis/TreeBuilder.java b/src/jalview/analysis/TreeBuilder.java index 78dc37f..61f65ff 100644 --- a/src/jalview/analysis/TreeBuilder.java +++ b/src/jalview/analysis/TreeBuilder.java @@ -28,52 +28,21 @@ import jalview.datamodel.CigarArray; import jalview.datamodel.SeqCigar; import jalview.datamodel.SequenceI; import jalview.datamodel.SequenceNode; -import jalview.math.MatrixI; import jalview.viewmodel.AlignmentViewport; import java.util.BitSet; import java.util.Vector; -public abstract class TreeBuilder +public abstract class TreeBuilder extends TreeEngine { public static final String AVERAGE_DISTANCE = "AV"; public static final String NEIGHBOUR_JOINING = "NJ"; - protected Vector clusters; - protected SequenceI[] sequences; public AlignmentView seqData; - protected BitSet done; - - protected int noseqs; - - int noClus; - - protected MatrixI distances; - - protected int mini; - - protected int minj; - - protected double ri; - - protected double rj; - - BinaryNode maxdist; - - BinaryNode top; - - double maxDistValue; - - double maxheight; - - int ycount; - - Vector node; - private AlignmentView seqStrings; /** @@ -115,116 +84,6 @@ public abstract class TreeBuilder } /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - * - * @return DOCUMENT ME! - */ - double findHeight(BinaryNode nd) - { - if (nd == null) - { - return maxheight; - } - - if ((nd.left() == null) && (nd.right() == null)) - { - nd.height = ((BinaryNode) nd.parent()).height + nd.dist; - - if (nd.height > maxheight) - { - return nd.height; - } - else - { - return maxheight; - } - } - else - { - if (nd.parent() != null) - { - nd.height = ((BinaryNode) nd.parent()).height + nd.dist; - } - else - { - maxheight = 0; - nd.height = (float) 0.0; - } - - maxheight = findHeight((BinaryNode) (nd.left())); - maxheight = findHeight((BinaryNode) (nd.right())); - } - - return maxheight; - } - - /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - */ - void reCount(BinaryNode nd) - { - ycount = 0; - // _lycount = 0; - // _lylimit = this.node.size(); - _reCount(nd); - } - - /** - * DOCUMENT ME! - * - * @param nd - * DOCUMENT ME! - */ - void _reCount(BinaryNode nd) - { - // if (_lycount<_lylimit) - // { - // 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(nd.left()); - _reCount((BinaryNode) nd.right()); - - BinaryNode l = nd.left(); - BinaryNode r = nd.right(); - - nd.count = l.count + r.count; - nd.ycount = (l.ycount + r.ycount) / 2; - } - else - { - nd.count = 1; - nd.ycount = ycount++; - } - // _lycount--; - } - - /** - * DOCUMENT ME! - * - * @return DOCUMENT ME! - */ - public BinaryNode getTopNode() - { - return top; - } - - /** * * @return true if tree has real distances */ @@ -248,40 +107,6 @@ public abstract class TreeBuilder } /** - * Form clusters by grouping sub-clusters, starting from one sequence per - * cluster, and finishing when only two clusters remain - */ - void cluster() - { - 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(); - - /** * Calculates the tree using the given score model and parameters, and the * configured tree type *

@@ -305,67 +130,9 @@ public abstract class TreeBuilder cluster(); } - /** - * Finds the node, at or below the given node, with the maximum distance, and - * saves the node and the distance value - * - * @param nd - */ - void findMaxDist(BinaryNode nd) - { - if (nd == null) - { - return; - } - - if ((nd.left() == null) && (nd.right() == null)) - { - double dist = nd.dist; - - if (dist > maxDistValue) - { - maxdist = nd; - maxDistValue = dist; - } - } - else - { - findMaxDist((BinaryNode) nd.left()); - findMaxDist((BinaryNode) nd.right()); - } - } - - /** - * Calculates and returns r, whatever that is - * - * @param i - * @param j - * - * @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))) - { - tmp = tmp + distances.getValue(i, k); - } - } - - if (noClus > 2) - { - tmp = tmp / (noClus - 2); - } - - return tmp; - } - protected void init(AlignmentView seqView, int start, int end) { - this.node = new Vector(); + this.node = new Vector(); if (seqView != null) { this.seqData = seqView; @@ -399,62 +166,6 @@ public abstract class TreeBuilder } /** - * Merges cluster(j) to cluster(i) and recalculates cluster and node distances - * - * @param i - * @param j - */ - 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))); - - BinaryNode tmpi = (node.elementAt(i)); - BinaryNode 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 - */ - clusters.get(i).or(clusters.get(j)); - clusters.get(j).clear(); - done.set(j); - } - - /* - * Computes and stores new distances for nodei and nodej, given the previous - * distance between them - */ - protected abstract void findNewDistances(BinaryNode nodei, - BinaryNode nodej, double previousDistance); - - /** - * Calculates and saves the distance between the combination of cluster(i) and - * cluster(j) and all other clusters. The form of the calculation depends on - * the tree clustering method being used. - * - * @param i - * @param j - */ - protected abstract void findClusterDistance(int i, int j); - - /** * Start by making a cluster for each individual sequence */ void makeLeaves()