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<BinaryNode> 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, BinaryNode 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<BinaryNode> leaves = findLeaves(top);
134 int namesleft = seqs.length;
139 Vector<SequenceI> one2many = new Vector<SequenceI>();
140 // int countOne2Many = 0;
141 while (i < leaves.size())
143 // TODO - decide if we get rid of the polymorphism here ?
144 j = (SequenceNode) leaves.elementAt(i++);
145 realnam = j.getName();
150 nam = algnIds.findIdMatch(realnam);
156 if (one2many.contains(nam))
159 // if (Cache.isDebugEnabled())
160 // Cache.debug("One 2 many relationship for
165 one2many.addElement(nam);
171 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
172 j.setPlaceholder(true);
175 // if (Cache.isDebugEnabled() && countOne2Many>0) {
176 // Cache.debug("There were "+countOne2Many+" alignment
177 // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
184 * Generate a string representation of the Tree
186 * @return Newick File with all tree data available
188 public String print()
190 NewickFile fout = new NewickFile(getTopNode());
192 return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
202 * used when the alignment associated to a tree has changed.
205 * Sequence set to be associated with tree nodes
207 public void updatePlaceHolders(List<SequenceI> list)
209 Vector<BinaryNode> leaves = findLeaves(top);
211 int sz = leaves.size();
212 SequenceIdMatcher seqmatcher = null;
217 SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
219 if (list.contains(leaf.element()))
221 leaf.setPlaceholder(false);
225 if (seqmatcher == null)
227 // Only create this the first time we need it
228 SequenceI[] seqs = new SequenceI[list.size()];
230 for (int j = 0; j < seqs.length; j++)
232 seqs[j] = list.get(j);
235 seqmatcher = new SequenceIdMatcher(seqs);
238 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
242 if (!leaf.isPlaceholder())
244 // remapping the node to a new sequenceI - should remove any refs to
246 // TODO - make many sequenceI to one leaf mappings possible!
249 leaf.setPlaceholder(false);
250 leaf.setElement(nam);
254 if (!leaf.isPlaceholder())
256 // Construct a new placeholder sequence object for this leaf
258 new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
260 leaf.setPlaceholder(true);
268 * rename any nodes according to their associated sequence. This will modify
269 * the tree's metadata! (ie the original NewickFile or newly generated
270 * BinaryTree's label data)
272 public void renameAssociatedNodes()
274 applyToNodes(new NodeTransformI()
278 public void transform(BinaryNode nd)
280 Object el = nd.element();
281 if (el != null && el instanceof SequenceI)
283 nd.setName(((SequenceI) el).getName());
290 * Search for leaf nodes below (or at) the given node
293 * root node to search from
297 public Vector<BinaryNode> findLeaves(BinaryNode top2)
299 Vector<BinaryNode> leaves = new Vector<BinaryNode>();
300 findLeaves(top2, leaves);
305 * Search for leaf nodes.
308 * root node to search from
310 * Vector of leaves to add leaf node objects too.
312 * @return Vector of leaf nodes on binary tree
314 Vector<BinaryNode> findLeaves(BinaryNode nd, Vector<BinaryNode> leaves)
321 if ((nd.left() == null) && (nd.right() == null)) // Interior node
324 leaves.addElement(nd);
331 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
332 * leaves.addElement(node); }
334 findLeaves(nd.left(), leaves);
335 findLeaves(nd.right(), leaves);
342 * printNode is mainly for debugging purposes.
347 void printNode(BinaryNode nd)
354 if ((nd.left() == null) && (nd.right() == null))
356 // TODO FIX FOR COLUMN TREES
358 .outPrintln("Leaf = " + ((SequenceI) nd.element()).getName());
359 jalview.bin.Console.outPrintln("Dist " + nd.dist);
360 jalview.bin.Console.outPrintln("Boot " + nd.getBootstrap());
364 jalview.bin.Console.outPrintln("Dist " + nd.dist);
365 printNode((BinaryNode) nd.left());
366 printNode((BinaryNode) nd.right());
373 * @return DOCUMENT ME!
375 public double getMaxHeight()
381 * Makes a list of groups, where each group is represented by a node whose
382 * height (distance from the root node), as a fraction of the height of the
383 * whole tree, is greater than the given threshold. This corresponds to
384 * selecting the nodes immediately to the right of a vertical line
385 * partitioning the tree (if the tree is drawn with root to the left). Each
386 * such node represents a group that contains all of the sequences linked to
387 * the child leaf nodes.
392 public List<BinaryNode> groupNodes(float threshold)
394 List<BinaryNode> groups = new ArrayList<BinaryNode>();
395 _groupNodes(groups, getTopNode(), threshold);
399 protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
407 if ((nd.height / maxheight) > threshold)
413 _groupNodes(groups, nd.left(), threshold);
414 _groupNodes(groups, nd.right(), threshold);
424 * @return DOCUMENT ME!
426 public double findHeight(BinaryNode nd)
433 if ((nd.left() == null) && (nd.right() == null))
435 nd.height = nd.parent().height + nd.dist;
437 if (nd.height > maxheight)
448 if (nd.parent() != null)
450 nd.height = nd.parent().height + nd.dist;
455 nd.height = (float) 0.0;
458 maxheight = findHeight((BinaryNode) (nd.left()));
459 maxheight = findHeight((BinaryNode) (nd.right()));
471 void printN(BinaryNode nd)
478 if ((nd.left() != null) && (nd.right() != null))
480 printN((BinaryNode) nd.left());
481 printN((BinaryNode) nd.right());
485 jalview.bin.Console.outPrintln(
486 " name = " + ((SequenceI) nd.element()).getName());
489 jalview.bin.Console.outPrintln(
490 " dist = " + nd.dist + " " + nd.count + " " + nd.height);
499 public void reCount(BinaryNode nd)
503 // _lylimit = this.node.size();
507 // private long _lycount = 0, _lylimit = 0;
515 void _reCount(BinaryNode nd)
517 // if (_lycount<_lylimit)
519 // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
529 if ((nd.left() != null) && (nd.right() != null))
532 _reCount((BinaryNode) nd.left());
533 _reCount((BinaryNode) nd.right());
535 BinaryNode l = (BinaryNode) nd.left();
536 BinaryNode r = (BinaryNode) nd.right();
538 nd.count = l.count + r.count;
539 nd.ycount = (l.ycount + r.ycount) / 2;
544 nd.ycount = ycount++;
555 public void swapNodes(BinaryNode nd)
562 BinaryNode tmp = (BinaryNode) nd.left();
564 nd.setLeft(nd.right());
576 void changeDirection(BinaryNode nd, BinaryNode dir)
583 if (nd.parent() != top)
585 changeDirection((BinaryNode) nd.parent(), nd);
587 BinaryNode tmp = (BinaryNode) nd.parent();
589 if (dir == nd.left())
594 else if (dir == nd.right())
602 if (dir == nd.left())
604 nd.setParent(nd.left());
606 if (top.left() == nd)
608 nd.setRight(top.right());
612 nd.setRight(top.left());
617 nd.setParent(nd.right());
619 if (top.left() == nd)
621 nd.setLeft(top.right());
625 nd.setLeft(top.left());
634 * @return DOCUMENT ME!
636 public BinaryNode getTopNode()
643 * @return true if tree has real distances
645 public boolean hasDistances()
652 * @return true if tree has real bootstrap values
654 public boolean hasBootstrap()
659 public boolean hasRootDistance()
661 return hasRootDistance;
665 * apply the given transform to all the nodes in the tree.
667 * @param nodeTransformI
669 public void applyToNodes(NodeTransformI nodeTransformI)
671 for (Enumeration<BinaryNode> nodes = node.elements(); nodes
672 .hasMoreElements(); nodeTransformI
673 .transform(nodes.nextElement()))
679 public AlignmentView getOriginalData()