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   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   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, BinaryNode 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<BinaryNode> leaves = findLeaves(top);
 132
 133     int i = 0;
 134     int namesleft = seqs.length;
 135
 136     SequenceNode j;
 137     SequenceI nam;
 138     String realnam;
 139     Vector<SequenceI> one2many = new Vector<SequenceI>();
 140     // int countOne2Many = 0;
 141     while (i < leaves.size())
 142     {
 143       // TODO - decide if we get rid of the polymorphism here ?
 144       j = (SequenceNode) leaves.elementAt(i++);
 145       realnam = j.getName();
 146       nam = null;
 147
 148       if (namesleft > -1)
 149       {
 150         nam = algnIds.findIdMatch(realnam);
 151       }
 152
 153       if (nam != null)
 154       {
 155         j.setElement(nam);
 156         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           one2many.addElement(nam);
 166           namesleft--;
 167         }
 168       }
 169       else
 170       {
 171         j.setElement(new Sequence(realnam, "THISISAPLACEHLDER"));
 172         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   public String print()
 189   {
 190     NewickFile fout = new NewickFile(getTopNode());
 191
 192     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   public void updatePlaceHolders(List<SequenceI> list)
 208   {
 209     Vector<BinaryNode> leaves = findLeaves(top);
 210
 211     int sz = leaves.size();
 212     SequenceIdMatcher seqmatcher = null;
 213     int i = 0;
 214
 215     while (i < sz)
 216     {
 217       SequenceNode leaf = (SequenceNode) leaves.elementAt(i++);
 218
 219       if (list.contains(leaf.element()))
 220       {
 221         leaf.setPlaceholder(false);
 222       }
 223       else
 224       {
 225         if (seqmatcher == null)
 226         {
 227           // Only create this the first time we need it
 228           SequenceI[] seqs = new SequenceI[list.size()];
 229
 230           for (int j = 0; j < seqs.length; j++)
 231           {
 232             seqs[j] = list.get(j);
 233           }
 234
 235           seqmatcher = new SequenceIdMatcher(seqs);
 236         }
 237
 238         SequenceI nam = seqmatcher.findIdMatch(leaf.getName());
 239
 240         if (nam != null)
 241         {
 242           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           leaf.setPlaceholder(false);
 250           leaf.setElement(nam);
 251         }
 252         else
 253         {
 254           if (!leaf.isPlaceholder())
 255           {
 256             // Construct a new placeholder sequence object for this leaf
 257             leaf.setElement(
 258                     new Sequence(leaf.getName(), "THISISAPLACEHLDER"));
 259           }
 260           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   public void renameAssociatedNodes()
 273   {
 274     applyToNodes(new NodeTransformI()
 275     {
 276
 277       @Override
 278       public void transform(BinaryNode nd)
 279       {
 280         Object el = nd.element();
 281         if (el != null && el instanceof SequenceI)
 282         {
 283           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   public Vector<BinaryNode> findLeaves(BinaryNode top2)
 298   {
 299     Vector<BinaryNode> leaves = new Vector<BinaryNode>();
 300     findLeaves(top2, leaves);
 301     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   Vector<BinaryNode> findLeaves(BinaryNode nd, Vector<BinaryNode> leaves)
 315   {
 316     if (nd == null)
 317     {
 318       return leaves;
 319     }
 320
 321     if ((nd.left() == null) && (nd.right() == null)) // Interior node
 322     // detection
 323     {
 324       leaves.addElement(nd);
 325
 326       return leaves;
 327     }
 328     else
 329     {
 330       /*
 331        * TODO: Identify internal nodes... if (node.isSequenceLabel()) {
 332        * leaves.addElement(node); }
 333        */
 334       findLeaves(nd.left(), leaves);
 335       findLeaves(nd.right(), leaves);
 336     }
 337
 338     return leaves;
 339   }
 340
 341   /**
 342    * printNode is mainly for debugging purposes.
 343    *
 344    * @param nd
 345    *          SequenceNode
 346    */
 347   void printNode(BinaryNode nd)
 348   {
 349     if (nd == null)
 350     {
 351       return;
 352     }
 353
 354     if ((nd.left() == null) && (nd.right() == null))
 355     {
 356       // TODO FIX FOR COLUMN TREES
 357       jalview.bin.Console
 358               .outPrintln("Leaf = " + ((SequenceI) nd.element()).getName());
 359       jalview.bin.Console.outPrintln("Dist " + nd.dist);
 360       jalview.bin.Console.outPrintln("Boot " + nd.getBootstrap());
 361     }
 362     else
 363     {
 364       jalview.bin.Console.outPrintln("Dist " + nd.dist);
 365       printNode((BinaryNode) nd.left());
 366       printNode((BinaryNode) nd.right());
 367     }
 368   }
 369
 370   /**
 371    * DOCUMENT ME!
 372    *
 373    * @return DOCUMENT ME!
 374    */
 375   public double getMaxHeight()
 376   {
 377     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   public List<BinaryNode> groupNodes(float threshold)
 393   {
 394     List<BinaryNode> groups = new ArrayList<BinaryNode>();
 395     _groupNodes(groups, getTopNode(), threshold);
 396     return groups;
 397   }
 398
 399   protected void _groupNodes(List<BinaryNode> groups, BinaryNode nd,
 400           float threshold)
 401   {
 402     if (nd == null)
 403     {
 404       return;
 405     }
 406
 407     if ((nd.height / maxheight) > threshold)
 408     {
 409       groups.add(nd);
 410     }
 411     else
 412     {
 413       _groupNodes(groups, nd.left(), threshold);
 414       _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   public double findHeight(BinaryNode nd)
 427   {
 428     if (nd == null)
 429     {
 430       return maxheight;
 431     }
 432
 433     if ((nd.left() == null) && (nd.right() == null))
 434     {
 435       nd.height = nd.parent().height + nd.dist;
 436
 437       if (nd.height > maxheight)
 438       {
 439         return nd.height;
 440       }
 441       else
 442       {
 443         return maxheight;
 444       }
 445     }
 446     else
 447     {
 448       if (nd.parent() != null)
 449       {
 450         nd.height = nd.parent().height + nd.dist;
 451       }
 452       else
 453       {
 454         maxheight = 0;
 455         nd.height = (float) 0.0;
 456       }
 457
 458       maxheight = findHeight((BinaryNode) (nd.left()));
 459       maxheight = findHeight((BinaryNode) (nd.right()));
 460     }
 461
 462     return maxheight;
 463   }
 464
 465   /**
 466    * DOCUMENT ME!
 467    *
 468    * @param nd
 469    *          DOCUMENT ME!
 470    */
 471   void printN(BinaryNode nd)
 472   {
 473     if (nd == null)
 474     {
 475       return;
 476     }
 477
 478     if ((nd.left() != null) && (nd.right() != null))
 479     {
 480       printN((BinaryNode) nd.left());
 481       printN((BinaryNode) nd.right());
 482     }
 483     else
 484     {
 485       jalview.bin.Console.outPrintln(
 486               " name = " + ((SequenceI) nd.element()).getName());
 487     }
 488
 489     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   public void reCount(BinaryNode nd)
 500   {
 501     ycount = 0;
 502     // _lycount = 0;
 503     // _lylimit = this.node.size();
 504     _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   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     if (nd == null)
 524     {
 525       return;
 526     }
 527     // _lycount++;
 528
 529     if ((nd.left() != null) && (nd.right() != null))
 530     {
 531
 532       _reCount((BinaryNode) nd.left());
 533       _reCount((BinaryNode) nd.right());
 534
 535       BinaryNode l = (BinaryNode) nd.left();
 536       BinaryNode r = (BinaryNode) nd.right();
 537
 538       nd.count = l.count + r.count;
 539       nd.ycount = (l.ycount + r.ycount) / 2;
 540     }
 541     else
 542     {
 543       nd.count = 1;
 544       nd.ycount = ycount++;
 545     }
 546     // _lycount--;
 547   }
 548
 549   /**
 550    * DOCUMENT ME!
 551    *
 552    * @param nd
 553    *          DOCUMENT ME!
 554    */
 555   public void swapNodes(BinaryNode nd)
 556   {
 557     if (nd == null)
 558     {
 559       return;
 560     }
 561
 562     BinaryNode tmp = (BinaryNode) nd.left();
 563
 564     nd.setLeft(nd.right());
 565     nd.setRight(tmp);
 566   }
 567
 568   /**
 569    * DOCUMENT ME!
 570    *
 571    * @param nd
 572    *          DOCUMENT ME!
 573    * @param dir
 574    *          DOCUMENT ME!
 575    */
 576   void changeDirection(BinaryNode nd, BinaryNode dir)
 577   {
 578     if (nd == null)
 579     {
 580       return;
 581     }
 582
 583     if (nd.parent() != top)
 584     {
 585       changeDirection((BinaryNode) nd.parent(), nd);
 586
 587       BinaryNode tmp = (BinaryNode) nd.parent();
 588
 589       if (dir == nd.left())
 590       {
 591         nd.setParent(dir);
 592         nd.setLeft(tmp);
 593       }
 594       else if (dir == nd.right())
 595       {
 596         nd.setParent(dir);
 597         nd.setRight(tmp);
 598       }
 599     }
 600     else
 601     {
 602       if (dir == nd.left())
 603       {
 604         nd.setParent(nd.left());
 605
 606         if (top.left() == nd)
 607         {
 608           nd.setRight(top.right());
 609         }
 610         else
 611         {
 612           nd.setRight(top.left());
 613         }
 614       }
 615       else
 616       {
 617         nd.setParent(nd.right());
 618
 619         if (top.left() == nd)
 620         {
 621           nd.setLeft(top.right());
 622         }
 623         else
 624         {
 625           nd.setLeft(top.left());
 626         }
 627       }
 628     }
 629   }
 630
 631   /**
 632    * DOCUMENT ME!
 633    *
 634    * @return DOCUMENT ME!
 635    */
 636   public BinaryNode getTopNode()
 637   {
 638     return top;
 639   }
 640
 641   /**
 642    *
 643    * @return true if tree has real distances
 644    */
 645   public boolean hasDistances()
 646   {
 647     return hasDistances;
 648   }
 649
 650   /**
 651    *
 652    * @return true if tree has real bootstrap values
 653    */
 654   public boolean hasBootstrap()
 655   {
 656     return hasBootstrap;
 657   }
 658
 659   public boolean hasRootDistance()
 660   {
 661     return hasRootDistance;
 662   }
 663
 664   /**
 665    * apply the given transform to all the nodes in the tree.
 666    *
 667    * @param nodeTransformI
 668    */
 669   public void applyToNodes(NodeTransformI nodeTransformI)
 670   {
 671     for (Enumeration<BinaryNode> nodes = node.elements(); nodes
 672             .hasMoreElements(); nodeTransformI
 673                     .transform(nodes.nextElement()))
 674     {
 675       ;
 676     }
 677   }
 678
 679   public AlignmentView getOriginalData()
 680   {
 681     return seqData;
 682   }
 683 }