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