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, NewickFile treefile)
82 this(seqs, treefile.getTree(), treefile.HasDistances(), treefile
83 .HasBootstrap(), treefile.HasRootDistance());
86 associateLeavesToSequences(seqs);
90 * Constructor given a calculated tree
94 public TreeModel(TreeBuilder tree)
96 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(), tree
97 .hasBootstrap(), tree.hasRootDistance());
98 seqData = tree.getOriginalData();
102 * Constructor given sequences, root node and tree property flags
110 public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
111 boolean hasBoot, boolean hasRootDist)
113 this.sequences = seqs;
116 hasDistances = hasDist;
117 hasBootstrap = hasBoot;
118 hasRootDistance = hasRootDist;
120 maxheight = findHeight(top);
126 public void associateLeavesToSequences(SequenceI[] seqs)
128 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
130 Vector<SequenceNode> leaves = findLeaves(top);
133 int namesleft = seqs.length;
138 Vector<SequenceI> one2many = new Vector<SequenceI>();
139 // int countOne2Many = 0;
140 while (i < leaves.size())
142 j = leaves.elementAt(i++);
143 realnam = j.getName();
148 nam = algnIds.findIdMatch(realnam);
154 if (one2many.contains(nam))
157 // if (jalview.bin.Cache.log.isDebugEnabled())
158 // jalview.bin.Cache.log.debug("One 2 many relationship for
163 one2many.addElement(nam);
169 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
170 j.setPlaceholder(true);
173 // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
174 // jalview.bin.Cache.log.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(),
191 hasRootDistance()); // output all data available for tree
196 * used when the alignment associated to a tree has changed.
199 * Sequence set to be associated with tree nodes
201 public void updatePlaceHolders(List<SequenceI> list)
203 Vector<SequenceNode> leaves = findLeaves(top);
205 int sz = leaves.size();
206 SequenceIdMatcher seqmatcher = null;
211 SequenceNode leaf = leaves.elementAt(i++);
213 if (list.contains(leaf.element()))
215 leaf.setPlaceholder(false);
219 if (seqmatcher == null)
221 // Only create this the first time we need it
222 SequenceI[] seqs = new SequenceI[list.size()];
224 for (int j = 0; j < seqs.length; j++)
226 seqs[j] = list.get(j);
229 seqmatcher = new SequenceIdMatcher(seqs);
232 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
236 if (!leaf.isPlaceholder())
238 // remapping the node to a new sequenceI - should remove any refs to
240 // TODO - make many sequenceI to one leaf mappings possible!
243 leaf.setPlaceholder(false);
244 leaf.setElement(nam);
248 if (!leaf.isPlaceholder())
250 // Construct a new placeholder sequence object for this leaf
251 leaf.setElement(new Sequence(leaf.getName(),
252 "THISISAPLACEHLDER"));
254 leaf.setPlaceholder(true);
262 * rename any nodes according to their associated sequence. This will modify
263 * the tree's metadata! (ie the original NewickFile or newly generated
264 * BinaryTree's label data)
266 public void renameAssociatedNodes()
268 applyToNodes(new NodeTransformI()
272 public void transform(BinaryNode nd)
274 Object el = nd.element();
275 if (el != null && el instanceof SequenceI)
277 nd.setName(((SequenceI) el).getName());
284 * Search for leaf nodes below (or at) the given node
287 * root node to search from
291 public Vector<SequenceNode> findLeaves(SequenceNode nd)
293 Vector<SequenceNode> leaves = new Vector<SequenceNode>();
294 findLeaves(nd, leaves);
299 * Search for leaf nodes.
302 * root node to search from
304 * Vector of leaves to add leaf node objects too.
306 * @return Vector of leaf nodes on binary tree
308 Vector<SequenceNode> findLeaves(SequenceNode nd,
309 Vector<SequenceNode> leaves)
316 if ((nd.left() == null) && (nd.right() == null)) // Interior node
319 leaves.addElement(nd);
326 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
327 * leaves.addElement(node); }
329 findLeaves((SequenceNode) nd.left(), leaves);
330 findLeaves((SequenceNode) nd.right(), leaves);
337 * printNode is mainly for debugging purposes.
342 void printNode(SequenceNode nd)
349 if ((nd.left() == null) && (nd.right() == null))
351 System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
352 System.out.println("Dist " + nd.dist);
353 System.out.println("Boot " + nd.getBootstrap());
357 System.out.println("Dist " + nd.dist);
358 printNode((SequenceNode) nd.left());
359 printNode((SequenceNode) nd.right());
366 * @return DOCUMENT ME!
368 public double getMaxHeight()
374 * Makes a list of groups, where each group is represented by a node whose
375 * height (distance from the root node), as a fraction of the height of the
376 * whole tree, is greater than the given threshold. This corresponds to
377 * selecting the nodes immediately to the right of a vertical line
378 * partitioning the tree (if the tree is drawn with root to the left). Each
379 * such node represents a group that contains all of the sequences linked to
380 * the child leaf nodes.
385 public List<SequenceNode> groupNodes(float threshold)
387 List<SequenceNode> groups = new ArrayList<SequenceNode>();
388 _groupNodes(groups, getTopNode(), threshold);
392 protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
400 if ((nd.height / maxheight) > threshold)
406 _groupNodes(groups, (SequenceNode) nd.left(), threshold);
407 _groupNodes(groups, (SequenceNode) nd.right(), threshold);
417 * @return DOCUMENT ME!
419 public double findHeight(SequenceNode nd)
426 if ((nd.left() == null) && (nd.right() == null))
428 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
430 if (nd.height > maxheight)
441 if (nd.parent() != null)
443 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
448 nd.height = (float) 0.0;
451 maxheight = findHeight((SequenceNode) (nd.left()));
452 maxheight = findHeight((SequenceNode) (nd.right()));
464 void printN(SequenceNode nd)
471 if ((nd.left() != null) && (nd.right() != null))
473 printN((SequenceNode) nd.left());
474 printN((SequenceNode) nd.right());
478 System.out.println(" name = " + ((SequenceI) nd.element()).getName());
481 System.out.println(" dist = " + nd.dist + " " + nd.count + " "
491 public void reCount(SequenceNode nd)
495 // _lylimit = this.node.size();
499 // private long _lycount = 0, _lylimit = 0;
507 void _reCount(SequenceNode nd)
509 // if (_lycount<_lylimit)
511 // System.err.println("Warning: depth of _recount greater than number of nodes.");
519 if ((nd.left() != null) && (nd.right() != null))
522 _reCount((SequenceNode) nd.left());
523 _reCount((SequenceNode) nd.right());
525 SequenceNode l = (SequenceNode) nd.left();
526 SequenceNode r = (SequenceNode) nd.right();
528 nd.count = l.count + r.count;
529 nd.ycount = (l.ycount + r.ycount) / 2;
534 nd.ycount = ycount++;
545 public void swapNodes(SequenceNode nd)
552 SequenceNode tmp = (SequenceNode) nd.left();
554 nd.setLeft(nd.right());
566 void changeDirection(SequenceNode nd, SequenceNode dir)
573 if (nd.parent() != top)
575 changeDirection((SequenceNode) nd.parent(), nd);
577 SequenceNode tmp = (SequenceNode) nd.parent();
579 if (dir == nd.left())
584 else if (dir == nd.right())
592 if (dir == nd.left())
594 nd.setParent(nd.left());
596 if (top.left() == nd)
598 nd.setRight(top.right());
602 nd.setRight(top.left());
607 nd.setParent(nd.right());
609 if (top.left() == nd)
611 nd.setLeft(top.right());
615 nd.setLeft(top.left());
624 * @return DOCUMENT ME!
626 public SequenceNode getTopNode()
633 * @return true if tree has real distances
635 public boolean hasDistances()
642 * @return true if tree has real bootstrap values
644 public boolean hasBootstrap()
649 public boolean hasRootDistance()
651 return hasRootDistance;
655 * apply the given transform to all the nodes in the tree.
657 * @param nodeTransformI
659 public void applyToNodes(NodeTransformI nodeTransformI)
661 for (Enumeration<SequenceNode> nodes = node.elements(); nodes
662 .hasMoreElements(); nodeTransformI.transform(nodes
669 public AlignmentView getOriginalData()