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());
101 * Constructor given sequences, root node and tree property flags
109 public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
110 boolean hasBoot, boolean hasRootDist)
112 this.sequences = seqs;
115 hasDistances = hasDist;
116 hasBootstrap = hasBoot;
117 hasRootDistance = hasRootDist;
119 maxheight = findHeight(top);
125 public void associateLeavesToSequences(SequenceI[] seqs)
127 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
129 Vector<SequenceNode> leaves = findLeaves(top);
132 int namesleft = seqs.length;
137 Vector<SequenceI> one2many = new Vector<SequenceI>();
138 // int countOne2Many = 0;
139 while (i < leaves.size())
141 j = leaves.elementAt(i++);
142 realnam = j.getName();
147 nam = algnIds.findIdMatch(realnam);
153 if (one2many.contains(nam))
156 // if (jalview.bin.Cache.log.isDebugEnabled())
157 // jalview.bin.Cache.log.debug("One 2 many relationship for
162 one2many.addElement(nam);
168 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
169 j.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(),
190 hasRootDistance()); // output all data available for tree
195 * used when the alignment associated to a tree has changed.
198 * Sequence set to be associated with tree nodes
200 public void updatePlaceHolders(List<SequenceI> list)
202 Vector<SequenceNode> leaves = findLeaves(top);
204 int sz = leaves.size();
205 SequenceIdMatcher seqmatcher = null;
210 SequenceNode leaf = leaves.elementAt(i++);
212 if (list.contains(leaf.element()))
214 leaf.setPlaceholder(false);
218 if (seqmatcher == null)
220 // Only create this the first time we need it
221 SequenceI[] seqs = new SequenceI[list.size()];
223 for (int j = 0; j < seqs.length; j++)
225 seqs[j] = list.get(j);
228 seqmatcher = new SequenceIdMatcher(seqs);
231 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
235 if (!leaf.isPlaceholder())
237 // remapping the node to a new sequenceI - should remove any refs to
239 // TODO - make many sequenceI to one leaf mappings possible!
242 leaf.setPlaceholder(false);
243 leaf.setElement(nam);
247 if (!leaf.isPlaceholder())
249 // Construct a new placeholder sequence object for this leaf
250 leaf.setElement(new Sequence(leaf.getName(),
251 "THISISAPLACEHLDER"));
253 leaf.setPlaceholder(true);
261 * rename any nodes according to their associated sequence. This will modify
262 * the tree's metadata! (ie the original NewickFile or newly generated
263 * BinaryTree's label data)
265 public void renameAssociatedNodes()
267 applyToNodes(new NodeTransformI()
271 public void transform(BinaryNode nd)
273 Object el = nd.element();
274 if (el != null && el instanceof SequenceI)
276 nd.setName(((SequenceI) el).getName());
283 * Search for leaf nodes below (or at) the given node
286 * root node to search from
290 public Vector<SequenceNode> findLeaves(SequenceNode nd)
292 Vector<SequenceNode> leaves = new Vector<SequenceNode>();
293 findLeaves(nd, leaves);
298 * Search for leaf nodes.
301 * root node to search from
303 * Vector of leaves to add leaf node objects too.
305 * @return Vector of leaf nodes on binary tree
307 Vector<SequenceNode> findLeaves(SequenceNode nd,
308 Vector<SequenceNode> leaves)
315 if ((nd.left() == null) && (nd.right() == null)) // Interior node
318 leaves.addElement(nd);
325 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
326 * leaves.addElement(node); }
328 findLeaves((SequenceNode) nd.left(), leaves);
329 findLeaves((SequenceNode) nd.right(), leaves);
336 * printNode is mainly for debugging purposes.
341 void printNode(SequenceNode nd)
348 if ((nd.left() == null) && (nd.right() == null))
350 System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
351 System.out.println("Dist " + nd.dist);
352 System.out.println("Boot " + nd.getBootstrap());
356 System.out.println("Dist " + nd.dist);
357 printNode((SequenceNode) nd.left());
358 printNode((SequenceNode) nd.right());
365 * @return DOCUMENT ME!
367 public double getMaxHeight()
373 * Makes a list of groups, where each group is represented by a node whose
374 * height (distance from the root node), as a fraction of the height of the
375 * whole tree, is greater than the given threshold. This corresponds to
376 * selecting the nodes immediately to the right of a vertical line
377 * partitioning the tree (if the tree is drawn with root to the left). Each
378 * such node represents a group that contains all of the sequences linked to
379 * the child leaf nodes.
384 public List<SequenceNode> groupNodes(float threshold)
386 List<SequenceNode> groups = new ArrayList<SequenceNode>();
387 _groupNodes(groups, getTopNode(), threshold);
391 protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
399 if ((nd.height / maxheight) > threshold)
405 _groupNodes(groups, (SequenceNode) nd.left(), threshold);
406 _groupNodes(groups, (SequenceNode) nd.right(), threshold);
416 * @return DOCUMENT ME!
418 public double findHeight(SequenceNode nd)
425 if ((nd.left() == null) && (nd.right() == null))
427 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
429 if (nd.height > maxheight)
440 if (nd.parent() != null)
442 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
447 nd.height = (float) 0.0;
450 maxheight = findHeight((SequenceNode) (nd.left()));
451 maxheight = findHeight((SequenceNode) (nd.right()));
458 * Returns original alignment data used for calculation - or null where not
461 * @return null or cut'n'pasteable alignment
463 public String printOriginalSequenceData(char gapChar)
470 StringBuffer sb = new StringBuffer();
471 String[] seqdatas = seqData.getSequenceStrings(gapChar);
472 for (int i = 0; i < seqdatas.length; i++)
474 sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequences[i]
476 sb.append(" " + seqdatas[i] + "\n");
478 return sb.toString();
487 void printN(SequenceNode nd)
494 if ((nd.left() != null) && (nd.right() != null))
496 printN((SequenceNode) nd.left());
497 printN((SequenceNode) nd.right());
501 System.out.println(" name = " + ((SequenceI) nd.element()).getName());
504 System.out.println(" dist = " + nd.dist + " " + nd.count + " "
514 public void reCount(SequenceNode nd)
518 // _lylimit = this.node.size();
522 // private long _lycount = 0, _lylimit = 0;
530 void _reCount(SequenceNode nd)
532 // if (_lycount<_lylimit)
534 // System.err.println("Warning: depth of _recount greater than number of nodes.");
542 if ((nd.left() != null) && (nd.right() != null))
545 _reCount((SequenceNode) nd.left());
546 _reCount((SequenceNode) nd.right());
548 SequenceNode l = (SequenceNode) nd.left();
549 SequenceNode r = (SequenceNode) nd.right();
551 nd.count = l.count + r.count;
552 nd.ycount = (l.ycount + r.ycount) / 2;
557 nd.ycount = ycount++;
568 public void swapNodes(SequenceNode nd)
575 SequenceNode tmp = (SequenceNode) nd.left();
577 nd.setLeft(nd.right());
589 void changeDirection(SequenceNode nd, SequenceNode dir)
596 if (nd.parent() != top)
598 changeDirection((SequenceNode) nd.parent(), nd);
600 SequenceNode tmp = (SequenceNode) nd.parent();
602 if (dir == nd.left())
607 else if (dir == nd.right())
615 if (dir == nd.left())
617 nd.setParent(nd.left());
619 if (top.left() == nd)
621 nd.setRight(top.right());
625 nd.setRight(top.left());
630 nd.setParent(nd.right());
632 if (top.left() == nd)
634 nd.setLeft(top.right());
638 nd.setLeft(top.left());
647 * @return DOCUMENT ME!
649 public SequenceNode getTopNode()
656 * @return true if tree has real distances
658 public boolean hasDistances()
665 * @return true if tree has real bootstrap values
667 public boolean hasBootstrap()
672 public boolean hasRootDistance()
674 return hasRootDistance;
678 * apply the given transform to all the nodes in the tree.
680 * @param nodeTransformI
682 public void applyToNodes(NodeTransformI nodeTransformI)
684 for (Enumeration<SequenceNode> nodes = node.elements(); nodes
685 .hasMoreElements(); nodeTransformI.transform(nodes
692 public AlignmentView getOriginalData()