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 public 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 original alignment data represented by Cigar strings
80 public TreeModel(SequenceI[] seqs, AlignmentView odata, NewickFile treefile)
87 * Creates a new TreeModel object from a tree from an external source
90 * SequenceI which should be associated with leafs of treefile
94 public TreeModel(SequenceI[] seqs, NewickFile treefile)
96 this(seqs, treefile.getTree(), treefile.HasDistances(), treefile
97 .HasBootstrap(), treefile.HasRootDistance());
99 associateLeavesToSequences(seqs);
103 * Constructor given a calculated tree
107 public TreeModel(TreeBuilder tree)
109 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(), tree
110 .hasBootstrap(), tree.hasRootDistance());
114 * Constructor given sequences, root node and tree property flags
122 public TreeModel(SequenceI[] seqs, SequenceNode root, boolean hasDist,
123 boolean hasBoot, boolean hasRootDist)
125 this.sequences = seqs;
128 hasDistances = hasDist;
129 hasBootstrap = hasBoot;
130 hasRootDistance = hasRootDist;
132 maxheight = findHeight(top);
138 public void associateLeavesToSequences(SequenceI[] seqs)
140 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
142 Vector<SequenceNode> leaves = findLeaves(top);
145 int namesleft = seqs.length;
150 Vector<SequenceI> one2many = new Vector<SequenceI>();
151 // int countOne2Many = 0;
152 while (i < leaves.size())
154 j = leaves.elementAt(i++);
155 realnam = j.getName();
160 nam = algnIds.findIdMatch(realnam);
166 if (one2many.contains(nam))
169 // if (jalview.bin.Cache.log.isDebugEnabled())
170 // jalview.bin.Cache.log.debug("One 2 many relationship for
175 one2many.addElement(nam);
181 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
182 j.setPlaceholder(true);
185 // if (jalview.bin.Cache.log.isDebugEnabled() && countOne2Many>0) {
186 // jalview.bin.Cache.log.debug("There were "+countOne2Many+" alignment
187 // sequence ids (out of "+one2many.size()+" unique ids) linked to two or
194 * Generate a string representation of the Tree
196 * @return Newick File with all tree data available
198 public String print()
200 NewickFile fout = new NewickFile(getTopNode());
202 return fout.print(hasBootstrap(), hasDistances(),
203 hasRootDistance()); // output all data available for tree
208 * used when the alignment associated to a tree has changed.
211 * Sequence set to be associated with tree nodes
213 public void updatePlaceHolders(List<SequenceI> list)
215 Vector<SequenceNode> leaves = findLeaves(top);
217 int sz = leaves.size();
218 SequenceIdMatcher seqmatcher = null;
223 SequenceNode leaf = leaves.elementAt(i++);
225 if (list.contains(leaf.element()))
227 leaf.setPlaceholder(false);
231 if (seqmatcher == null)
233 // Only create this the first time we need it
234 SequenceI[] seqs = new SequenceI[list.size()];
236 for (int j = 0; j < seqs.length; j++)
238 seqs[j] = list.get(j);
241 seqmatcher = new SequenceIdMatcher(seqs);
244 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
248 if (!leaf.isPlaceholder())
250 // remapping the node to a new sequenceI - should remove any refs to
252 // TODO - make many sequenceI to one leaf mappings possible!
255 leaf.setPlaceholder(false);
256 leaf.setElement(nam);
260 if (!leaf.isPlaceholder())
262 // Construct a new placeholder sequence object for this leaf
263 leaf.setElement(new Sequence(leaf.getName(),
264 "THISISAPLACEHLDER"));
266 leaf.setPlaceholder(true);
274 * rename any nodes according to their associated sequence. This will modify
275 * the tree's metadata! (ie the original NewickFile or newly generated
276 * BinaryTree's label data)
278 public void renameAssociatedNodes()
280 applyToNodes(new NodeTransformI()
284 public void transform(BinaryNode nd)
286 Object el = nd.element();
287 if (el != null && el instanceof SequenceI)
289 nd.setName(((SequenceI) el).getName());
296 * Search for leaf nodes below (or at) the given node
299 * root node to search from
303 public Vector<SequenceNode> findLeaves(SequenceNode nd)
305 Vector<SequenceNode> leaves = new Vector<SequenceNode>();
306 findLeaves(nd, leaves);
311 * Search for leaf nodes.
314 * root node to search from
316 * Vector of leaves to add leaf node objects too.
318 * @return Vector of leaf nodes on binary tree
320 Vector<SequenceNode> findLeaves(SequenceNode nd,
321 Vector<SequenceNode> leaves)
328 if ((nd.left() == null) && (nd.right() == null)) // Interior node
331 leaves.addElement(nd);
338 * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
339 * leaves.addElement(node); }
341 findLeaves((SequenceNode) nd.left(), leaves);
342 findLeaves((SequenceNode) nd.right(), leaves);
349 * printNode is mainly for debugging purposes.
354 void printNode(SequenceNode nd)
361 if ((nd.left() == null) && (nd.right() == null))
363 System.out.println("Leaf = " + ((SequenceI) nd.element()).getName());
364 System.out.println("Dist " + nd.dist);
365 System.out.println("Boot " + nd.getBootstrap());
369 System.out.println("Dist " + nd.dist);
370 printNode((SequenceNode) nd.left());
371 printNode((SequenceNode) nd.right());
378 * @return DOCUMENT ME!
380 public double getMaxHeight()
386 * Makes a list of groups, where each group is represented by a node whose
387 * height (distance from the root node), as a fraction of the height of the
388 * whole tree, is greater than the given threshold. This corresponds to
389 * selecting the nodes immediately to the right of a vertical line
390 * partitioning the tree (if the tree is drawn with root to the left). Each
391 * such node represents a group that contains all of the sequences linked to
392 * the child leaf nodes.
397 public List<SequenceNode> groupNodes(float threshold)
399 List<SequenceNode> groups = new ArrayList<SequenceNode>();
400 _groupNodes(groups, getTopNode(), threshold);
404 protected void _groupNodes(List<SequenceNode> groups, SequenceNode nd,
412 if ((nd.height / maxheight) > threshold)
418 _groupNodes(groups, (SequenceNode) nd.left(), threshold);
419 _groupNodes(groups, (SequenceNode) nd.right(), threshold);
429 * @return DOCUMENT ME!
431 public double findHeight(SequenceNode nd)
438 if ((nd.left() == null) && (nd.right() == null))
440 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
442 if (nd.height > maxheight)
453 if (nd.parent() != null)
455 nd.height = ((SequenceNode) nd.parent()).height + nd.dist;
460 nd.height = (float) 0.0;
463 maxheight = findHeight((SequenceNode) (nd.left()));
464 maxheight = findHeight((SequenceNode) (nd.right()));
472 * @return true if original sequence data can be recovered
474 public boolean hasOriginalSequenceData()
476 return seqData != null;
480 * Returns original alignment data used for calculation - or null where not
483 * @return null or cut'n'pasteable alignment
485 public String printOriginalSequenceData(char gapChar)
492 StringBuffer sb = new StringBuffer();
493 String[] seqdatas = seqData.getSequenceStrings(gapChar);
494 for (int i = 0; i < seqdatas.length; i++)
496 sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequences[i]
498 sb.append(" " + seqdatas[i] + "\n");
500 return sb.toString();
509 void printN(SequenceNode nd)
516 if ((nd.left() != null) && (nd.right() != null))
518 printN((SequenceNode) nd.left());
519 printN((SequenceNode) nd.right());
523 System.out.println(" name = " + ((SequenceI) nd.element()).getName());
526 System.out.println(" dist = " + nd.dist + " " + nd.count + " "
536 public void reCount(SequenceNode nd)
540 // _lylimit = this.node.size();
544 // private long _lycount = 0, _lylimit = 0;
552 void _reCount(SequenceNode nd)
554 // if (_lycount<_lylimit)
556 // System.err.println("Warning: depth of _recount greater than number of nodes.");
564 if ((nd.left() != null) && (nd.right() != null))
567 _reCount((SequenceNode) nd.left());
568 _reCount((SequenceNode) nd.right());
570 SequenceNode l = (SequenceNode) nd.left();
571 SequenceNode r = (SequenceNode) nd.right();
573 nd.count = l.count + r.count;
574 nd.ycount = (l.ycount + r.ycount) / 2;
579 nd.ycount = ycount++;
590 public void swapNodes(SequenceNode nd)
597 SequenceNode tmp = (SequenceNode) nd.left();
599 nd.setLeft(nd.right());
611 void changeDirection(SequenceNode nd, SequenceNode dir)
618 if (nd.parent() != top)
620 changeDirection((SequenceNode) nd.parent(), nd);
622 SequenceNode tmp = (SequenceNode) nd.parent();
624 if (dir == nd.left())
629 else if (dir == nd.right())
637 if (dir == nd.left())
639 nd.setParent(nd.left());
641 if (top.left() == nd)
643 nd.setRight(top.right());
647 nd.setRight(top.left());
652 nd.setParent(nd.right());
654 if (top.left() == nd)
656 nd.setLeft(top.right());
660 nd.setLeft(top.left());
669 * @return DOCUMENT ME!
671 public SequenceNode getTopNode()
678 * @return true if tree has real distances
680 public boolean hasDistances()
687 * @return true if tree has real bootstrap values
689 public boolean hasBootstrap()
694 public boolean hasRootDistance()
696 return hasRootDistance;
700 * apply the given transform to all the nodes in the tree.
702 * @param nodeTransformI
704 public void applyToNodes(NodeTransformI nodeTransformI)
706 for (Enumeration<SequenceNode> nodes = node.elements(); nodes
707 .hasMoreElements(); nodeTransformI.transform(nodes