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.datamodel.AlignmentView;
24 import jalview.datamodel.BinaryNode;
25 import jalview.datamodel.NodeTransformI;
26 import jalview.datamodel.Sequence;
27 import jalview.datamodel.SequenceI;
28 import jalview.datamodel.SequenceNode;
29 import jalview.io.NewickFile;
31 import java.util.ArrayList;
32 import java.util.Enumeration;
33 import java.util.List;
34 import java.util.Vector;
37 * A model of a tree, either computed by Jalview or loaded from a file or other
40 public class TreeModel
43 SequenceI[] sequences;
46 * SequenceData is a string representation of what the user
47 * sees. The display may contain hidden columns.
49 private AlignmentView seqData;
61 Vector<SequenceNode> node;
63 boolean hasDistances = true; // normal case for jalview trees
65 boolean hasBootstrap = false; // normal case for jalview trees
67 private boolean hasRootDistance = true;
70 * Create a new TreeModel object with leaves associated with sequences in
71 * seqs, and (optionally) original alignment data represented by Cigar strings
80 public TreeModel(SequenceI[] seqs, AlignmentView odata,
83 this(seqs, treefile.getTree(), treefile.hasDistances(),
84 treefile.hasBootstrap(), treefile.hasRootDistance());
87 associateLeavesToSequences(seqs);
91 * Constructor given a calculated tree
95 public TreeModel(TreeBuilder tree)
97 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(),
98 tree.hasBootstrap(), tree.hasRootDistance());
99 seqData = tree.getOriginalData();
103 * Constructor given sequences, root node and tree property flags
111 public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
112 boolean hasBoot, boolean hasRootDist)
114 this.sequences = seqs;
117 hasDistances = hasDist;
118 hasBootstrap = hasBoot;
119 hasRootDistance = hasRootDist;
121 maxheight = findHeight(top);
127 public void associateLeavesToSequences(SequenceI[] seqs)
129 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
131 Vector<SequenceNode> leaves = findLeaves(top);
133 int namesleft = seqs.length;
135 SequenceI nodeSequence;
136 String nodeSequenceName;
137 Vector<SequenceI> one2many = new Vector<>();
138 // int countOne2Many = 0;
140 for (SequenceNode sn : leaves)
142 nodeSequenceName = sn.getName();
147 nodeSequence = algnIds.findIdMatch(nodeSequenceName);
150 if (nodeSequence != null)
152 sn.setElement(nodeSequence);
153 if (one2many.contains(nodeSequence))
156 // if (jalview.bin.Cache.log.isDebugEnabled())
157 // jalview.bin.Cache.log.debug("One 2 many relationship for
162 one2many.addElement(nodeSequence);
168 sn.setElement(new Sequence(nodeSequenceName, "THISISAPLACEHLDER"));
169 sn.setPlaceholder(true);
172 // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
173 // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
174 // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
181 * Generate a string representation of the Tree
183 * @return Newick File with all tree data available
185 public String print()
187 NewickFile fout = new NewickFile(getTopNode());
189 return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
199 * used when the alignment associated to a tree has changed.
202 * Sequence set to be associated with tree nodes
204 public void updatePlaceHolders(List<SequenceI> list)
206 Vector<SequenceNode> leaves = findLeaves(top);
208 int sz = leaves.size();
209 SequenceIdMatcher seqmatcher = null;
214 SequenceNode leaf = leaves.elementAt(i++);
216 if (list.contains(leaf.element()))
218 leaf.setPlaceholder(false);
222 if (seqmatcher == null)
224 // Only create this the first time we need it
225 SequenceI[] seqs = new SequenceI[list.size()];
227 for (int j = 0; j < seqs.length; j++)
229 seqs[j] = list.get(j);
232 seqmatcher = new SequenceIdMatcher(seqs);
235 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
239 if (!leaf.isPlaceholder())
241 // remapping the node to a new sequenceI - should remove any refs to
243 // TODO - make many sequenceI to one leaf mappings possible!
246 leaf.setPlaceholder(false);
247 leaf.setElement(nam);
251 if (!leaf.isPlaceholder())
253 // Construct a new placeholder sequence object for this leaf
255 new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
257 leaf.setPlaceholder(true);
265 * rename any nodes according to their associated sequence. This will modify
266 * the tree's metadata! (ie the original NewickFile or newly generated
267 * BinaryTree's label data)
269 public void renameAssociatedNodes()
271 applyToNodes(new NodeTransformI()
275 public void transform(BinaryNode nd)
277 Object el = nd.element();
278 if (el != null && el instanceof SequenceI)
280 nd.setName(((SequenceI) el).getName());
287 * Search for leaf nodes below (or at) the given node
290 * root node to search from
294 public Vector<SequenceNode> findLeaves(SequenceNode nd)
296 Vector<SequenceNode> leaves = new Vector<>();
297 findLeaves(nd, leaves);
302 * Search for leaf nodes.
305 * root node to search from
307 * Vector of leaves to add leaf node objects too.
309 * @return Vector of leaf nodes on binary tree
311 Vector<SequenceNode> findLeaves(SequenceNode nd,
312 Vector<SequenceNode> leaves)
319 if ((nd.left() == null) && (nd.right() == null)) // Interior node
322 leaves.addElement(nd);
329 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
330 * leaves.addElement(node); }
332 findLeaves((SequenceNode) nd.left(), leaves);
333 findLeaves((SequenceNode) nd.right(), leaves);
340 * printNode is mainly for debugging purposes.
345 void printNode(SequenceNode nd)
352 if ((nd.left() == null) && (nd.right() == null))
354 System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
355 System.out.println("Dist " + nd.dist);
356 System.out.println("Boot " + nd.getBootstrap());
360 System.out.println("Dist " + nd.dist);
361 printNode((SequenceNode) nd.left());
362 printNode((SequenceNode) nd.right());
369 * @return DOCUMENT ME!
371 public double getMaxHeight()
377 * Makes a list of groups, where each group is represented by a node whose
378 * height (distance from the root node), as a fraction of the height of the
379 * whole tree, is greater than the given threshold. This corresponds to
380 * selecting the nodes immediately to the right of a vertical line
381 * partitioning the tree (if the tree is drawn with root to the left). Each
382 * such node represents a group that contains all of the sequences linked to
383 * the child leaf nodes.
388 public List<SequenceNode> groupNodes(float threshold)
390 List<SequenceNode> groups = new ArrayList<>();
391 _groupNodes(groups, getTopNode(), threshold);
395 protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
403 if ((nd.height / maxheight) > threshold)
409 _groupNodes(groups, (SequenceNode) nd.left(), threshold);
410 _groupNodes(groups, (SequenceNode) nd.right(), threshold);
420 * @return DOCUMENT ME!
422 public double findHeight(SequenceNode nd)
429 if ((nd.left() == null) && (nd.right() == null))
431 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
433 if (nd.height > maxheight)
444 if (nd.parent() != null)
446 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
451 nd.height = (float) 0.0;
454 maxheight = findHeight((SequenceNode) (nd.left()));
455 maxheight = findHeight((SequenceNode) (nd.right()));
467 void printN(SequenceNode nd)
474 if ((nd.left() != null) && (nd.right() != null))
476 printN((SequenceNode) nd.left());
477 printN((SequenceNode) nd.right());
481 System.out.println(" name = " + ((SequenceI) nd.element()).getName());
485 " dist = " + nd.dist + " " + nd.count + " " + nd.height);
494 public void reCount(SequenceNode nd)
498 // _lylimit = this.node.size();
502 // private long _lycount = 0, _lylimit = 0;
510 void _reCount(SequenceNode nd)
512 // if (_lycount<_lylimit)
514 // System.err.println("Warning: depth of _recount greater than number of
523 if ((nd.left() != null) && (nd.right() != null))
526 _reCount((SequenceNode) nd.left());
527 _reCount((SequenceNode) nd.right());
529 SequenceNode l = (SequenceNode) nd.left();
530 SequenceNode r = (SequenceNode) nd.right();
532 nd.count = l.count + r.count;
533 nd.ycount = (l.ycount + r.ycount) / 2;
538 nd.ycount = ycount++;
549 public void swapNodes(SequenceNode nd)
556 SequenceNode tmp = (SequenceNode) nd.left();
558 nd.setLeft(nd.right());
570 void changeDirection(SequenceNode nd, SequenceNode dir)
577 if (nd.parent() != top)
579 changeDirection((SequenceNode) nd.parent(), nd);
581 SequenceNode tmp = (SequenceNode) nd.parent();
583 if (dir == nd.left())
588 else if (dir == nd.right())
596 if (dir == nd.left())
598 nd.setParent(nd.left());
600 if (top.left() == nd)
602 nd.setRight(top.right());
606 nd.setRight(top.left());
611 nd.setParent(nd.right());
613 if (top.left() == nd)
615 nd.setLeft(top.right());
619 nd.setLeft(top.left());
628 * @return DOCUMENT ME!
630 public SequenceNode getTopNode()
637 * @return true if tree has real distances
639 public boolean hasDistances()
646 * @return true if tree has real bootstrap values
648 public boolean hasBootstrap()
653 public boolean hasRootDistance()
655 return hasRootDistance;
659 * apply the given transform to all the nodes in the tree.
661 * @param nodeTransformI
663 public void applyToNodes(NodeTransformI nodeTransformI)
665 for (Enumeration<SequenceNode> nodes = node.elements(); nodes
666 .hasMoreElements(); nodeTransformI
667 .transform(nodes.nextElement()))
673 public AlignmentView getOriginalData()