src/jalview/io/NewickFile.java

   1 // NewickFile.java
   2 // Tree I/O
   3 // http://evolution.genetics.washington.edu/phylip/newick_doc.html
   4 package jalview.io;
   5
   6 import java.io.*;
   7 import java.util.*;
   8 import jalview.datamodel.*;
   9
  10 public class NewickFile extends FileParse
  11 {
  12   SequenceNode root;
  13
  14   private boolean HasBootstrap = false;
  15   private boolean HasDistances = false;
  16   private boolean RootHasDistance = false;
  17
  18   private String ErrorStringrange(String Error, String Er, int r, int p, String s) {
  19     return ((Error==null) ? "" : Error)
  20         + Er +
  21         " at position "+p+" ( "
  22         + s.substring((p-r)<0 ? 0 : (p-r),
  23                       (p+r)>s.length() ? s.length() : (p+r))
  24         + " )\n";
  25   }
  26
  27   // @tree annotations
  28   // These are set automatically by the reader
  29   public boolean HasBootstrap() {
  30     return HasBootstrap;
  31   }
  32
  33   public boolean HasDistances() {
  34     return HasDistances;
  35   }
  36   public NewickFile(String inStr) throws IOException
  37   {
  38     super(inStr, "Paste");
  39   }
  40
  41   public NewickFile(String inFile, String type)
  42       throws IOException
  43   {
  44
  45     super(inFile, type);
  46   }
  47   // File IO Flags
  48   boolean ReplaceUnderscores = false;
  49
  50   public void parse() throws IOException
  51   {
  52     String nf;
  53
  54     { // fill nf with complete tree file
  55       StringBuffer file = new StringBuffer();
  56       while ( (nf = nextLine()) != null)
  57       {
  58         file.append(nf);
  59       }
  60       nf = file.toString();
  61     }
  62
  63     root = new SequenceNode();
  64     SequenceNode realroot = null;
  65     SequenceNode c = root;
  66     int d = -1;
  67     int cp = 0;
  68     int flen = nf.length();
  69     String Error = null;
  70     String nodename = null;
  71     float distance=-99999;
  72     int bootstrap=-99999;
  73     boolean ascending = false; // flag indicating that we are leaving the current node
  74     com.stevesoft.pat.Regex majorsyms = new com.stevesoft.pat.Regex("[(\\['),;]");
  75     while (majorsyms.searchFrom(nf, cp) && Error==null) {
  76       int fcp = majorsyms.matchedFrom();
  77       switch (nf.charAt(fcp)) {
  78
  79         case '[': // Comment or structured/extended NH format info
  80           com.stevesoft.pat.Regex comment = new com.stevesoft.pat.Regex("]");
  81           if (comment.searchFrom(nf, fcp))
  82           {
  83             // Skip the comment field
  84             cp = 1 + comment.matchedFrom();
  85           }
  86           else
  87           {
  88             Error = ErrorStringrange(Error, "Unterminated comment", 3, fcp, nf);
  89           }
  90           ;
  91           break;
  92
  93         case '(':
  94
  95           // ascending should not be set
  96           // New Internal node
  97           if (ascending)
  98           {
  99             Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
 100             continue;
 101           }
 102           ;
 103           d++;
 104           if (c.right() == null)
 105           {
 106             c.setRight(new SequenceNode(null, c, 0, null));
 107             c = (SequenceNode) c.right();
 108           }
 109           else
 110           {
 111             if (c.left() != null)
 112             {
 113               // Dummy node for polytomy - keeps c.left free for new node
 114               SequenceNode tmpn = new SequenceNode(null, c, null, 0, 0, true);
 115               tmpn.SetChildren(c.left(), c.right());
 116               c.setRight(tmpn);
 117             }
 118             c.setLeft(new SequenceNode(null, c, 0, null));
 119             c = (SequenceNode) c.left();
 120           }
 121           if (realroot==null) {
 122             realroot = c;
 123           }
 124           nodename = null;
 125           distance = -99999;
 126           bootstrap = -99999;
 127           cp = fcp + 1;
 128           break;
 129
 130           // Deal with quoted fields
 131         case '\'':
 132           com.stevesoft.pat.Regex qnodename = new com.stevesoft.pat.Regex(
 133               "([^']|'')+'");
 134           if (qnodename.searchFrom(nf, fcp))
 135           {
 136             int nl = qnodename.stringMatched().length();
 137             nodename = new String(qnodename.stringMatched().substring(0, nl - 1));
 138             cp = fcp + nl + 1;
 139           }
 140           else
 141           {
 142             Error = ErrorStringrange(Error, "Unterminated quotes for nodename",
 143                                      7, fcp, nf);
 144           }
 145           break;
 146
 147         case ';':
 148           if (d != -1)
 149           {
 150             Error = ErrorStringrange(Error,
 151                                      "Wayward semicolon (depth=" + d + ")", 7,
 152                                      fcp, nf);
 153           }
 154           // cp advanced at the end of default
 155
 156         default:
 157
 158           // Parse simpler field strings
 159           String fstring = nf.substring(cp, fcp);
 160           com.stevesoft.pat.Regex uqnodename = new com.stevesoft.pat.Regex(
 161               "\\b([^' :;\\](),]+)");
 162           com.stevesoft.pat.Regex nbootstrap = new com.stevesoft.pat.Regex(
 163               "\\S+([0-9+]+)\\S*:");
 164           com.stevesoft.pat.Regex ndist = new com.stevesoft.pat.Regex(
 165               ":([-0-9.+]+)");
 166           if (uqnodename.search(fstring)
 167               && (uqnodename.matchedFrom(1) == 0
 168                   || fstring.charAt(uqnodename.matchedFrom(1) - 1) != ':')) // JBPNote HACK!
 169
 170           {
 171             if (nodename == null)
 172             {
 173               if (ReplaceUnderscores) {
 174                 nodename = uqnodename.stringMatched(1).replace('_', ' ');
 175               } else {
 176                 nodename = uqnodename.stringMatched(1);
 177               }
 178             }
 179             else
 180             {
 181               Error = ErrorStringrange(Error,
 182                                        "File has broken algorithm - overwritten nodename",
 183                                        10, fcp,
 184                                        nf);
 185             }
 186           }
 187           if (nbootstrap.search(fstring)
 188               &&
 189               nbootstrap.matchedFrom(1)
 190               > uqnodename.matchedFrom(1) + uqnodename.stringMatched().length())
 191           {
 192             try
 193             {
 194               bootstrap = (new Integer(nbootstrap.stringMatched(1))).intValue();
 195               HasBootstrap = true;
 196             }
 197             catch (Exception e)
 198             {
 199               Error = ErrorStringrange(Error, "Can't parse bootstrap value", 4,
 200                                        cp + nbootstrap.matchedFrom(), nf);
 201             }
 202           }
 203           boolean nodehasdistance=false;
 204           if (ndist.search(fstring))
 205           {
 206             try
 207             {
 208               distance = (new Float(ndist.stringMatched(1))).floatValue();
 209               HasDistances = true;
 210               nodehasdistance = true;
 211             }
 212             catch (Exception e)
 213             {
 214               Error = ErrorStringrange(Error, "Can't parse node distance value",
 215                                        7, cp + ndist.matchedFrom(), nf);
 216             }
 217           }
 218
 219           if (ascending)
 220           {
 221             // Write node info here
 222             c.setName(nodename);
 223             c.dist = (HasDistances) ? distance : 0;
 224             c.setBootstrap((HasBootstrap) ? bootstrap : 0);
 225             if (c==realroot) {
 226               RootHasDistance = nodehasdistance; // JBPNote This is really UGLY!!!
 227             }
 228           }
 229           else
 230           {
 231             // Find a place to put the leaf
 232             SequenceNode newnode = new SequenceNode(null, c,
 233                 (HasDistances) ? distance : 0,
 234                 nodename);
 235
 236             newnode.setBootstrap(HasBootstrap ? bootstrap : 0);
 237
 238             if (c.right() == null)
 239             {
 240               c.setRight(newnode);
 241             }
 242             else
 243             {
 244               if (c.left() == null)
 245               {
 246                 c.setLeft(newnode);
 247               }
 248               else
 249               {
 250                 // Insert a dummy node for polytomy
 251                 SequenceNode newdummy = new SequenceNode(null, c, null, 0, 0, true);
 252                 newdummy.SetChildren(c.left(), newnode);
 253                 c.setLeft(newdummy);
 254               }
 255             }
 256           }
 257           if (ascending)
 258           {
 259             // move back up the tree from preceding closure
 260             c = c.AscendTree();
 261             if (d > -1 && c == null)
 262             {
 263               Error = ErrorStringrange(Error,
 264                                        "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
 265                                        7, fcp, nf);
 266             }
 267           }
 268
 269           if (nf.charAt(fcp) == ')') {
 270             d--;
 271             ascending = true;
 272           } else {
 273             if (nf.charAt(fcp) == ',') {
 274               if (ascending) {
 275                ascending = false;
 276              } else {
 277                // Just advance focus, if we need to
 278                if (c.left()!=null && (!c.left().isLeaf())) {
 279                  c = (SequenceNode) c.left();
 280                }
 281              }
 282             } // else : We do nothing if ';' is encountered.
 283           }
 284           // Reset new node properties to obvious fakes
 285           nodename = null;
 286           distance = -99999;
 287           bootstrap = -99999;
 288
 289           cp=fcp+1;
 290       }
 291     }
 292
 293     if (Error!=null) {
 294       throw(new IOException("NewickFile: "+Error+"\n"));
 295     }
 296
 297     root = (SequenceNode) root.right().detach(); // remove the imaginary root.
 298     if (!RootHasDistance) {
 299       root.dist = 0;
 300     }
 301   }
 302
 303   public NewickFile(SequenceNode newtree) {
 304     root = newtree;
 305   }
 306
 307   public NewickFile(SequenceNode newtree, boolean bootstrap) {
 308     HasBootstrap = bootstrap;
 309     root=newtree;
 310   }
 311   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances) {
 312     root = newtree;
 313     HasBootstrap = bootstrap;
 314     HasDistances = distances;
 315   }
 316
 317   public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances, boolean rootdistance) {
 318       root = newtree;
 319       HasBootstrap = bootstrap;
 320       HasDistances = distances;
 321       RootHasDistance = rootdistance;
 322     }
 323
 324   public SequenceNode getTree() {
 325     return root;
 326   }
 327
 328   public String print() {
 329     synchronized (this) {
 330       StringBuffer tf = new StringBuffer();
 331       print(tf, root);
 332       return (tf.append(";").toString());
 333     }
 334   }
 335
 336   public String print(boolean withbootstraps) {
 337     synchronized(this) {
 338       boolean boots = this.HasBootstrap;
 339       this.HasBootstrap = withbootstraps;
 340       String rv = print();
 341       this.HasBootstrap = boots;
 342       return rv;
 343     }
 344   }
 345
 346   public String print(boolean withbootstraps, boolean withdists) {
 347     synchronized(this) {
 348       boolean dists = this.HasDistances;
 349       this.HasDistances = withdists;
 350       String rv = print(withbootstraps);
 351       this.HasDistances = dists;
 352       return rv;
 353     }
 354   }
 355   boolean printRootInfo = false;
 356
 357
 358   public String print(boolean withbootstraps, boolean withdists, boolean printRootInfo) {
 359     synchronized(this) {
 360       boolean rootinfo = printRootInfo;
 361       this.printRootInfo = printRootInfo;
 362       String rv = print(withbootstraps, withdists);
 363       this.printRootInfo = rootinfo;
 364       return rv;
 365     }
 366   }
 367   private com.stevesoft.pat.Regex[] NodeSafeName =
 368       new com.stevesoft.pat.Regex[]
 369       { new com.stevesoft.pat.Regex().perlCode("m/[\\[,:'()]/"), // test for requiring quotes
 370       new com.stevesoft.pat.Regex().perlCode("s/'/''/"), // escaping quote characters
 371       new com.stevesoft.pat.Regex().perlCode("s/\\/w/_/") // unqoted whitespace transformation
 372   };
 373   char QuoteChar='\'';
 374   char getQuoteChar() {
 375     return QuoteChar;
 376   }
 377
 378   char setQuoteChar(char c) {
 379     char old = QuoteChar;
 380     QuoteChar = c;
 381     return old;
 382   }
 383
 384   private String nodeName(String name) {
 385     if (NodeSafeName[0].search(name)) {
 386       return QuoteChar + NodeSafeName[1].replaceAll(name) + QuoteChar;
 387     } else {
 388       return NodeSafeName[2].replaceAll(name);
 389     }
 390   }
 391   private String printNodeField(SequenceNode c) {
 392
 393     return ( (c.getName() == null) ? ""
 394              : nodeName(c.getName()))
 395         + ( (HasBootstrap)
 396             ? ( (c.getBootstrap() > -1)
 397                 ? " " + c.getBootstrap()
 398                 : "")
 399             : "")
 400         + ( (HasDistances)
 401             ? ":" + c.dist : "");
 402   }
 403   private String printRootField(SequenceNode root) {
 404
 405       return (printRootInfo)
 406           ? (( (root.getName() == null) ? ""
 407                : nodeName(root.getName()))
 408              + ( (HasBootstrap)
 409                  ? ( (root.getBootstrap() > -1)
 410                      ? " " + root.getBootstrap()
 411                      : "")
 412                  : "")
 413              + ( (RootHasDistance)
 414                  ? ":" + root.dist : ""))
 415           : "";
 416     }
 417
 418 // Non recursive call deals with root node properties
 419   public void print(StringBuffer tf, SequenceNode root) {
 420     if (root!=null) {
 421       if (root.isLeaf() && printRootInfo) {
 422         tf.append(printRootField(root));
 423       } else {
 424         if (root.isDummy()) {
 425           _print(tf, (SequenceNode) root.right());
 426           _print(tf, (SequenceNode) root.left());
 427         } else {
 428           tf.append("(");
 429           _print(tf, (SequenceNode) root.right());
 430           if (root.left() != null) {
 431             tf.append(",");
 432           }
 433           _print(tf, (SequenceNode) root.left());
 434           tf.append(")" + printRootField(root));
 435         }
 436       }
 437     }
 438   }
 439
 440   // Recursive call for non-root nodes
 441   public void _print(StringBuffer tf, SequenceNode c) {
 442     if (c!=null) {
 443       if (c.isLeaf()) {
 444         tf.append(printNodeField(c));
 445       } else {
 446         if (c.isDummy()) {
 447           _print(tf, (SequenceNode) c.right());
 448           _print(tf, (SequenceNode) c.left());
 449         } else {
 450           tf.append("(");
 451           _print(tf, (SequenceNode) c.right());
 452           if (c.left() != null) {
 453             tf.append(",");
 454           }
 455           _print(tf, (SequenceNode) c.left());
 456           tf.append(")" + printNodeField(c));
 457         }
 458       }
 459     }
 460   }
 461
 462 // Test
 463   public static void main(String[] args)
 464 {
 465   try
 466   {
 467     File fn = new File(args[0]);
 468
 469     StringBuffer newickfile =  new StringBuffer();
 470     BufferedReader treefile =
 471         new BufferedReader(new FileReader(fn));
 472     String l;
 473     while ((l = treefile.readLine())!=null) {
 474       newickfile.append(l);
 475     }
 476     treefile.close();
 477     System.out.println("Read file :\n");
 478     NewickFile trf = new NewickFile(args[0], "File");
 479     trf.parse();
 480     System.out.println("Original file :\n");
 481     com.stevesoft.pat.Regex nonl = new com.stevesoft.pat.Regex("\n+", "");
 482     System.out.println(nonl.replaceAll(newickfile.toString())+"\n");
 483
 484     System.out.println("Parsed file.\n");
 485     System.out.println("Default output type for original input.\n");
 486     System.out.println(trf.print());
 487     System.out.println("Without bootstraps.\n");
 488     System.out.println(trf.print(false));
 489     System.out.println("Without distances.\n");
 490     System.out.println(trf.print(true,false));
 491     System.out.println("Without bootstraps but with distanecs.\n");
 492     System.out.println(trf.print(false, true));
 493     System.out.println("Without bootstraps or distanecs.\n");
 494     System.out.println(trf.print(false, false));
 495     System.out.println("With bootstraps and with distances.\n");
 496     System.out.println(trf.print(true, true));
 497   }
 498   catch (java.io.IOException e)
 499   {
 500     System.out.println("Exception\n" + e);
 501     e.printStackTrace();
 502   }
 503 }
 504
 505 }