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