2 * Jalview - A Sequence Alignment Editor and Viewer
\r
3 * Copyright (C) 2007 AM Waterhouse, J Procter, G Barton, M Clamp, S Searle
\r
5 * This program is free software; you can redistribute it and/or
\r
6 * modify it under the terms of the GNU General Public License
\r
7 * as published by the Free Software Foundation; either version 2
\r
8 * of the License, or (at your option) any later version.
\r
10 * This program is distributed in the hope that it will be useful,
\r
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
13 * GNU General Public License for more details.
\r
15 * You should have received a copy of the GNU General Public License
\r
16 * along with this program; if not, write to the Free Software
\r
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
\r
22 // http://evolution.genetics.washington.edu/phylip/newick_doc.html
\r
23 // TODO: Implement Basic NHX tag parsing and preservation
\r
24 // TODO: http://evolution.genetics.wustl.edu/eddy/forester/NHX.html
\r
25 // TODO: Extended SequenceNodeI to hold parsed NHX strings
\r
30 import jalview.datamodel.*;
\r
36 * @version $Revision$
\r
38 public class NewickFile
\r
42 private boolean HasBootstrap = false;
\r
43 private boolean HasDistances = false;
\r
44 private boolean RootHasDistance = false;
\r
47 boolean ReplaceUnderscores = false;
\r
48 boolean printRootInfo = false;
\r
49 private com.stevesoft.pat.Regex[] NodeSafeName = new com.stevesoft.pat.Regex[]
\r
51 new com.stevesoft.pat.Regex().perlCode("m/[\\[,:'()]/"), // test for requiring quotes
\r
52 new com.stevesoft.pat.Regex().perlCode("s/'/''/"), // escaping quote characters
\r
53 new com.stevesoft.pat.Regex().perlCode("s/\\/w/_/") // unqoted whitespace transformation
\r
55 char QuoteChar = '\'';
\r
58 * Creates a new NewickFile object.
\r
60 * @param inStr DOCUMENT ME!
\r
62 * @throws IOException DOCUMENT ME!
\r
64 public NewickFile(String inStr)
\r
67 super(inStr, "Paste");
\r
71 * Creates a new NewickFile object.
\r
73 * @param inFile DOCUMENT ME!
\r
74 * @param type DOCUMENT ME!
\r
76 * @throws IOException DOCUMENT ME!
\r
78 public NewickFile(String inFile, String type)
\r
81 super(inFile, type);
\r
85 * Creates a new NewickFile object.
\r
87 * @param newtree DOCUMENT ME!
\r
89 public NewickFile(SequenceNode newtree)
\r
95 * Creates a new NewickFile object.
\r
97 * @param newtree DOCUMENT ME!
\r
98 * @param bootstrap DOCUMENT ME!
\r
100 public NewickFile(SequenceNode newtree, boolean bootstrap)
\r
102 HasBootstrap = bootstrap;
\r
107 * Creates a new NewickFile object.
\r
109 * @param newtree DOCUMENT ME!
\r
110 * @param bootstrap DOCUMENT ME!
\r
111 * @param distances DOCUMENT ME!
\r
113 public NewickFile(SequenceNode newtree, boolean bootstrap, boolean distances)
\r
116 HasBootstrap = bootstrap;
\r
117 HasDistances = distances;
\r
121 * Creates a new NewickFile object.
\r
123 * @param newtree DOCUMENT ME!
\r
124 * @param bootstrap DOCUMENT ME!
\r
125 * @param distances DOCUMENT ME!
\r
126 * @param rootdistance DOCUMENT ME!
\r
128 public NewickFile(SequenceNode newtree, boolean bootstrap,
\r
129 boolean distances, boolean rootdistance)
\r
132 HasBootstrap = bootstrap;
\r
133 HasDistances = distances;
\r
134 RootHasDistance = rootdistance;
\r
140 * @param Error DOCUMENT ME!
\r
141 * @param Er DOCUMENT ME!
\r
142 * @param r DOCUMENT ME!
\r
143 * @param p DOCUMENT ME!
\r
144 * @param s DOCUMENT ME!
\r
146 * @return DOCUMENT ME!
\r
148 private String ErrorStringrange(String Error, String Er, int r, int p,
\r
151 return ( (Error == null) ? "" : Error) + Er + " at position " + p +
\r
153 s.substring( ( (p - r) < 0) ? 0 : (p - r),
\r
154 ( (p + r) > s.length()) ? s.length() : (p + r)) + " )\n";
\r
157 // @tree annotations
\r
158 // These are set automatically by the reader
\r
159 public boolean HasBootstrap()
\r
161 return HasBootstrap;
\r
167 * @return DOCUMENT ME!
\r
169 public boolean HasDistances()
\r
171 return HasDistances;
\r
174 public boolean HasRootDistance()
\r
176 return RootHasDistance;
\r
182 * @throws IOException DOCUMENT ME!
\r
184 public void parse()
\r
189 { // fill nf with complete tree file
\r
191 StringBuffer file = new StringBuffer();
\r
193 while ( (nf = nextLine()) != null)
\r
198 nf = file.toString();
\r
201 root = new SequenceNode();
\r
203 SequenceNode realroot = null;
\r
204 SequenceNode c = root;
\r
208 //int flen = nf.length();
\r
210 String Error = null;
\r
211 String nodename = null;
\r
213 float DefDistance = (float) 0.001; // @param Default distance for a node - very very small
\r
214 int DefBootstrap = 0; // @param Default bootstrap for a node
\r
216 float distance = DefDistance;
\r
217 int bootstrap = DefBootstrap;
\r
219 boolean ascending = false; // flag indicating that we are leaving the current node
\r
221 com.stevesoft.pat.Regex majorsyms = new com.stevesoft.pat.Regex(
\r
224 while (majorsyms.searchFrom(nf, cp) && (Error == null))
\r
226 int fcp = majorsyms.matchedFrom();
\r
228 switch (nf.charAt(fcp))
\r
230 case '[': // Comment or structured/extended NH format info
\r
232 com.stevesoft.pat.Regex comment = new com.stevesoft.pat.Regex(
\r
235 if (comment.searchFrom(nf, fcp))
\r
237 // Skip the comment field
\r
238 cp = 1 + comment.matchedFrom();
\r
242 Error = ErrorStringrange(Error, "Unterminated comment", 3,
\r
252 // ascending should not be set
\r
253 // New Internal node
\r
256 Error = ErrorStringrange(Error, "Unexpected '('", 7, fcp, nf);
\r
264 if (c.right() == null)
\r
266 c.setRight(new SequenceNode(null, c, null, DefDistance,
\r
267 DefBootstrap, false));
\r
268 c = (SequenceNode) c.right();
\r
272 if (c.left() != null)
\r
274 // Dummy node for polytomy - keeps c.left free for new node
\r
275 SequenceNode tmpn = new SequenceNode(null, c, null, 0,
\r
277 tmpn.SetChildren(c.left(), c.right());
\r
281 c.setLeft(new SequenceNode(null, c, null, DefDistance,
\r
282 DefBootstrap, false));
\r
283 c = (SequenceNode) c.left();
\r
286 if (realroot == null)
\r
292 distance = DefDistance;
\r
293 bootstrap = DefBootstrap;
\r
298 // Deal with quoted fields
\r
301 com.stevesoft.pat.Regex qnodename = new com.stevesoft.pat.Regex(
\r
304 if (qnodename.searchFrom(nf, fcp))
\r
306 int nl = qnodename.stringMatched().length();
\r
307 nodename = new String(qnodename.stringMatched().substring(0,
\r
313 Error = ErrorStringrange(Error,
\r
314 "Unterminated quotes for nodename", 7, fcp,
\r
324 Error = ErrorStringrange(Error,
\r
325 "Wayward semicolon (depth=" + d + ")", 7,
\r
329 // cp advanced at the end of default
\r
332 // Parse simpler field strings
\r
333 String fstring = nf.substring(cp, fcp);
\r
334 com.stevesoft.pat.Regex uqnodename = new com.stevesoft.pat.Regex(
\r
335 "\\b([^' :;\\](),]+)");
\r
336 com.stevesoft.pat.Regex nbootstrap = new com.stevesoft.pat.Regex(
\r
337 "\\S+([0-9+]+)\\S*:");
\r
338 com.stevesoft.pat.Regex ndist = new com.stevesoft.pat.Regex(
\r
341 if (uqnodename.search(fstring) &&
\r
342 ( (uqnodename.matchedFrom(1) == 0) ||
\r
343 (fstring.charAt(uqnodename.matchedFrom(1) - 1) != ':'))) // JBPNote HACK!
\r
345 if (nodename == null)
\r
347 if (ReplaceUnderscores)
\r
349 nodename = uqnodename.stringMatched(1).replace('_',
\r
354 nodename = uqnodename.stringMatched(1);
\r
359 Error = ErrorStringrange(Error,
\r
360 "File has broken algorithm - overwritten nodename",
\r
365 if (nbootstrap.search(fstring) &&
\r
366 (nbootstrap.matchedFrom(1) > (uqnodename.matchedFrom(1) +
\r
367 uqnodename.stringMatched().length())))
\r
371 bootstrap = (new Integer(nbootstrap.stringMatched(1))).intValue();
\r
372 HasBootstrap = true;
\r
374 catch (Exception e)
\r
376 Error = ErrorStringrange(Error,
\r
377 "Can't parse bootstrap value", 4,
\r
378 cp + nbootstrap.matchedFrom(), nf);
\r
382 boolean nodehasdistance = false;
\r
384 if (ndist.search(fstring))
\r
388 distance = (new Float(ndist.stringMatched(1))).floatValue();
\r
389 HasDistances = true;
\r
390 nodehasdistance = true;
\r
392 catch (Exception e)
\r
394 Error = ErrorStringrange(Error,
\r
395 "Can't parse node distance value", 7,
\r
396 cp + ndist.matchedFrom(), nf);
\r
402 // Write node info here
\r
403 c.setName(nodename);
\r
404 // Trees without distances still need a render distance
\r
405 c.dist = (HasDistances) ? distance : DefDistance;
\r
406 // be consistent for internal bootstrap defaults too
\r
407 c.setBootstrap( (HasBootstrap) ? bootstrap : DefBootstrap);
\r
410 RootHasDistance = nodehasdistance; // JBPNote This is really UGLY!!! Ensure root node gets its given distance
\r
415 // Find a place to put the leaf
\r
416 SequenceNode newnode = new SequenceNode(null, c, nodename,
\r
417 (HasDistances) ? distance : DefDistance,
\r
418 (HasBootstrap) ? bootstrap : DefBootstrap, false);
\r
420 if (c.right() == null)
\r
422 c.setRight(newnode);
\r
426 if (c.left() == null)
\r
428 c.setLeft(newnode);
\r
432 // Insert a dummy node for polytomy
\r
433 // dummy nodes have distances
\r
434 SequenceNode newdummy = new SequenceNode(null, c,
\r
435 null, (HasDistances ? 0 : DefDistance), 0, true);
\r
436 newdummy.SetChildren(c.left(), newnode);
\r
437 c.setLeft(newdummy);
\r
444 // move back up the tree from preceding closure
\r
445 c = c.AscendTree();
\r
447 if ( (d > -1) && (c == null))
\r
449 Error = ErrorStringrange(Error,
\r
450 "File broke algorithm: Lost place in tree (is there an extra ')' ?)",
\r
455 if (nf.charAt(fcp) == ')')
\r
462 if (nf.charAt(fcp) == ',')
\r
470 // Just advance focus, if we need to
\r
471 if ( (c.left() != null) && (!c.left().isLeaf()))
\r
473 c = (SequenceNode) c.left();
\r
478 // else : We do nothing if ';' is encountered.
\r
481 // Reset new node properties to obvious fakes
\r
483 distance = DefDistance;
\r
484 bootstrap = DefBootstrap;
\r
492 throw (new IOException("NewickFile: " + Error + "\n"));
\r
495 root = (SequenceNode) root.right().detach(); // remove the imaginary root.
\r
497 if (!RootHasDistance)
\r
499 root.dist = (HasDistances) ? 0 : DefDistance;
\r
506 * @return DOCUMENT ME!
\r
508 public SequenceNode getTree()
\r
514 * Generate a newick format tree according to internal flags
\r
515 * for bootstraps, distances and root distances.
\r
517 * @return new hampshire tree in a single line
\r
519 public String print()
\r
521 synchronized (this)
\r
523 StringBuffer tf = new StringBuffer();
\r
526 return (tf.append(";").toString());
\r
533 * Generate a newick format tree according to internal flags
\r
534 * for distances and root distances and user specificied writing of
\r
536 * @param withbootstraps controls if bootstrap values are explicitly written.
\r
538 * @return new hampshire tree in a single line
\r
540 public String print(boolean withbootstraps)
\r
542 synchronized (this)
\r
544 boolean boots = this.HasBootstrap;
\r
545 this.HasBootstrap = withbootstraps;
\r
547 String rv = print();
\r
548 this.HasBootstrap = boots;
\r
556 * Generate newick format tree according to internal flags
\r
557 * for writing root node distances.
\r
559 * @param withbootstraps explicitly write bootstrap values
\r
560 * @param withdists explicitly write distances
\r
562 * @return new hampshire tree in a single line
\r
564 public String print(boolean withbootstraps, boolean withdists)
\r
566 synchronized (this)
\r
568 boolean dists = this.HasDistances;
\r
569 this.HasDistances = withdists;
\r
571 String rv = print(withbootstraps);
\r
572 this.HasDistances = dists;
\r
579 * Generate newick format tree according to user specified flags
\r
581 * @param withbootstraps explicitly write bootstrap values
\r
582 * @param withdists explicitly write distances
\r
583 * @param printRootInfo explicitly write root distance
\r
585 * @return new hampshire tree in a single line
\r
587 public String print(boolean withbootstraps, boolean withdists,
\r
588 boolean printRootInfo)
\r
590 synchronized (this)
\r
592 boolean rootinfo = printRootInfo;
\r
593 this.printRootInfo = printRootInfo;
\r
595 String rv = print(withbootstraps, withdists);
\r
596 this.printRootInfo = rootinfo;
\r
605 * @return DOCUMENT ME!
\r
607 char getQuoteChar()
\r
615 * @param c DOCUMENT ME!
\r
617 * @return DOCUMENT ME!
\r
619 char setQuoteChar(char c)
\r
621 char old = QuoteChar;
\r
630 * @param name DOCUMENT ME!
\r
632 * @return DOCUMENT ME!
\r
634 private String nodeName(String name)
\r
636 if (NodeSafeName[0].search(name))
\r
638 return QuoteChar + NodeSafeName[1].replaceAll(name) + QuoteChar;
\r
642 return NodeSafeName[2].replaceAll(name);
\r
649 * @param c DOCUMENT ME!
\r
651 * @return DOCUMENT ME!
\r
653 private String printNodeField(SequenceNode c)
\r
655 return ( (c.getName() == null) ? "" : nodeName(c.getName())) +
\r
657 ? ( (c.getBootstrap() > -1) ? (" " + c.getBootstrap()) : "") : "") +
\r
658 ( (HasDistances) ? (":" + c.dist) : "");
\r
664 * @param root DOCUMENT ME!
\r
666 * @return DOCUMENT ME!
\r
668 private String printRootField(SequenceNode root)
\r
670 return (printRootInfo)
\r
671 ? ( ( (root.getName() == null) ? "" : nodeName(root.getName())) +
\r
673 ? ( (root.getBootstrap() > -1) ? (" " + root.getBootstrap()) : "") :
\r
675 ( (RootHasDistance) ? (":" + root.dist) : "")) : "";
\r
678 // Non recursive call deals with root node properties
\r
679 public void print(StringBuffer tf, SequenceNode root)
\r
683 if (root.isLeaf() && printRootInfo)
\r
685 tf.append(printRootField(root));
\r
689 if (root.isDummy())
\r
691 _print(tf, (SequenceNode) root.right());
\r
692 _print(tf, (SequenceNode) root.left());
\r
697 _print(tf, (SequenceNode) root.right());
\r
699 if (root.left() != null)
\r
704 _print(tf, (SequenceNode) root.left());
\r
705 tf.append(")" + printRootField(root));
\r
711 // Recursive call for non-root nodes
\r
712 public void _print(StringBuffer tf, SequenceNode c)
\r
718 tf.append(printNodeField(c));
\r
724 _print(tf, (SequenceNode) c.left());
\r
725 if (c.left() != null)
\r
729 _print(tf, (SequenceNode) c.right());
\r
734 _print(tf, (SequenceNode) c.right());
\r
736 if (c.left() != null)
\r
741 _print(tf, (SequenceNode) c.left());
\r
742 tf.append(")" + printNodeField(c));
\r
749 public static void main(String[] args)
\r
753 if (args == null || args.length != 1)
\r
755 System.err.println(
\r
756 "Takes one argument - file name of a newick tree file.");
\r
760 File fn = new File(args[0]);
\r
762 StringBuffer newickfile = new StringBuffer();
\r
763 BufferedReader treefile = new BufferedReader(new FileReader(fn));
\r
766 while ( (l = treefile.readLine()) != null)
\r
768 newickfile.append(l);
\r
772 System.out.println("Read file :\n");
\r
774 NewickFile trf = new NewickFile(args[0], "File");
\r
776 System.out.println("Original file :\n");
\r
778 com.stevesoft.pat.Regex nonl = new com.stevesoft.pat.Regex("\n+", "");
\r
779 System.out.println(nonl.replaceAll(newickfile.toString()) + "\n");
\r
781 System.out.println("Parsed file.\n");
\r
782 System.out.println("Default output type for original input.\n");
\r
783 System.out.println(trf.print());
\r
784 System.out.println("Without bootstraps.\n");
\r
785 System.out.println(trf.print(false));
\r
786 System.out.println("Without distances.\n");
\r
787 System.out.println(trf.print(true, false));
\r
788 System.out.println("Without bootstraps but with distanecs.\n");
\r
789 System.out.println(trf.print(false, true));
\r
790 System.out.println("Without bootstraps or distanecs.\n");
\r
791 System.out.println(trf.print(false, false));
\r
792 System.out.println("With bootstraps and with distances.\n");
\r
793 System.out.println(trf.print(true, true));
\r
795 catch (java.io.IOException e)
\r
797 System.err.println("Exception\n" + e);
\r
798 e.printStackTrace();
\r