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.bin.Cache;
24 import jalview.datamodel.AlignmentView;
25 import jalview.datamodel.BinaryNode;
26 import jalview.datamodel.NodeTransformI;
27 import jalview.datamodel.Sequence;
28 import jalview.datamodel.SequenceI;
29 import jalview.datamodel.SequenceNode;
30 import jalview.io.NewickFile;
32 import java.util.ArrayList;
33 import java.util.Enumeration;
34 import java.util.List;
35 import java.util.Vector;
38 * A model of a tree, either computed by Jalview or loaded from a file or other
41 public class TreeModel
44 SequenceI[] sequences;
47 * SequenceData is a string representation of what the user
48 * sees. The display may contain hidden columns.
50 private AlignmentView seqData;
62 Vector<SequenceNode> node;
64 boolean hasDistances = true; // normal case for jalview trees
66 boolean hasBootstrap = false; // normal case for jalview trees
68 private boolean hasRootDistance = true;
71 * Create a new TreeModel object with leaves associated with sequences in
72 * seqs, and (optionally) original alignment data represented by Cigar strings
81 public TreeModel(SequenceI[] seqs, AlignmentView odata,
84 this(seqs, treefile.getTree(), treefile.hasDistances(),
85 treefile.hasBootstrap(), treefile.hasRootDistance());
88 associateLeavesToSequences(seqs);
92 * Constructor given a calculated tree
96 public TreeModel(TreeBuilder tree)
98 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(),
99 tree.hasBootstrap(), tree.hasRootDistance());
100 seqData = tree.getOriginalData();
104 * Constructor given sequences, root node and tree property flags
112 public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
113 boolean hasBoot, boolean hasRootDist)
115 this.sequences = seqs;
118 hasDistances = hasDist;
119 hasBootstrap = hasBoot;
120 hasRootDistance = hasRootDist;
122 maxheight = findHeight(top);
128 public void associateLeavesToSequences(SequenceI[] seqs)
130 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
132 Vector<SequenceNode> leaves = findLeaves(top);
134 int namesleft = seqs.length;
136 SequenceI nodeSequence;
137 String nodeSequenceName;
138 Vector<SequenceI> one2many = new Vector<>();
139 // int countOne2Many = 0;
141 for (SequenceNode sn : leaves)
143 nodeSequenceName = sn.getName();
148 nodeSequence = algnIds.findIdMatch(nodeSequenceName);
151 if (nodeSequence != null)
153 sn.setElement(nodeSequence);
154 if (one2many.contains(nodeSequence))
157 // if (Cache.isDebugEnabled())
158 // Cache.debug("One 2 many relationship for
163 one2many.addElement(nodeSequence);
169 sn.setElement(new Sequence(nodeSequenceName, "THISISAPLACEHLDER"));
170 sn.setPlaceholder(true);
173 // if (Cache.isDebugEnabled() && countOne2Many>0) {
174 // Cache.debug("There were "+countOne2Many+" alignment
175 // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
182 * Generate a string representation of the Tree
184 * @return Newick File with all tree data available
186 public String print()
188 NewickFile fout = new NewickFile(getTopNode());
190 return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
200 * used when the alignment associated to a tree has changed.
203 * Sequence set to be associated with tree nodes
205 public void updatePlaceHolders(List<SequenceI> list)
207 Vector<SequenceNode> leaves = findLeaves(top);
209 int sz = leaves.size();
210 SequenceIdMatcher seqmatcher = null;
215 SequenceNode leaf = leaves.elementAt(i++);
217 if (list.contains(leaf.element()))
219 leaf.setPlaceholder(false);
223 if (seqmatcher == null)
225 // Only create this the first time we need it
226 SequenceI[] seqs = new SequenceI[list.size()];
228 for (int j = 0; j < seqs.length; j++)
230 seqs[j] = list.get(j);
233 seqmatcher = new SequenceIdMatcher(seqs);
236 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
240 if (!leaf.isPlaceholder())
242 // remapping the node to a new sequenceI - should remove any refs to
244 // TODO - make many sequenceI to one leaf mappings possible!
247 leaf.setPlaceholder(false);
248 leaf.setElement(nam);
252 if (!leaf.isPlaceholder())
254 // Construct a new placeholder sequence object for this leaf
256 new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
258 leaf.setPlaceholder(true);
266 * rename any nodes according to their associated sequence. This will modify
267 * the tree's metadata! (ie the original NewickFile or newly generated
268 * BinaryTree's label data)
270 public void renameAssociatedNodes()
272 applyToNodes(new NodeTransformI()
276 public void transform(BinaryNode nd)
278 Object el = nd.element();
279 if (el != null && el instanceof SequenceI)
281 nd.setName(((SequenceI) el).getName());
288 * Search for leaf nodes below (or at) the given node
291 * root node to search from
295 public Vector<SequenceNode> findLeaves(SequenceNode nd)
297 Vector<SequenceNode> leaves = new Vector<>();
298 findLeaves(nd, leaves);
303 * Search for leaf nodes.
306 * root node to search from
308 * Vector of leaves to add leaf node objects too.
310 * @return Vector of leaf nodes on binary tree
312 Vector<SequenceNode> findLeaves(SequenceNode nd,
313 Vector<SequenceNode> leaves)
320 if ((nd.left() == null) && (nd.right() == null)) // Interior node
323 leaves.addElement(nd);
330 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
331 * leaves.addElement(node); }
333 findLeaves((SequenceNode) nd.left(), leaves);
334 findLeaves((SequenceNode) nd.right(), leaves);
341 * printNode is mainly for debugging purposes.
346 void printNode(SequenceNode nd)
353 if ((nd.left() == null) && (nd.right() == null))
355 System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
356 System.out.println("Dist " + nd.dist);
357 System.out.println("Boot " + nd.getBootstrap());
361 System.out.println("Dist " + nd.dist);
362 printNode((SequenceNode) nd.left());
363 printNode((SequenceNode) nd.right());
370 * @return DOCUMENT ME!
372 public double getMaxHeight()
378 * Makes a list of groups, where each group is represented by a node whose
379 * height (distance from the root node), as a fraction of the height of the
380 * whole tree, is greater than the given threshold. This corresponds to
381 * selecting the nodes immediately to the right of a vertical line
382 * partitioning the tree (if the tree is drawn with root to the left). Each
383 * such node represents a group that contains all of the sequences linked to
384 * the child leaf nodes.
389 public List<SequenceNode> groupNodes(float threshold)
391 List<SequenceNode> groups = new ArrayList<>();
392 _groupNodes(groups, getTopNode(), threshold);
396 protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
404 if ((nd.height / maxheight) > threshold)
410 _groupNodes(groups, (SequenceNode) nd.left(), threshold);
411 _groupNodes(groups, (SequenceNode) nd.right(), threshold);
421 * @return DOCUMENT ME!
423 public double findHeight(SequenceNode nd)
430 if ((nd.left() == null) && (nd.right() == null))
432 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
434 if (nd.height > maxheight)
445 if (nd.parent() != null)
447 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
452 nd.height = (float) 0.0;
455 maxheight = findHeight((SequenceNode) (nd.left()));
456 maxheight = findHeight((SequenceNode) (nd.right()));
468 void printN(SequenceNode nd)
475 if ((nd.left() != null) && (nd.right() != null))
477 printN((SequenceNode) nd.left());
478 printN((SequenceNode) nd.right());
482 System.out.println(" name = " + ((SequenceI) nd.element()).getName());
486 " dist = " + nd.dist + " " + nd.count + " " + nd.height);
495 public void reCount(SequenceNode nd)
499 // _lylimit = this.node.size();
503 // private long _lycount = 0, _lylimit = 0;
511 void _reCount(SequenceNode nd)
513 // if (_lycount<_lylimit)
515 // System.err.println("Warning: depth of _recount greater than number of
524 if ((nd.left() != null) && (nd.right() != null))
527 _reCount((SequenceNode) nd.left());
528 _reCount((SequenceNode) nd.right());
530 SequenceNode l = (SequenceNode) nd.left();
531 SequenceNode r = (SequenceNode) nd.right();
533 nd.count = l.count + r.count;
534 nd.ycount = (l.ycount + r.ycount) / 2;
539 nd.ycount = ycount++;
550 public void swapNodes(SequenceNode nd)
557 SequenceNode tmp = (SequenceNode) nd.left();
559 nd.setLeft(nd.right());
571 void changeDirection(SequenceNode nd, SequenceNode dir)
578 if (nd.parent() != top)
580 changeDirection((SequenceNode) nd.parent(), nd);
582 SequenceNode tmp = (SequenceNode) nd.parent();
584 if (dir == nd.left())
589 else if (dir == nd.right())
597 if (dir == nd.left())
599 nd.setParent(nd.left());
601 if (top.left() == nd)
603 nd.setRight(top.right());
607 nd.setRight(top.left());
612 nd.setParent(nd.right());
614 if (top.left() == nd)
616 nd.setLeft(top.right());
620 nd.setLeft(top.left());
629 * @return DOCUMENT ME!
631 public SequenceNode getTopNode()
638 * @return true if tree has real distances
640 public boolean hasDistances()
647 * @return true if tree has real bootstrap values
649 public boolean hasBootstrap()
654 public boolean hasRootDistance()
656 return hasRootDistance;
660 * apply the given transform to all the nodes in the tree.
662 * @param nodeTransformI
664 public void applyToNodes(NodeTransformI nodeTransformI)
666 for (Enumeration<SequenceNode> nodes = node.elements(); nodes
667 .hasMoreElements(); nodeTransformI
668 .transform(nodes.nextElement()))
674 public AlignmentView getOriginalData()