Clover icon

Coverage Report

  1. Project Clover database Mon Nov 18 2024 09:56:54 GMT
  2. Package jalview.analysis

File TreeModel.java

 

Coverage histogram

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

Code metrics

72
156
26
1
699
398
68
0.44
6
26
2.62

Classes

Class Line # Actions
TreeModel 41 156 68
0.4212598542.1%
 

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