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  * Parse a new hanpshire style tree
  34  * Caveats: NHX files are NOT supported and the tree distances and topology are unreliable when they are parsed.
  35  * @author Jim Procter
  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       char schar;
 228       switch (schar=nf.charAt(fcp))
 229       {
 230         case '(':
 231
 232           // ascending should not be set
 233           // New Internal node
 234           if (ascending)
 235           {
 236             Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
 237
 238             continue;
 239           }
 240
 241           ;
 242           d++;
 243
 244           if (c.right() == null)
 245           {
 246             c.setRight(new SequenceNode(null, c, null, DefDistance,
 247                                         DefBootstrap, false));
 248             c = (SequenceNode) c.right();
 249           }
 250           else
 251           {
 252             if (c.left() != null)
 253             {
 254               // Dummy node for polytomy - keeps c.left free for new node
 255               SequenceNode tmpn = new SequenceNode(null, c, null, 0,
 256                   0, true);
 257               tmpn.SetChildren(c.left(), c.right());
 258               c.setRight(tmpn);
 259             }
 260
 261             c.setLeft(new SequenceNode(null, c, null, DefDistance,
 262                                        DefBootstrap, false));
 263             c = (SequenceNode) c.left();
 264           }
 265
 266           if (realroot == null)
 267           {
 268             realroot = c;
 269           }
 270
 271           nodename = null;
 272           distance = DefDistance;
 273           bootstrap = DefBootstrap;
 274           cp = fcp + 1;
 275
 276           break;
 277
 278           // Deal with quoted fields
 279         case '\'':
 280
 281           com.stevesoft.pat.Regex qnodename = new com.stevesoft.pat.Regex(
 282               "([^']|'')+'");
 283
 284           if (qnodename.searchFrom(nf, fcp))
 285           {
 286             int nl = qnodename.stringMatched().length();
 287             nodename = new String(qnodename.stringMatched().substring(0,
 288                 nl - 1));
 289             cp = fcp + nl + 1;
 290           }
 291           else
 292           {
 293             Error = ErrorStringrange(Error,
 294                                      "Unterminated quotes for nodename", 7, fcp,
 295                                      nf);
 296           }
 297
 298           break;
 299
 300         default:
 301           if (schar==';')
 302           {
 303             if (d != -1)
 304             {
 305               Error = ErrorStringrange(Error,
 306                                      "Wayward semicolon (depth=" + d + ")", 7,
 307                                      fcp, nf);
 308             }
 309             // cp advanced at the end of default
 310           }
 311           int nextcp=0;
 312           if (schar == '[')
 313           {
 314             // node string contains Comment or structured/extended NH format info
 315             /* if ((fcp-cp>1 && nf.substring(cp,fcp).trim().length()>1))
 316               {
 317                 // will process in remains System.err.println("skipped text: '"+nf.substring(cp,fcp)+"'");
 318               }
 319              */
 320             // verify termination.
 321             com.stevesoft.pat.Regex comment = new com.stevesoft.pat.Regex(
 322               "]");
 323             if (comment.searchFrom(nf, fcp))
 324             {
 325               // Skip the comment field
 326               nextcp=comment.matchedFrom()+1;
 327               warningMessage = "Tree file contained comments which may confuse input algorithm.";
 328               // Skip the comment field
 329               // should advance fcp too here
 330               // fcp = nextcp+1;
 331               // schar = nf.charAt(nextcp+1);
 332
 333               // cp advanced at the end of default to nextcp
 334             }
 335             else
 336             {
 337               Error = ErrorStringrange(Error, "Unterminated comment", 3,
 338                                      fcp, nf);
 339             }
 340
 341             ;
 342           }
 343           // Parse simpler field strings
 344           String fstring = nf.substring(cp, fcp);
 345           com.stevesoft.pat.Regex uqnodename = new com.stevesoft.pat.Regex(
 346               "\\b([^' :;\\](),]+)");
 347           com.stevesoft.pat.Regex nbootstrap = new com.stevesoft.pat.Regex(
 348               "\\S+([0-9+]+)\\S*:");
 349           com.stevesoft.pat.Regex ndist = new com.stevesoft.pat.Regex(
 350               ":([-0-9Ee.+]+)");
 351
 352           if (uqnodename.search(fstring) &&
 353               ( (uqnodename.matchedFrom(1) == 0) ||
 354                (fstring.charAt(uqnodename.matchedFrom(1) - 1) != ':'))) // JBPNote HACK!
 355           {
 356             if (nodename == null)
 357             {
 358               if (ReplaceUnderscores)
 359               {
 360                 nodename = uqnodename.stringMatched(1).replace('_',
 361                     ' ');
 362               }
 363               else
 364               {
 365                 nodename = uqnodename.stringMatched(1);
 366               }
 367             }
 368             else
 369             {
 370               Error = ErrorStringrange(Error,
 371                                        "File has broken algorithm - overwritten nodename",
 372                                        10, fcp, nf);
 373             }
 374           }
 375
 376           if (nbootstrap.search(fstring) &&
 377               (nbootstrap.matchedFrom(1) > (uqnodename.matchedFrom(1) +
 378                                             uqnodename.stringMatched().length())))
 379           {
 380             try
 381             {
 382               bootstrap = (new Integer(nbootstrap.stringMatched(1))).intValue();
 383               HasBootstrap = true;
 384             }
 385             catch (Exception e)
 386             {
 387               Error = ErrorStringrange(Error,
 388                                        "Can't parse bootstrap value", 4,
 389                                        cp + nbootstrap.matchedFrom(), nf);
 390             }
 391           }
 392
 393           boolean nodehasdistance = false;
 394
 395           if (ndist.search(fstring))
 396           {
 397             try
 398             {
 399               distance = (new Float(ndist.stringMatched(1))).floatValue();
 400               HasDistances = true;
 401               nodehasdistance = true;
 402             }
 403             catch (Exception e)
 404             {
 405               Error = ErrorStringrange(Error,
 406                                        "Can't parse node distance value", 7,
 407                                        cp + ndist.matchedFrom(), nf);
 408             }
 409           }
 410
 411           if (ascending)
 412           {
 413             // Write node info here
 414             c.setName(nodename);
 415             // Trees without distances still need a render distance
 416             c.dist = (HasDistances) ? distance : DefDistance;
 417             // be consistent for internal bootstrap defaults too
 418             c.setBootstrap( (HasBootstrap) ? bootstrap : DefBootstrap);
 419             if (c == realroot)
 420             {
 421               RootHasDistance = nodehasdistance; // JBPNote This is really UGLY!!! Ensure root node gets its given distance
 422             }
 423           }
 424           else
 425           {
 426             // Find a place to put the leaf
 427             SequenceNode newnode = new SequenceNode(null, c, nodename,
 428                 (HasDistances) ? distance : DefDistance,
 429                 (HasBootstrap) ? bootstrap : DefBootstrap, false);
 430
 431             if (c.right() == null)
 432             {
 433               c.setRight(newnode);
 434             }
 435             else
 436             {
 437               if (c.left() == null)
 438               {
 439                 c.setLeft(newnode);
 440               }
 441               else
 442               {
 443                 // Insert a dummy node for polytomy
 444                 // dummy nodes have distances
 445                 SequenceNode newdummy = new SequenceNode(null, c,
 446                     null, (HasDistances ? 0 : DefDistance), 0, true);
 447                 newdummy.SetChildren(c.left(), newnode);
 448                 c.setLeft(newdummy);
 449               }
 450             }
 451           }
 452
 453           if (ascending)
 454           {
 455             // move back up the tree from preceding closure
 456             c = c.AscendTree();
 457
 458             if ( (d > -1) && (c == null))
 459             {
 460               Error = ErrorStringrange(Error,
 461                                        "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
 462                                        7, fcp, nf);
 463             }
 464           }
 465
 466           if (nf.charAt(fcp) == ')')
 467           {
 468             d--;
 469             ascending = true;
 470           }
 471           else
 472           {
 473             if (nf.charAt(fcp) == ',')
 474             {
 475               if (ascending)
 476               {
 477                 ascending = false;
 478               }
 479               else
 480               {
 481                 // Just advance focus, if we need to
 482                 if ( (c.left() != null) && (!c.left().isLeaf()))
 483                 {
 484                   c = (SequenceNode) c.left();
 485                 }
 486               }
 487             }
 488             else
 489             {
 490               if (nf.charAt(fcp)=='[') {
 491
 492               }
 493
 494                 // else : We do nothing if ';' is encountered.
 495             }
 496           }
 497
 498           // Reset new node properties to obvious fakes
 499           nodename = null;
 500           distance = DefDistance;
 501           bootstrap = DefBootstrap;
 502
 503           if (nextcp==0)
 504             cp = fcp + 1;
 505           else
 506             cp=nextcp;
 507       }
 508     }
 509
 510     if (Error != null)
 511     {
 512       throw (new IOException("NewickFile: " + Error + "\n"));
 513     }
 514     if (root==null)
 515     {
 516       throw (new IOException("NewickFile: No Tree read in\n"));
 517     }
 518     // THe next line is failing for topali trees - not sure why yet. if (root.right()!=null && root.isDummy())
 519     root = (SequenceNode) root.right().detach(); // remove the imaginary root.
 520
 521     if (!RootHasDistance)
 522     {
 523       root.dist = (HasDistances) ? 0 : DefDistance;
 524     }
 525   }
 526
 527   /**
 528    * DOCUMENT ME!
 529    *
 530    * @return DOCUMENT ME!
 531    */
 532   public SequenceNode getTree()
 533   {
 534     return root;
 535   }
 536
 537   /**
 538    * Generate a newick format tree according to internal flags
 539    * for bootstraps, distances and root distances.
 540    *
 541    * @return new hampshire tree in a single line
 542    */
 543   public String print()
 544   {
 545     synchronized (this)
 546     {
 547       StringBuffer tf = new StringBuffer();
 548       print(tf, root);
 549
 550       return (tf.append(";").toString());
 551     }
 552   }
 553
 554   /**
 555    *
 556    *
 557    * Generate a newick format tree according to internal flags
 558    * for distances and root distances and user specificied writing of
 559    * bootstraps.
 560    * @param withbootstraps controls if bootstrap values are explicitly written.
 561    *
 562    * @return new hampshire tree in a single line
 563    */
 564   public String print(boolean withbootstraps)
 565   {
 566     synchronized (this)
 567     {
 568       boolean boots = this.HasBootstrap;
 569       this.HasBootstrap = withbootstraps;
 570
 571       String rv = print();
 572       this.HasBootstrap = boots;
 573
 574       return rv;
 575     }
 576   }
 577
 578   /**
 579    *
 580    * Generate newick format tree according to internal flags
 581    * for writing root node distances.
 582    *
 583    * @param withbootstraps explicitly write bootstrap values
 584    * @param withdists explicitly write distances
 585    *
 586    * @return new hampshire tree in a single line
 587    */
 588   public String print(boolean withbootstraps, boolean withdists)
 589   {
 590     synchronized (this)
 591     {
 592       boolean dists = this.HasDistances;
 593       this.HasDistances = withdists;
 594
 595       String rv = print(withbootstraps);
 596       this.HasDistances = dists;
 597
 598       return rv;
 599     }
 600   }
 601
 602   /**
 603    * Generate newick format tree according to user specified flags
 604    *
 605    * @param withbootstraps explicitly write bootstrap values
 606    * @param withdists explicitly write distances
 607    * @param printRootInfo explicitly write root distance
 608    *
 609    * @return new hampshire tree in a single line
 610    */
 611   public String print(boolean withbootstraps, boolean withdists,
 612                       boolean printRootInfo)
 613   {
 614     synchronized (this)
 615     {
 616       boolean rootinfo = printRootInfo;
 617       this.printRootInfo = printRootInfo;
 618
 619       String rv = print(withbootstraps, withdists);
 620       this.printRootInfo = rootinfo;
 621
 622       return rv;
 623     }
 624   }
 625
 626   /**
 627    * DOCUMENT ME!
 628    *
 629    * @return DOCUMENT ME!
 630    */
 631   char getQuoteChar()
 632   {
 633     return QuoteChar;
 634   }
 635
 636   /**
 637    * DOCUMENT ME!
 638    *
 639    * @param c DOCUMENT ME!
 640    *
 641    * @return DOCUMENT ME!
 642    */
 643   char setQuoteChar(char c)
 644   {
 645     char old = QuoteChar;
 646     QuoteChar = c;
 647
 648     return old;
 649   }
 650
 651   /**
 652    * DOCUMENT ME!
 653    *
 654    * @param name DOCUMENT ME!
 655    *
 656    * @return DOCUMENT ME!
 657    */
 658   private String nodeName(String name)
 659   {
 660     if (NodeSafeName[0].search(name))
 661     {
 662       return QuoteChar + NodeSafeName[1].replaceAll(name) + QuoteChar;
 663     }
 664     else
 665     {
 666       return NodeSafeName[2].replaceAll(name);
 667     }
 668   }
 669
 670   /**
 671    * DOCUMENT ME!
 672    *
 673    * @param c DOCUMENT ME!
 674    *
 675    * @return DOCUMENT ME!
 676    */
 677   private String printNodeField(SequenceNode c)
 678   {
 679     return ( (c.getName() == null) ? "" : nodeName(c.getName())) +
 680         ( (HasBootstrap)
 681          ? ( (c.getBootstrap() > -1) ? (" " + c.getBootstrap()) : "") : "") +
 682         ( (HasDistances) ? (":" + c.dist) : "");
 683   }
 684
 685   /**
 686    * DOCUMENT ME!
 687    *
 688    * @param root DOCUMENT ME!
 689    *
 690    * @return DOCUMENT ME!
 691    */
 692   private String printRootField(SequenceNode root)
 693   {
 694     return (printRootInfo)
 695         ? ( ( (root.getName() == null) ? "" : nodeName(root.getName())) +
 696            ( (HasBootstrap)
 697             ? ( (root.getBootstrap() > -1) ? (" " + root.getBootstrap()) : "") :
 698             "") +
 699            ( (RootHasDistance) ? (":" + root.dist) : "")) : "";
 700   }
 701
 702   // Non recursive call deals with root node properties
 703   public void print(StringBuffer tf, SequenceNode root)
 704   {
 705     if (root != null)
 706     {
 707       if (root.isLeaf() && printRootInfo)
 708       {
 709         tf.append(printRootField(root));
 710       }
 711       else
 712       {
 713         if (root.isDummy())
 714         {
 715           _print(tf, (SequenceNode) root.right());
 716           _print(tf, (SequenceNode) root.left());
 717         }
 718         else
 719         {
 720           tf.append("(");
 721           _print(tf, (SequenceNode) root.right());
 722
 723           if (root.left() != null)
 724           {
 725             tf.append(",");
 726           }
 727
 728           _print(tf, (SequenceNode) root.left());
 729           tf.append(")" + printRootField(root));
 730         }
 731       }
 732     }
 733   }
 734
 735   // Recursive call for non-root nodes
 736   public void _print(StringBuffer tf, SequenceNode c)
 737   {
 738     if (c != null)
 739     {
 740       if (c.isLeaf())
 741       {
 742         tf.append(printNodeField(c));
 743       }
 744       else
 745       {
 746         if (c.isDummy())
 747         {
 748           _print(tf, (SequenceNode) c.left());
 749           if (c.left() != null)
 750           {
 751             tf.append(",");
 752           }
 753           _print(tf, (SequenceNode) c.right());
 754         }
 755         else
 756         {
 757           tf.append("(");
 758           _print(tf, (SequenceNode) c.right());
 759
 760           if (c.left() != null)
 761           {
 762             tf.append(",");
 763           }
 764
 765           _print(tf, (SequenceNode) c.left());
 766           tf.append(")" + printNodeField(c));
 767         }
 768       }
 769     }
 770   }
 771
 772   // Test
 773   public static void main(String[] args)
 774   {
 775     try
 776     {
 777       if (args == null || args.length != 1)
 778       {
 779         System.err.println(
 780             "Takes one argument - file name of a newick tree file.");
 781         System.exit(0);
 782       }
 783
 784       File fn = new File(args[0]);
 785
 786       StringBuffer newickfile = new StringBuffer();
 787       BufferedReader treefile = new BufferedReader(new FileReader(fn));
 788       String l;
 789
 790       while ( (l = treefile.readLine()) != null)
 791       {
 792         newickfile.append(l);
 793       }
 794
 795       treefile.close();
 796       System.out.println("Read file :\n");
 797
 798       NewickFile trf = new NewickFile(args[0], "File");
 799       trf.parse();
 800       System.out.println("Original file :\n");
 801
 802       com.stevesoft.pat.Regex nonl = new com.stevesoft.pat.Regex("\n+", "");
 803       System.out.println(nonl.replaceAll(newickfile.toString()) + "\n");
 804
 805       System.out.println("Parsed file.\n");
 806       System.out.println("Default output type for original input.\n");
 807       System.out.println(trf.print());
 808       System.out.println("Without bootstraps.\n");
 809       System.out.println(trf.print(false));
 810       System.out.println("Without distances.\n");
 811       System.out.println(trf.print(true, false));
 812       System.out.println("Without bootstraps but with distanecs.\n");
 813       System.out.println(trf.print(false, true));
 814       System.out.println("Without bootstraps or distanecs.\n");
 815       System.out.println(trf.print(false, false));
 816       System.out.println("With bootstraps and with distances.\n");
 817       System.out.println(trf.print(true, true));
 818     }
 819     catch (java.io.IOException e)
 820     {
 821       System.err.println("Exception\n" + e);
 822       e.printStackTrace();
 823     }
 824   }
 825 }