src/jalview/io/NewickFile.java

   1 /*
   2  * Jalview - A Sequence Alignment Editor and Viewer
   3  * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA
  18  */
  19
  20 // NewickFile.java
  21 // Tree I/O
  22 // http://evolution.genetics.washington.edu/phylip/newick_doc.html
  23 // TODO: Implement Basic NHX tag parsing and preservation
  24 // TODO: http://evolution.genetics.wustl.edu/eddy/forester/NHX.html
  25 // TODO: Extended SequenceNodeI to hold parsed NHX strings
  26 package jalview.io;
  27
  28 import java.io.*;
  29
  30 import jalview.datamodel.*;
  31
  32 /**
  33  * DOCUMENT ME!
  34  *
  35  * @author $author$
  36  * @version $Revision$
  37  */
  38 public class NewickFile
  39     extends FileParse
  40 {
  41   SequenceNode root;
  42   private boolean HasBootstrap = false;
  43   private boolean HasDistances = false;
  44   private boolean RootHasDistance = false;
  45
  46   // File IO Flags
  47   boolean ReplaceUnderscores = false;
  48   boolean printRootInfo = false;
  49   private com.stevesoft.pat.Regex[] NodeSafeName = new com.stevesoft.pat.Regex[]
  50       {
  51       new com.stevesoft.pat.Regex().perlCode("m/[\\[,:'()]/"), // test for requiring quotes
  52       new com.stevesoft.pat.Regex().perlCode("s/'/''/"), // escaping quote characters
  53       new com.stevesoft.pat.Regex().perlCode("s/\\/w/_/") // unqoted whitespace transformation
  54   };
  55   char QuoteChar = '\'';
  56
  57   /**
  58    * Creates a new NewickFile object.
  59    *
  60    * @param inStr DOCUMENT ME!
  61    *
  62    * @throws IOException DOCUMENT ME!
  63    */
  64   public NewickFile(String inStr)
  65       throws IOException
  66   {
  67     super(inStr, "Paste");
  68   }
  69
  70   /**
  71    * Creates a new NewickFile object.
  72    *
  73    * @param inFile DOCUMENT ME!
  74    * @param type DOCUMENT ME!
  75    *
  76    * @throws IOException DOCUMENT ME!
  77    */
  78   public NewickFile(String inFile, String type)
  79       throws IOException
  80   {
  81     super(inFile, type);
  82   }
  83
  84   /**
  85    * Creates a new NewickFile object.
  86    *
  87    * @param newtree DOCUMENT ME!
  88    */
  89   public NewickFile(SequenceNode newtree)
  90   {
  91     root = newtree;
  92   }
  93
  94   /**
  95    * Creates a new NewickFile object.
  96    *
  97    * @param newtree DOCUMENT ME!
  98    * @param bootstrap DOCUMENT ME!
  99    */
 100   public NewickFile(SequenceNode newtree, boolean bootstrap)
 101   {
 102     HasBootstrap = bootstrap;
 103     root = newtree;
 104   }
 105
 106   /**
 107    * Creates a new NewickFile object.
 108    *
 109    * @param newtree DOCUMENT ME!
 110    * @param bootstrap DOCUMENT ME!
 111    * @param distances DOCUMENT ME!
 112    */
 113   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances)
 114   {
 115     root = newtree;
 116     HasBootstrap = bootstrap;
 117     HasDistances = distances;
 118   }
 119
 120   /**
 121    * Creates a new NewickFile object.
 122    *
 123    * @param newtree DOCUMENT ME!
 124    * @param bootstrap DOCUMENT ME!
 125    * @param distances DOCUMENT ME!
 126    * @param rootdistance DOCUMENT ME!
 127    */
 128   public NewickFile(SequenceNode newtree, boolean bootstrap,
 129                     boolean distances, boolean rootdistance)
 130   {
 131     root = newtree;
 132     HasBootstrap = bootstrap;
 133     HasDistances = distances;
 134     RootHasDistance = rootdistance;
 135   }
 136
 137   /**
 138    * DOCUMENT ME!
 139    *
 140    * @param Error DOCUMENT ME!
 141    * @param Er DOCUMENT ME!
 142    * @param r DOCUMENT ME!
 143    * @param p DOCUMENT ME!
 144    * @param s DOCUMENT ME!
 145    *
 146    * @return DOCUMENT ME!
 147    */
 148   private String ErrorStringrange(String Error, String Er, int r, int p,
 149                                   String s)
 150   {
 151     return ( (Error == null) ? "" : Error) + Er + " at position " + p +
 152         " ( " +
 153         s.substring( ( (p - r) < 0) ? 0 : (p - r),
 154                     ( (p + r) > s.length()) ? s.length() : (p + r)) + " )\n";
 155   }
 156
 157   // @tree annotations
 158   // These are set automatically by the reader
 159   public boolean HasBootstrap()
 160   {
 161     return HasBootstrap;
 162   }
 163
 164   /**
 165    * DOCUMENT ME!
 166    *
 167    * @return DOCUMENT ME!
 168    */
 169   public boolean HasDistances()
 170   {
 171     return HasDistances;
 172   }
 173
 174   public boolean HasRootDistance()
 175   {
 176     return RootHasDistance;
 177   }
 178
 179   /**
 180    * parse the filesource as a newick file (new hampshire and/or extended)
 181    *
 182    * @throws IOException with a line number and character position for badly formatted NH strings
 183    */
 184   public void parse()
 185       throws IOException
 186   {
 187     String nf;
 188
 189     { // fill nf with complete tree file
 190
 191       StringBuffer file = new StringBuffer();
 192
 193       while ( (nf = nextLine()) != null)
 194       {
 195         file.append(nf);
 196       }
 197
 198       nf = file.toString();
 199     }
 200
 201     root = new SequenceNode();
 202
 203     SequenceNode realroot = null;
 204     SequenceNode c = root;
 205
 206     int d = -1;
 207     int cp = 0;
 208     //int flen = nf.length();
 209
 210     String Error = null;
 211     String nodename = null;
 212
 213     float DefDistance = (float) 0.001; // @param Default distance for a node - very very small
 214     int DefBootstrap = 0; // @param Default bootstrap for a node
 215
 216     float distance = DefDistance;
 217     int bootstrap = DefBootstrap;
 218
 219     boolean ascending = false; // flag indicating that we are leaving the current node
 220
 221     com.stevesoft.pat.Regex majorsyms = new com.stevesoft.pat.Regex(
 222         "[(\\['),;]");
 223
 224     while (majorsyms.searchFrom(nf, cp) && (Error == null))
 225     {
 226       int fcp = majorsyms.matchedFrom();
 227
 228       switch (nf.charAt(fcp))
 229       {
 230         case '[': // Comment or structured/extended NH format info
 231
 232           com.stevesoft.pat.Regex comment = new com.stevesoft.pat.Regex(
 233               "]");
 234
 235           if (comment.searchFrom(nf, fcp))
 236           {
 237             // Skip the comment field
 238             cp = 1 + comment.matchedFrom();
 239           }
 240           else
 241           {
 242             Error = ErrorStringrange(Error, "Unterminated comment", 3,
 243                                      fcp, nf);
 244           }
 245
 246           ;
 247
 248           break;
 249
 250         case '(':
 251
 252           // ascending should not be set
 253           // New Internal node
 254           if (ascending)
 255           {
 256             Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
 257
 258             continue;
 259           }
 260
 261           ;
 262           d++;
 263
 264           if (c.right() == null)
 265           {
 266             c.setRight(new SequenceNode(null, c, null, DefDistance,
 267                                         DefBootstrap, false));
 268             c = (SequenceNode) c.right();
 269           }
 270           else
 271           {
 272             if (c.left() != null)
 273             {
 274               // Dummy node for polytomy - keeps c.left free for new node
 275               SequenceNode tmpn = new SequenceNode(null, c, null, 0,
 276                   0, true);
 277               tmpn.SetChildren(c.left(), c.right());
 278               c.setRight(tmpn);
 279             }
 280
 281             c.setLeft(new SequenceNode(null, c, null, DefDistance,
 282                                        DefBootstrap, false));
 283             c = (SequenceNode) c.left();
 284           }
 285
 286           if (realroot == null)
 287           {
 288             realroot = c;
 289           }
 290
 291           nodename = null;
 292           distance = DefDistance;
 293           bootstrap = DefBootstrap;
 294           cp = fcp + 1;
 295
 296           break;
 297
 298           // Deal with quoted fields
 299         case '\'':
 300
 301           com.stevesoft.pat.Regex qnodename = new com.stevesoft.pat.Regex(
 302               "([^']|'')+'");
 303
 304           if (qnodename.searchFrom(nf, fcp))
 305           {
 306             int nl = qnodename.stringMatched().length();
 307             nodename = new String(qnodename.stringMatched().substring(0,
 308                 nl - 1));
 309             cp = fcp + nl + 1;
 310           }
 311           else
 312           {
 313             Error = ErrorStringrange(Error,
 314                                      "Unterminated quotes for nodename", 7, fcp,
 315                                      nf);
 316           }
 317
 318           break;
 319
 320         case ';':
 321
 322           if (d != -1)
 323           {
 324             Error = ErrorStringrange(Error,
 325                                      "Wayward semicolon (depth=" + d + ")", 7,
 326                                      fcp, nf);
 327           }
 328
 329           // cp advanced at the end of default
 330         default:
 331
 332           // Parse simpler field strings
 333           String fstring = nf.substring(cp, fcp);
 334           com.stevesoft.pat.Regex uqnodename = new com.stevesoft.pat.Regex(
 335               "\\b([^' :;\\](),]+)");
 336           com.stevesoft.pat.Regex nbootstrap = new com.stevesoft.pat.Regex(
 337               "\\S+([0-9+]+)\\S*:");
 338           com.stevesoft.pat.Regex ndist = new com.stevesoft.pat.Regex(
 339               ":([-0-9Ee.+]+)");
 340
 341           if (uqnodename.search(fstring) &&
 342               ( (uqnodename.matchedFrom(1) == 0) ||
 343                (fstring.charAt(uqnodename.matchedFrom(1) - 1) != ':'))) // JBPNote HACK!
 344           {
 345             if (nodename == null)
 346             {
 347               if (ReplaceUnderscores)
 348               {
 349                 nodename = uqnodename.stringMatched(1).replace('_',
 350                     ' ');
 351               }
 352               else
 353               {
 354                 nodename = uqnodename.stringMatched(1);
 355               }
 356             }
 357             else
 358             {
 359               Error = ErrorStringrange(Error,
 360                                        "File has broken algorithm - overwritten nodename",
 361                                        10, fcp, nf);
 362             }
 363           }
 364
 365           if (nbootstrap.search(fstring) &&
 366               (nbootstrap.matchedFrom(1) > (uqnodename.matchedFrom(1) +
 367                                             uqnodename.stringMatched().length())))
 368           {
 369             try
 370             {
 371               bootstrap = (new Integer(nbootstrap.stringMatched(1))).intValue();
 372               HasBootstrap = true;
 373             }
 374             catch (Exception e)
 375             {
 376               Error = ErrorStringrange(Error,
 377                                        "Can't parse bootstrap value", 4,
 378                                        cp + nbootstrap.matchedFrom(), nf);
 379             }
 380           }
 381
 382           boolean nodehasdistance = false;
 383
 384           if (ndist.search(fstring))
 385           {
 386             try
 387             {
 388               distance = (new Float(ndist.stringMatched(1))).floatValue();
 389               HasDistances = true;
 390               nodehasdistance = true;
 391             }
 392             catch (Exception e)
 393             {
 394               Error = ErrorStringrange(Error,
 395                                        "Can't parse node distance value", 7,
 396                                        cp + ndist.matchedFrom(), nf);
 397             }
 398           }
 399
 400           if (ascending)
 401           {
 402             // Write node info here
 403             c.setName(nodename);
 404             // Trees without distances still need a render distance
 405             c.dist = (HasDistances) ? distance : DefDistance;
 406             // be consistent for internal bootstrap defaults too
 407             c.setBootstrap( (HasBootstrap) ? bootstrap : DefBootstrap);
 408             if (c == realroot)
 409             {
 410               RootHasDistance = nodehasdistance; // JBPNote This is really UGLY!!! Ensure root node gets its given distance
 411             }
 412           }
 413           else
 414           {
 415             // Find a place to put the leaf
 416             SequenceNode newnode = new SequenceNode(null, c, nodename,
 417                 (HasDistances) ? distance : DefDistance,
 418                 (HasBootstrap) ? bootstrap : DefBootstrap, false);
 419
 420             if (c.right() == null)
 421             {
 422               c.setRight(newnode);
 423             }
 424             else
 425             {
 426               if (c.left() == null)
 427               {
 428                 c.setLeft(newnode);
 429               }
 430               else
 431               {
 432                 // Insert a dummy node for polytomy
 433                 // dummy nodes have distances
 434                 SequenceNode newdummy = new SequenceNode(null, c,
 435                     null, (HasDistances ? 0 : DefDistance), 0, true);
 436                 newdummy.SetChildren(c.left(), newnode);
 437                 c.setLeft(newdummy);
 438               }
 439             }
 440           }
 441
 442           if (ascending)
 443           {
 444             // move back up the tree from preceding closure
 445             c = c.AscendTree();
 446
 447             if ( (d > -1) && (c == null))
 448             {
 449               Error = ErrorStringrange(Error,
 450                                        "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
 451                                        7, fcp, nf);
 452             }
 453           }
 454
 455           if (nf.charAt(fcp) == ')')
 456           {
 457             d--;
 458             ascending = true;
 459           }
 460           else
 461           {
 462             if (nf.charAt(fcp) == ',')
 463             {
 464               if (ascending)
 465               {
 466                 ascending = false;
 467               }
 468               else
 469               {
 470                 // Just advance focus, if we need to
 471                 if ( (c.left() != null) && (!c.left().isLeaf()))
 472                 {
 473                   c = (SequenceNode) c.left();
 474                 }
 475               }
 476             }
 477
 478             // else : We do nothing if ';' is encountered.
 479           }
 480
 481           // Reset new node properties to obvious fakes
 482           nodename = null;
 483           distance = DefDistance;
 484           bootstrap = DefBootstrap;
 485
 486           cp = fcp + 1;
 487       }
 488     }
 489
 490     if (Error != null)
 491     {
 492       throw (new IOException("NewickFile: " + Error + "\n"));
 493     }
 494     if (root==null)
 495     {
 496       throw (new IOException("NewickFile: No Tree read in\n"));
 497     }
 498     // THe next line is failing for topali trees - not sure why yet. if (root.right()!=null && root.isDummy())
 499     root = (SequenceNode) root.right().detach(); // remove the imaginary root.
 500
 501     if (!RootHasDistance)
 502     {
 503       root.dist = (HasDistances) ? 0 : DefDistance;
 504     }
 505   }
 506
 507   /**
 508    * DOCUMENT ME!
 509    *
 510    * @return DOCUMENT ME!
 511    */
 512   public SequenceNode getTree()
 513   {
 514     return root;
 515   }
 516
 517   /**
 518    * Generate a newick format tree according to internal flags
 519    * for bootstraps, distances and root distances.
 520    *
 521    * @return new hampshire tree in a single line
 522    */
 523   public String print()
 524   {
 525     synchronized (this)
 526     {
 527       StringBuffer tf = new StringBuffer();
 528       print(tf, root);
 529
 530       return (tf.append(";").toString());
 531     }
 532   }
 533
 534   /**
 535    *
 536    *
 537    * Generate a newick format tree according to internal flags
 538    * for distances and root distances and user specificied writing of
 539    * bootstraps.
 540    * @param withbootstraps controls if bootstrap values are explicitly written.
 541    *
 542    * @return new hampshire tree in a single line
 543    */
 544   public String print(boolean withbootstraps)
 545   {
 546     synchronized (this)
 547     {
 548       boolean boots = this.HasBootstrap;
 549       this.HasBootstrap = withbootstraps;
 550
 551       String rv = print();
 552       this.HasBootstrap = boots;
 553
 554       return rv;
 555     }
 556   }
 557
 558   /**
 559    *
 560    * Generate newick format tree according to internal flags
 561    * for writing root node distances.
 562    *
 563    * @param withbootstraps explicitly write bootstrap values
 564    * @param withdists explicitly write distances
 565    *
 566    * @return new hampshire tree in a single line
 567    */
 568   public String print(boolean withbootstraps, boolean withdists)
 569   {
 570     synchronized (this)
 571     {
 572       boolean dists = this.HasDistances;
 573       this.HasDistances = withdists;
 574
 575       String rv = print(withbootstraps);
 576       this.HasDistances = dists;
 577
 578       return rv;
 579     }
 580   }
 581
 582   /**
 583    * Generate newick format tree according to user specified flags
 584    *
 585    * @param withbootstraps explicitly write bootstrap values
 586    * @param withdists explicitly write distances
 587    * @param printRootInfo explicitly write root distance
 588    *
 589    * @return new hampshire tree in a single line
 590    */
 591   public String print(boolean withbootstraps, boolean withdists,
 592                       boolean printRootInfo)
 593   {
 594     synchronized (this)
 595     {
 596       boolean rootinfo = printRootInfo;
 597       this.printRootInfo = printRootInfo;
 598
 599       String rv = print(withbootstraps, withdists);
 600       this.printRootInfo = rootinfo;
 601
 602       return rv;
 603     }
 604   }
 605
 606   /**
 607    * DOCUMENT ME!
 608    *
 609    * @return DOCUMENT ME!
 610    */
 611   char getQuoteChar()
 612   {
 613     return QuoteChar;
 614   }
 615
 616   /**
 617    * DOCUMENT ME!
 618    *
 619    * @param c DOCUMENT ME!
 620    *
 621    * @return DOCUMENT ME!
 622    */
 623   char setQuoteChar(char c)
 624   {
 625     char old = QuoteChar;
 626     QuoteChar = c;
 627
 628     return old;
 629   }
 630
 631   /**
 632    * DOCUMENT ME!
 633    *
 634    * @param name DOCUMENT ME!
 635    *
 636    * @return DOCUMENT ME!
 637    */
 638   private String nodeName(String name)
 639   {
 640     if (NodeSafeName[0].search(name))
 641     {
 642       return QuoteChar + NodeSafeName[1].replaceAll(name) + QuoteChar;
 643     }
 644     else
 645     {
 646       return NodeSafeName[2].replaceAll(name);
 647     }
 648   }
 649
 650   /**
 651    * DOCUMENT ME!
 652    *
 653    * @param c DOCUMENT ME!
 654    *
 655    * @return DOCUMENT ME!
 656    */
 657   private String printNodeField(SequenceNode c)
 658   {
 659     return ( (c.getName() == null) ? "" : nodeName(c.getName())) +
 660         ( (HasBootstrap)
 661          ? ( (c.getBootstrap() > -1) ? (" " + c.getBootstrap()) : "") : "") +
 662         ( (HasDistances) ? (":" + c.dist) : "");
 663   }
 664
 665   /**
 666    * DOCUMENT ME!
 667    *
 668    * @param root DOCUMENT ME!
 669    *
 670    * @return DOCUMENT ME!
 671    */
 672   private String printRootField(SequenceNode root)
 673   {
 674     return (printRootInfo)
 675         ? ( ( (root.getName() == null) ? "" : nodeName(root.getName())) +
 676            ( (HasBootstrap)
 677             ? ( (root.getBootstrap() > -1) ? (" " + root.getBootstrap()) : "") :
 678             "") +
 679            ( (RootHasDistance) ? (":" + root.dist) : "")) : "";
 680   }
 681
 682   // Non recursive call deals with root node properties
 683   public void print(StringBuffer tf, SequenceNode root)
 684   {
 685     if (root != null)
 686     {
 687       if (root.isLeaf() && printRootInfo)
 688       {
 689         tf.append(printRootField(root));
 690       }
 691       else
 692       {
 693         if (root.isDummy())
 694         {
 695           _print(tf, (SequenceNode) root.right());
 696           _print(tf, (SequenceNode) root.left());
 697         }
 698         else
 699         {
 700           tf.append("(");
 701           _print(tf, (SequenceNode) root.right());
 702
 703           if (root.left() != null)
 704           {
 705             tf.append(",");
 706           }
 707
 708           _print(tf, (SequenceNode) root.left());
 709           tf.append(")" + printRootField(root));
 710         }
 711       }
 712     }
 713   }
 714
 715   // Recursive call for non-root nodes
 716   public void _print(StringBuffer tf, SequenceNode c)
 717   {
 718     if (c != null)
 719     {
 720       if (c.isLeaf())
 721       {
 722         tf.append(printNodeField(c));
 723       }
 724       else
 725       {
 726         if (c.isDummy())
 727         {
 728           _print(tf, (SequenceNode) c.left());
 729           if (c.left() != null)
 730           {
 731             tf.append(",");
 732           }
 733           _print(tf, (SequenceNode) c.right());
 734         }
 735         else
 736         {
 737           tf.append("(");
 738           _print(tf, (SequenceNode) c.right());
 739
 740           if (c.left() != null)
 741           {
 742             tf.append(",");
 743           }
 744
 745           _print(tf, (SequenceNode) c.left());
 746           tf.append(")" + printNodeField(c));
 747         }
 748       }
 749     }
 750   }
 751
 752   // Test
 753   public static void main(String[] args)
 754   {
 755     try
 756     {
 757       if (args == null || args.length != 1)
 758       {
 759         System.err.println(
 760             "Takes one argument - file name of a newick tree file.");
 761         System.exit(0);
 762       }
 763
 764       File fn = new File(args[0]);
 765
 766       StringBuffer newickfile = new StringBuffer();
 767       BufferedReader treefile = new BufferedReader(new FileReader(fn));
 768       String l;
 769
 770       while ( (l = treefile.readLine()) != null)
 771       {
 772         newickfile.append(l);
 773       }
 774
 775       treefile.close();
 776       System.out.println("Read file :\n");
 777
 778       NewickFile trf = new NewickFile(args[0], "File");
 779       trf.parse();
 780       System.out.println("Original file :\n");
 781
 782       com.stevesoft.pat.Regex nonl = new com.stevesoft.pat.Regex("\n+", "");
 783       System.out.println(nonl.replaceAll(newickfile.toString()) + "\n");
 784
 785       System.out.println("Parsed file.\n");
 786       System.out.println("Default output type for original input.\n");
 787       System.out.println(trf.print());
 788       System.out.println("Without bootstraps.\n");
 789       System.out.println(trf.print(false));
 790       System.out.println("Without distances.\n");
 791       System.out.println(trf.print(true, false));
 792       System.out.println("Without bootstraps but with distanecs.\n");
 793       System.out.println(trf.print(false, true));
 794       System.out.println("Without bootstraps or distanecs.\n");
 795       System.out.println(trf.print(false, false));
 796       System.out.println("With bootstraps and with distances.\n");
 797       System.out.println(trf.print(true, true));
 798     }
 799     catch (java.io.IOException e)
 800     {
 801       System.err.println("Exception\n" + e);
 802       e.printStackTrace();
 803     }
 804   }
 805 }