2 * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3 * Copyright (C) $$Year-Rel$$ The Jalview Authors
5 * This file is part of Jalview.
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.
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.
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.
21 package jalview.analysis;
23 import jalview.api.analysis.ScoreModelI;
24 import jalview.api.analysis.SimilarityParamsI;
25 import jalview.datamodel.AlignmentView;
26 import jalview.datamodel.BinaryNode;
27 import jalview.datamodel.CigarArray;
28 import jalview.datamodel.SeqCigar;
29 import jalview.datamodel.SequenceI;
30 import jalview.datamodel.SequenceNode;
31 import jalview.math.MatrixI;
32 import jalview.viewmodel.AlignmentViewport;
34 import java.util.BitSet;
35 import java.util.Vector;
37 public abstract class TreeBuilder
39 public static final String AVERAGE_DISTANCE = "AV";
41 public static final String NEIGHBOUR_JOINING = "NJ";
43 protected Vector<BitSet> clusters;
45 protected SequenceI[] sequences;
47 public AlignmentView seqData;
49 protected BitSet done;
55 protected MatrixI distances;
75 Vector<SequenceNode> node;
77 private AlignmentView seqStrings;
84 * @param scoreParameters
86 public TreeBuilder(AlignmentViewport av, ScoreModelI sm,
87 SimilarityParamsI scoreParameters)
90 boolean selview = av.getSelectionGroup() != null
91 && av.getSelectionGroup().getSize() > 1;
92 seqStrings = av.getAlignmentView(selview);
96 end = av.getAlignment().getWidth();
97 this.sequences = av.getAlignment().getSequencesArray();
101 start = av.getSelectionGroup().getStartRes();
102 end = av.getSelectionGroup().getEndRes() + 1;
103 this.sequences = av.getSelectionGroup()
104 .getSequencesInOrder(av.getAlignment());
107 init(seqStrings, start, end);
109 computeTree(sm, scoreParameters);
112 public SequenceI[] getSequences()
123 * @return DOCUMENT ME!
125 double findHeight(BinaryNode nd)
132 if ((nd.left() == null) && (nd.right() == null))
134 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
136 if (nd.height > maxheight)
147 if (nd.parent() != null)
149 nd.height = ((BinaryNode) nd.parent()).height + nd.dist;
154 nd.height = (float) 0.0;
157 maxheight = findHeight((BinaryNode) (nd.left()));
158 maxheight = findHeight((BinaryNode) (nd.right()));
170 void reCount(BinaryNode nd)
174 // _lylimit = this.node.size();
184 void _reCount(BinaryNode nd)
186 // if (_lycount<_lylimit)
188 // System.err.println("Warning: depth of _recount greater than number of
197 if ((nd.left() != null) && (nd.right() != null))
201 _reCount((BinaryNode) nd.right());
203 BinaryNode l = nd.left();
204 BinaryNode r = nd.right();
206 nd.count = l.count + r.count;
207 nd.ycount = (l.ycount + r.ycount) / 2;
212 nd.ycount = ycount++;
220 * @return DOCUMENT ME!
222 public BinaryNode getTopNode()
229 * @return true if tree has real distances
231 public boolean hasDistances()
238 * @return true if tree has real bootstrap values
240 public boolean hasBootstrap()
245 public boolean hasRootDistance()
251 * Form clusters by grouping sub-clusters, starting from one sequence per
252 * cluster, and finishing when only two clusters remain
260 joinClusters(mini, minj);
265 int rightChild = done.nextClearBit(0);
266 int leftChild = done.nextClearBit(rightChild + 1);
268 joinClusters(leftChild, rightChild);
269 top = (node.elementAt(leftChild));
277 * Returns the minimum distance between two clusters, and also sets the
278 * indices of the clusters in fields mini and minj
282 protected abstract double findMinDistance();
285 * Calculates the tree using the given score model and parameters, and the
286 * configured tree type
288 * If the score model computes pairwise distance scores, then these are used
289 * directly to derive the tree
291 * If the score model computes similarity scores, then the range of the scores
292 * is reversed to give a distance measure, and this is used to derive the tree
295 * @param scoreOptions
297 protected void computeTree(ScoreModelI sm, SimilarityParamsI scoreOptions)
299 distances = sm.findDistances(seqData, scoreOptions);
303 noClus = clusters.size();
309 * Finds the node, at or below the given node, with the maximum distance, and
310 * saves the node and the distance value
314 void findMaxDist(BinaryNode nd)
321 if ((nd.left() == null) && (nd.right() == null))
323 double dist = nd.dist;
325 if (dist > maxDistValue)
333 findMaxDist((BinaryNode) nd.left());
334 findMaxDist((BinaryNode) nd.right());
339 * Calculates and returns r, whatever that is
346 protected double findr(int i, int j)
350 for (int k = 0; k < noseqs; k++)
352 if ((k != i) && (k != j) && (!done.get(k)))
354 tmp = tmp + distances.getValue(i, k);
360 tmp = tmp / (noClus - 2);
366 protected void init(AlignmentView seqView, int start, int end)
368 this.node = new Vector<SequenceNode>();
371 this.seqData = seqView;
375 SeqCigar[] seqs = new SeqCigar[sequences.length];
376 for (int i = 0; i < sequences.length; i++)
378 seqs[i] = new SeqCigar(sequences[i], start, end);
380 CigarArray sdata = new CigarArray(seqs);
381 sdata.addOperation(CigarArray.M, end - start + 1);
382 this.seqData = new AlignmentView(sdata, start);
386 * count the non-null sequences
392 for (SequenceI seq : sequences)
402 * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
407 void joinClusters(final int i, final int j)
409 double dist = distances.getValue(i, j);
414 findClusterDistance(i, j);
416 SequenceNode sn = new SequenceNode();
418 sn.setLeft((node.elementAt(i)));
419 sn.setRight((node.elementAt(j)));
421 BinaryNode tmpi = (node.elementAt(i));
422 BinaryNode tmpj = (node.elementAt(j));
424 findNewDistances(tmpi, tmpj, dist);
429 node.setElementAt(sn, i);
432 * move the members of cluster(j) to cluster(i)
433 * and mark cluster j as out of the game
435 clusters.get(i).or(clusters.get(j));
436 clusters.get(j).clear();
441 * Computes and stores new distances for nodei and nodej, given the previous
442 * distance between them
444 protected abstract void findNewDistances(BinaryNode nodei,
445 BinaryNode nodej, double previousDistance);
448 * Calculates and saves the distance between the combination of cluster(i) and
449 * cluster(j) and all other clusters. The form of the calculation depends on
450 * the tree clustering method being used.
455 protected abstract void findClusterDistance(int i, int j);
458 * Start by making a cluster for each individual sequence
462 clusters = new Vector<BitSet>();
464 for (int i = 0; i < noseqs; i++)
466 SequenceNode sn = new SequenceNode();
468 sn.setElement(sequences[i]);
469 sn.setName(sequences[i].getName());
471 BitSet bs = new BitSet();
473 clusters.addElement(bs);
477 public AlignmentView getOriginalData()