Clover icon

Coverage Report

  1. Project Clover database Thu Nov 7 2024 13:01:17 GMT
  2. Package jalview.analysis

File TreeModel.java

 

Coverage histogram

../../img/srcFileCovDistChart5.png
43% of files have more coverage

Code metrics

70
155
26
1
683
391
67
0.43
5.96
26
2.58

Classes

Class Line # Actions
TreeModel 40 155 67
0.418326741.8%
 

Contributing tests

This file is covered by 11 tests. .

Source view

1    /*
2    * Jalview - A Sequence Alignment Editor and Viewer ($$Version-Rel$$)
3    * Copyright (C) $$Year-Rel$$ The Jalview Authors
4    *
5    * This file is part of Jalview.
6    *
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.
11    *
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.
16    *
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.
20    */
21    package jalview.analysis;
22   
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;
30   
31    import java.util.ArrayList;
32    import java.util.Enumeration;
33    import java.util.List;
34    import java.util.Vector;
35   
36    /**
37    * A model of a tree, either computed by Jalview or loaded from a file or other
38    * resource or service
39    */
 
40    public class TreeModel
41    {
42   
43    SequenceI[] sequences;
44   
45    /*
46    * SequenceData is a string representation of what the user
47    * sees. The display may contain hidden columns.
48    */
49    private AlignmentView seqData;
50   
51    int noseqs;
52   
53    BinaryNode top;
54   
55    double maxDistValue;
56   
57    double maxheight;
58   
59    int ycount;
60   
61    Vector<BinaryNode> node;
62   
63    boolean hasDistances = true; // normal case for jalview trees
64   
65    boolean hasBootstrap = false; // normal case for jalview trees
66   
67    private boolean hasRootDistance = true;
68   
69    /**
70    * Create a new TreeModel object with leaves associated with sequences in
71    * seqs, and (optionally) original alignment data represented by Cigar strings
72    *
73    * @param seqs
74    * SequenceI[]
75    * @param odata
76    * Cigar[]
77    * @param treefile
78    * NewickFile
79    */
 
80  20 toggle public TreeModel(SequenceI[] seqs, AlignmentView odata,
81    NewickFile treefile)
82    {
83  20 this(seqs, treefile.getTree(), treefile.HasDistances(),
84    treefile.HasBootstrap(), treefile.HasRootDistance());
85  20 seqData = odata;
86   
87  20 associateLeavesToSequences(seqs);
88    }
89   
90    /**
91    * Constructor given a calculated tree
92    *
93    * @param tree
94    */
 
95  0 toggle public TreeModel(TreeBuilder tree)
96    {
97  0 this(tree.getSequences(), tree.getTopNode(), tree.hasDistances(),
98    tree.hasBootstrap(), tree.hasRootDistance());
99  0 seqData = tree.getOriginalData();
100    }
101   
102    /**
103    * Constructor given sequences, root node and tree property flags
104    *
105    * @param seqs
106    * @param root
107    * @param hasDist
108    * @param hasBoot
109    * @param hasRootDist
110    */
 
111  20 toggle public TreeModel(SequenceI[] seqs, BinaryNode root, boolean hasDist,
112    boolean hasBoot, boolean hasRootDist)
113    {
114  20 this.sequences = seqs;
115  20 top = root;
116   
117  20 hasDistances = hasDist;
118  20 hasBootstrap = hasBoot;
119  20 hasRootDistance = hasRootDist;
120   
121  20 maxheight = findHeight(top);
122    }
123   
124    /**
125    * @param seqs
126    */
 
127  20 toggle public void associateLeavesToSequences(SequenceI[] seqs)
128    {
129  20 SequenceIdMatcher algnIds = new SequenceIdMatcher(seqs);
130   
131  20 Vector<BinaryNode> leaves = findLeaves(top);
132   
133  20 int i = 0;
134  20 int namesleft = seqs.length;
135   
136  20 SequenceNode j;
137  20 SequenceI nam;
138  20 String realnam;
139  20 Vector<SequenceI> one2many = new Vector<SequenceI>();
140    // int countOne2Many = 0;
141  228 while (i < leaves.size())
142    {
143    // TODO - decide if we get rid of the polymorphism here ?
144  208 j = (SequenceNode) leaves.elementAt(i++);
145  208 realnam = j.getName();
146  208 nam = null;
147   
148  208 if (namesleft > -1)
149    {
150  208 nam = algnIds.findIdMatch(realnam);
151    }
152   
153  208 if (nam != null)
154    {
155  170 j.setElement(nam);
156  170 if (one2many.contains(nam))
157    {
158    // countOne2Many++;
159    // if (Cache.isDebugEnabled())
160    // Cache.debug("One 2 many relationship for
161    // "+nam.getName());
162    }
163    else
164    {
165  170 one2many.addElement(nam);
166  170 namesleft--;
167    }
168    }
169    else
170    {
171  38 j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
172  38 j.setPlaceholder(true);
173    }
174    }
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
178    // more leaves.");
179    // }
180    // one2many.clear();
181    }
182   
183    /**
184    * Generate a string representation of the Tree
185    *
186    * @return Newick File with all tree data available
187    */
 
188  4 toggle public String print()
189    {
190  4 NewickFile fout = new NewickFile(getTopNode());
191   
192  4 return fout.print(hasBootstrap(), hasDistances(), hasRootDistance()); // output
193    // all
194    // data
195    // available
196    // for
197    // tree
198    }
199   
200    /**
201    *
202    * used when the alignment associated to a tree has changed.
203    *
204    * @param list
205    * Sequence set to be associated with tree nodes
206    */
 
207  0 toggle public void updatePlaceHolders(List<SequenceI> list)
208    {
209  0 Vector<BinaryNode> leaves = findLeaves(top);
210   
211  0 int sz = leaves.size();
212  0 SequenceIdMatcher seqmatcher = null;
213  0 int i = 0;
214   
215  0 while (i < sz)
216    {
217  0 SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
218   
219  0 if (list.contains(leaf.element()))
220    {
221  0 leaf.setPlaceholder(false);
222    }
223    else
224    {
225  0 if (seqmatcher == null)
226    {
227    // Only create this the first time we need it
228  0 SequenceI[] seqs = new SequenceI[list.size()];
229   
230  0 for (int j = 0; j < seqs.length; j++)
231    {
232  0 seqs[j] = list.get(j);
233    }
234   
235  0 seqmatcher = new SequenceIdMatcher(seqs);
236    }
237   
238  0 SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
239   
240  0 if (nam != null)
241    {
242  0 if (!leaf.isPlaceholder())
243    {
244    // remapping the node to a new sequenceI - should remove any refs to
245    // old one.
246    // TODO - make many sequenceI to one leaf mappings possible!
247    // (JBPNote)
248    }
249  0 leaf.setPlaceholder(false);
250  0 leaf.setElement(nam);
251    }
252    else
253    {
254  0 if (!leaf.isPlaceholder())
255    {
256    // Construct a new placeholder sequence object for this leaf
257  0 leaf.setElement(
258    new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
259    }
260  0 leaf.setPlaceholder(true);
261   
262    }
263    }
264    }
265    }
266   
267    /**
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)
271    */
 
272  0 toggle public void renameAssociatedNodes()
273    {
274  0 applyToNodes(new NodeTransformI()
275    {
276   
 
277  0 toggle @Override
278    public void transform(BinaryNode nd)
279    {
280  0 Object el = nd.element();
281  0 if (el != null && el instanceof SequenceI)
282    {
283  0 nd.setName(((SequenceI) el).getName());
284    }
285    }
286    });
287    }
288   
289    /**
290    * Search for leaf nodes below (or at) the given node
291    *
292    * @param top2
293    * root node to search from
294    *
295    * @return
296    */
 
297  40 toggle public Vector<BinaryNode> findLeaves(BinaryNode top2)
298    {
299  40 Vector<BinaryNode> leaves = new Vector<BinaryNode>();
300  40 findLeaves(top2, leaves);
301  40 return leaves;
302    }
303   
304    /**
305    * Search for leaf nodes.
306    *
307    * @param nd
308    * root node to search from
309    * @param leaves
310    * Vector of leaves to add leaf node objects too.
311    *
312    * @return Vector of leaf nodes on binary tree
313    */
 
314  792 toggle Vector<BinaryNode> findLeaves(BinaryNode nd, Vector<BinaryNode> leaves)
315    {
316  792 if (nd == null)
317    {
318  0 return leaves;
319    }
320   
321  792 if ((nd.left() == null) && (nd.right() == null)) // Interior node
322    // detection
323    {
324  416 leaves.addElement(nd);
325   
326  416 return leaves;
327    }
328    else
329    {
330    /*
331    * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
332    * leaves.addElement(node); }
333    */
334  376 findLeaves(nd.left(), leaves);
335  376 findLeaves(nd.right(), leaves);
336    }
337   
338  376 return leaves;
339    }
340   
341    /**
342    * printNode is mainly for debugging purposes.
343    *
344    * @param nd
345    * SequenceNode
346    */
 
347  0 toggle void printNode(BinaryNode nd)
348    {
349  0 if (nd == null)
350    {
351  0 return;
352    }
353   
354  0 if ((nd.left() == null) && (nd.right() == null))
355    {
356    // TODO FIX FOR COLUMN TREES
357  0 jalview.bin.Console
358    .outPrintln("Leaf = " + ((SequenceI) nd.element()).getName());
359  0 jalview.bin.Console.outPrintln("Dist " + nd.dist);
360  0 jalview.bin.Console.outPrintln("Boot " + nd.getBootstrap());
361    }
362    else
363    {
364  0 jalview.bin.Console.outPrintln("Dist " + nd.dist);
365  0 printNode((BinaryNode) nd.left());
366  0 printNode((BinaryNode) nd.right());
367    }
368    }
369   
370    /**
371    * DOCUMENT ME!
372    *
373    * @return DOCUMENT ME!
374    */
 
375  0 toggle public double getMaxHeight()
376    {
377  0 return maxheight;
378    }
379   
380    /**
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.
388    *
389    * @param threshold
390    * @see #getGroups()
391    */
 
392  0 toggle public List<BinaryNode> groupNodes(float threshold)
393    {
394  0 List<BinaryNode> groups = new ArrayList<BinaryNode>();
395  0 _groupNodes(groups, getTopNode(), threshold);
396  0 return groups;
397    }
398   
 
399  0 toggle protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
400    float threshold)
401    {
402  0 if (nd == null)
403    {
404  0 return;
405    }
406   
407  0 if ((nd.height / maxheight) > threshold)
408    {
409  0 groups.add(nd);
410    }
411    else
412    {
413  0 _groupNodes(groups, nd.left(), threshold);
414  0 _groupNodes(groups, nd.right(), threshold);
415    }
416    }
417   
418    /**
419    * DOCUMENT ME!
420    *
421    * @param nd
422    * DOCUMENT ME!
423    *
424    * @return DOCUMENT ME!
425    */
 
426  1048 toggle public double findHeight(BinaryNode nd)
427    {
428  1048 if (nd == null)
429    {
430  0 return maxheight;
431    }
432   
433  1048 if ((nd.left() == null) && (nd.right() == null))
434    {
435  548 nd.height = nd.parent().height + nd.dist;
436   
437  548 if (nd.height > maxheight)
438    {
439  64 return nd.height;
440    }
441    else
442    {
443  484 return maxheight;
444    }
445    }
446    else
447    {
448  500 if (nd.parent() != null)
449    {
450  452 nd.height = nd.parent().height + nd.dist;
451    }
452    else
453    {
454  48 maxheight = 0;
455  48 nd.height = (float) 0.0;
456    }
457   
458  500 maxheight = findHeight((BinaryNode) (nd.left()));
459  500 maxheight = findHeight((BinaryNode) (nd.right()));
460    }
461   
462  500 return maxheight;
463    }
464   
465    /**
466    * DOCUMENT ME!
467    *
468    * @param nd
469    * DOCUMENT ME!
470    */
 
471  0 toggle void printN(BinaryNode nd)
472    {
473  0 if (nd == null)
474    {
475  0 return;
476    }
477   
478  0 if ((nd.left() != null) && (nd.right() != null))
479    {
480  0 printN((BinaryNode) nd.left());
481  0 printN((BinaryNode) nd.right());
482    }
483    else
484    {
485  0 jalview.bin.Console.outPrintln(
486    " name = " + ((SequenceI) nd.element()).getName());
487    }
488   
489  0 jalview.bin.Console.outPrintln(
490    " dist = " + nd.dist + " " + nd.count + " " + nd.height);
491    }
492   
493    /**
494    * DOCUMENT ME!
495    *
496    * @param nd
497    * DOCUMENT ME!
498    */
 
499  14 toggle public void reCount(BinaryNode nd)
500    {
501  14 ycount = 0;
502    // _lycount = 0;
503    // _lylimit = this.node.size();
504  14 _reCount(nd);
505    }
506   
507    // private long _lycount = 0, _lylimit = 0;
508   
509    /**
510    * DOCUMENT ME!
511    *
512    * @param nd
513    * DOCUMENT ME!
514    */
 
515  326 toggle void _reCount(BinaryNode nd)
516    {
517    // if (_lycount<_lylimit)
518    // {
519    // jalview.bin.Console.errPrintln("Warning: depth of _recount greater than
520    // number of
521    // nodes.");
522    // }
523  326 if (nd == null)
524    {
525  0 return;
526    }
527    // _lycount++;
528   
529  326 if ((nd.left() != null) && (nd.right() != null))
530    {
531   
532  156 _reCount((BinaryNode) nd.left());
533  156 _reCount((BinaryNode) nd.right());
534   
535  156 BinaryNode l = (BinaryNode) nd.left();
536  156 BinaryNode r = (BinaryNode) nd.right();
537   
538  156 nd.count = l.count + r.count;
539  156 nd.ycount = (l.ycount + r.ycount) / 2;
540    }
541    else
542    {
543  170 nd.count = 1;
544  170 nd.ycount = ycount++;
545    }
546    // _lycount--;
547    }
548   
549    /**
550    * DOCUMENT ME!
551    *
552    * @param nd
553    * DOCUMENT ME!
554    */
 
555  0 toggle public void swapNodes(BinaryNode nd)
556    {
557  0 if (nd == null)
558    {
559  0 return;
560    }
561   
562  0 BinaryNode tmp = (BinaryNode) nd.left();
563   
564  0 nd.setLeft(nd.right());
565  0 nd.setRight(tmp);
566    }
567   
568    /**
569    * DOCUMENT ME!
570    *
571    * @param nd
572    * DOCUMENT ME!
573    * @param dir
574    * DOCUMENT ME!
575    */
 
576  0 toggle void changeDirection(BinaryNode nd, BinaryNode dir)
577    {
578  0 if (nd == null)
579    {
580  0 return;
581    }
582   
583  0 if (nd.parent() != top)
584    {
585  0 changeDirection((BinaryNode) nd.parent(), nd);
586   
587  0 BinaryNode tmp = (BinaryNode) nd.parent();
588   
589  0 if (dir == nd.left())
590    {
591  0 nd.setParent(dir);
592  0 nd.setLeft(tmp);
593    }
594  0 else if (dir == nd.right())
595    {
596  0 nd.setParent(dir);
597  0 nd.setRight(tmp);
598    }
599    }
600    else
601    {
602  0 if (dir == nd.left())
603    {
604  0 nd.setParent(nd.left());
605   
606  0 if (top.left() == nd)
607    {
608  0 nd.setRight(top.right());
609    }
610    else
611    {
612  0 nd.setRight(top.left());
613    }
614    }
615    else
616    {
617  0 nd.setParent(nd.right());
618   
619  0 if (top.left() == nd)
620    {
621  0 nd.setLeft(top.right());
622    }
623    else
624    {
625  0 nd.setLeft(top.left());
626    }
627    }
628    }
629    }
630   
631    /**
632    * DOCUMENT ME!
633    *
634    * @return DOCUMENT ME!
635    */
 
636  61 toggle public BinaryNode getTopNode()
637    {
638  61 return top;
639    }
640   
641    /**
642    *
643    * @return true if tree has real distances
644    */
 
645  4 toggle public boolean hasDistances()
646    {
647  4 return hasDistances;
648    }
649   
650    /**
651    *
652    * @return true if tree has real bootstrap values
653    */
 
654  4 toggle public boolean hasBootstrap()
655    {
656  4 return hasBootstrap;
657    }
658   
 
659  4 toggle public boolean hasRootDistance()
660    {
661  4 return hasRootDistance;
662    }
663   
664    /**
665    * apply the given transform to all the nodes in the tree.
666    *
667    * @param nodeTransformI
668    */
 
669  0 toggle public void applyToNodes(NodeTransformI nodeTransformI)
670    {
671  0 for (Enumeration<BinaryNode> nodes = node.elements(); nodes
672    .hasMoreElements(); nodeTransformI
673    .transform(nodes.nextElement()))
674    {
675  0 ;
676    }
677    }
678   
 
679  14 toggle public AlignmentView getOriginalData()
680    {
681  14 return seqData;
682    }
683    }
  • Report generated by OpenClover v 4.4.1 on Thu Nov 7 2024 13:08:41 GMT using coverage data from Thu Nov 7 2024 13:08:28 GMT.
  • OpenClover is free and open-source software.