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    * Returns original alignment data used for calculation - or null where not
 460    * available.
 461    *
 462    * @return null or cut'n'pasteable alignment
 463    */
 464   public String printOriginalSequenceData(char gapChar)
 465   {
 466     if (seqData == null)
 467     {
 468       return null;
 469     }
 470
 471     StringBuffer sb = new StringBuffer();
 472     String[] seqdatas = seqData.getSequenceStrings(gapChar);
 473     for (int i = 0; i < seqdatas.length; i++)
 474     {
 475       sb.append(new jalview.util.Format("%-" + 15 + "s").form(sequences[i]
 476               .getName()));
 477       sb.append(" " + seqdatas[i] + "\n");
 478     }
 479     return sb.toString();
 480   }
 481
 482   /**
 483    * DOCUMENT ME!
 484    *
 485    * @param nd
 486    *          DOCUMENT ME!
 487    */
 488   void printN(SequenceNode nd)
 489   {
 490     if (nd == null)
 491     {
 492       return;
 493     }
 494
 495     if ((nd.left() != null) && (nd.right() != null))
 496     {
 497       printN((SequenceNode) nd.left());
 498       printN((SequenceNode) nd.right());
 499     }
 500     else
 501     {
 502       System.out.println(" name = " + ((SequenceI) nd.element()).getName());
 503     }
 504
 505     System.out.println(" dist = " + nd.dist + " " + nd.count + " "
 506             + nd.height);
 507   }
 508
 509   /**
 510    * DOCUMENT ME!
 511    *
 512    * @param nd
 513    *          DOCUMENT ME!
 514    */
 515   public void reCount(SequenceNode nd)
 516   {
 517     ycount = 0;
 518     // _lycount = 0;
 519     // _lylimit = this.node.size();
 520     _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   void _reCount(SequenceNode nd)
 532   {
 533     // if (_lycount<_lylimit)
 534     // {
 535     // System.err.println("Warning: depth of _recount greater than number of nodes.");
 536     // }
 537     if (nd == null)
 538     {
 539       return;
 540     }
 541     // _lycount++;
 542
 543     if ((nd.left() != null) && (nd.right() != null))
 544     {
 545
 546       _reCount((SequenceNode) nd.left());
 547       _reCount((SequenceNode) nd.right());
 548
 549       SequenceNode l = (SequenceNode) nd.left();
 550       SequenceNode r = (SequenceNode) nd.right();
 551
 552       nd.count = l.count + r.count;
 553       nd.ycount = (l.ycount + r.ycount) / 2;
 554     }
 555     else
 556     {
 557       nd.count = 1;
 558       nd.ycount = ycount++;
 559     }
 560     // _lycount--;
 561   }
 562
 563   /**
 564    * DOCUMENT ME!
 565    *
 566    * @param nd
 567    *          DOCUMENT ME!
 568    */
 569   public void swapNodes(SequenceNode nd)
 570   {
 571     if (nd == null)
 572     {
 573       return;
 574     }
 575
 576     SequenceNode tmp = (SequenceNode) nd.left();
 577
 578     nd.setLeft(nd.right());
 579     nd.setRight(tmp);
 580   }
 581
 582   /**
 583    * DOCUMENT ME!
 584    *
 585    * @param nd
 586    *          DOCUMENT ME!
 587    * @param dir
 588    *          DOCUMENT ME!
 589    */
 590   void changeDirection(SequenceNode nd, SequenceNode dir)
 591   {
 592     if (nd == null)
 593     {
 594       return;
 595     }
 596
 597     if (nd.parent() != top)
 598     {
 599       changeDirection((SequenceNode) nd.parent(), nd);
 600
 601       SequenceNode tmp = (SequenceNode) nd.parent();
 602
 603       if (dir == nd.left())
 604       {
 605         nd.setParent(dir);
 606         nd.setLeft(tmp);
 607       }
 608       else if (dir == nd.right())
 609       {
 610         nd.setParent(dir);
 611         nd.setRight(tmp);
 612       }
 613     }
 614     else
 615     {
 616       if (dir == nd.left())
 617       {
 618         nd.setParent(nd.left());
 619
 620         if (top.left() == nd)
 621         {
 622           nd.setRight(top.right());
 623         }
 624         else
 625         {
 626           nd.setRight(top.left());
 627         }
 628       }
 629       else
 630       {
 631         nd.setParent(nd.right());
 632
 633         if (top.left() == nd)
 634         {
 635           nd.setLeft(top.right());
 636         }
 637         else
 638         {
 639           nd.setLeft(top.left());
 640         }
 641       }
 642     }
 643   }
 644
 645   /**
 646    * DOCUMENT ME!
 647    *
 648    * @return DOCUMENT ME!
 649    */
 650   public SequenceNode getTopNode()
 651   {
 652     return top;
 653   }
 654
 655   /**
 656    *
 657    * @return true if tree has real distances
 658    */
 659   public boolean hasDistances()
 660   {
 661     return hasDistances;
 662   }
 663
 664   /**
 665    *
 666    * @return true if tree has real bootstrap values
 667    */
 668   public boolean hasBootstrap()
 669   {
 670     return hasBootstrap;
 671   }
 672
 673   public boolean hasRootDistance()
 674   {
 675     return hasRootDistance;
 676   }
 677
 678   /**
 679    * apply the given transform to all the nodes in the tree.
 680    *
 681    * @param nodeTransformI
 682    */
 683   public void applyToNodes(NodeTransformI nodeTransformI)
 684   {
 685     for (Enumeration<SequenceNode> nodes = node.elements(); nodes
 686             .hasMoreElements(); nodeTransformI.transform(nodes
 687             .nextElement()))
 688     {
 689       ;
 690     }
 691   }
 692
 693   public AlignmentView getOriginalData()
 694   {
 695     return seqData;
 696   }
 697 }