src/jalview/io/NewickFile.java

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