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