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.CigarArray;
27 import jalview.datamodel.SeqCigar;
28 import jalview.datamodel.SequenceI;
29 import jalview.datamodel.SequenceNode;
30 import jalview.math.MatrixI;
31 import jalview.viewmodel.AlignmentViewport;
33 import java.util.BitSet;
34 import java.util.Vector;
36 public abstract class TreeBuilder
38 public static final String AVERAGE_DISTANCE = "AV";
40 public static final String NEIGHBOUR_JOINING = "NJ";
42 protected Vector<BitSet> clusters;
44 protected SequenceI[] sequences;
46 public AlignmentView seqData;
48 protected BitSet done;
54 protected MatrixI distances;
74 Vector<SequenceNode> node;
76 protected ScoreModelI scoreModel;
78 protected SimilarityParamsI scoreParams;
80 private AlignmentViewport avport;
82 private AlignmentView seqStrings; // redundant? (see seqData)
89 * @param scoreParameters
91 public TreeBuilder(AlignmentViewport av, ScoreModelI sm,
92 SimilarityParamsI scoreParameters)
96 boolean selview = av.getSelectionGroup() != null
97 && av.getSelectionGroup().getSize() > 1;
98 seqStrings = av.getAlignmentView(selview);
102 end = av.getAlignment().getWidth();
103 this.sequences = av.getAlignment().getSequencesArray();
107 start = av.getSelectionGroup().getStartRes();
108 end = av.getSelectionGroup().getEndRes() + 1;
109 this.sequences = av.getSelectionGroup()
110 .getSequencesInOrder(av.getAlignment());
113 init(seqStrings, start, end);
115 computeTree(sm, scoreParameters);
118 public SequenceI[] getSequences()
129 * @return DOCUMENT ME!
131 double findHeight(SequenceNode nd)
138 if ((nd.left() == null) && (nd.right() == null))
140 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
142 if (nd.height > maxHeight)
153 if (nd.parent() != null)
155 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
160 nd.height = (float) 0.0;
163 maxHeight = findHeight((SequenceNode) (nd.left()));
164 maxHeight = findHeight((SequenceNode) (nd.right()));
176 void reCount(SequenceNode nd)
180 // _lylimit = this.node.size();
190 void _reCount(SequenceNode nd)
192 // if (_lycount<_lylimit)
194 // System.err.println("Warning: depth of _recount greater than number of
203 if ((nd.left() != null) && (nd.right() != null))
206 _reCount((SequenceNode) nd.left());
207 _reCount((SequenceNode) nd.right());
209 SequenceNode l = (SequenceNode) nd.left();
210 SequenceNode r = (SequenceNode) nd.right();
212 nd.count = l.count + r.count;
213 nd.ycount = (l.ycount + r.ycount) / 2;
218 nd.ycount = ycount++;
226 * @return DOCUMENT ME!
228 public SequenceNode getTopNode()
235 * @return true if tree has real distances
237 public boolean hasDistances()
244 * @return true if tree has real bootstrap values
246 public boolean hasBootstrap()
251 public boolean hasRootDistance()
257 * Form clusters by grouping sub-clusters, starting from one sequence per
258 * cluster, and finishing when only two clusters remain
266 joinClusters(mini, minj);
271 int rightChild = done.nextClearBit(0);
272 int leftChild = done.nextClearBit(rightChild + 1);
274 joinClusters(leftChild, rightChild);
275 top = (node.elementAt(leftChild));
283 * Returns the minimum distance between two clusters, and also sets the
284 * indices of the clusters in fields mini and minj
288 protected abstract double findMinDistance();
291 * Calculates the tree using the given score model and parameters, and the
292 * configured tree type
294 * If the score model computes pairwise distance scores, then these are used
295 * directly to derive the tree
297 * If the score model computes similarity scores, then the range of the scores
298 * is reversed to give a distance measure, and this is used to derive the tree
301 * @param scoreOptions
303 protected void computeTree(ScoreModelI sm, SimilarityParamsI scoreOptions)
306 this.scoreModel = sm;
307 this.scoreParams = scoreOptions;
309 distances = scoreModel.findDistances(seqData, scoreParams);
313 noClus = clusters.size();
319 * Finds the node, at or below the given node, with the maximum distance, and
320 * saves the node and the distance value
324 void findMaxDist(SequenceNode nd)
331 if ((nd.left() == null) && (nd.right() == null))
333 double dist = nd.dist;
335 if (dist > maxDistValue)
343 findMaxDist((SequenceNode) nd.left());
344 findMaxDist((SequenceNode) nd.right());
349 * Calculates and returns r, whatever that is
356 protected double findr(int i, int j)
360 for (int k = 0; k < noseqs; k++)
362 if ((k != i) && (k != j) && (!done.get(k)))
364 tmp = tmp + distances.getValue(i, k);
370 tmp = tmp / (noClus - 2);
376 protected void init(AlignmentView seqView, int start, int end)
378 this.node = new Vector<>();
381 this.seqData = seqView;
385 SeqCigar[] seqs = new SeqCigar[sequences.length];
386 for (int i = 0; i < sequences.length; i++)
388 seqs[i] = new SeqCigar(sequences[i], start, end);
390 CigarArray sdata = new CigarArray(seqs);
391 sdata.addOperation(CigarArray.M, end - start + 1);
392 this.seqData = new AlignmentView(sdata, start);
396 * count the non-null sequences
402 for (SequenceI seq : sequences)
412 * Merges cluster(j) to cluster(i) and recalculates cluster and node distances
417 void joinClusters(final int i, final int j)
419 double dist = distances.getValue(i, j);
424 findClusterDistance(i, j);
426 SequenceNode sn = new SequenceNode();
428 sn.setLeft((node.elementAt(i)));
429 sn.setRight((node.elementAt(j)));
431 SequenceNode tmpi = (node.elementAt(i));
432 SequenceNode tmpj = (node.elementAt(j));
434 findNewDistances(tmpi, tmpj, dist);
439 node.setElementAt(sn, i);
442 * move the members of cluster(j) to cluster(i)
443 * and mark cluster j as out of the game
445 clusters.get(i).or(clusters.get(j));
446 clusters.get(j).clear();
451 * Computes and stores new distances for nodei and nodej, given the previous
452 * distance between them
454 protected abstract void findNewDistances(SequenceNode nodei,
455 SequenceNode nodej, double previousDistance);
458 * Calculates and saves the distance between the combination of cluster(i) and
459 * cluster(j) and all other clusters. The form of the calculation depends on
460 * the tree clustering method being used.
465 protected abstract void findClusterDistance(int i, int j);
468 * Start by making a cluster for each individual sequence
472 clusters = new Vector<>();
474 for (int i = 0; i < noseqs; i++)
476 SequenceNode sn = new SequenceNode();
478 sn.setElement(sequences[i]);
479 sn.setName(sequences[i].getName());
482 BitSet bs = new BitSet();
484 clusters.addElement(bs);
488 public AlignmentView getOriginalData()
493 public MatrixI getDistances()
498 public ScoreModelI getScoreModel()
503 public SimilarityParamsI getScoreParams()
508 public AlignmentViewport getAvport()