Question: Parsing A Tree File
4
gravatar for User 1940
9.4 years ago by
User 194080
User 194080 wrote:

Hi,

Is there any script template that parses a tree into its subtrees while showing all subchild / subparent nodes?

For example, for this following tree:

((ar, tk) 23 , (abc, ((xa, xb) 26 , ((lima, limb) 28 , (((spi, sfi) 31 , (eqc, (kme, ame) 33 ) 32 ) 30 , ((fxf, (tva, tvb) 36 ) 35 , (fxe, (cjk, ((mrb, (qq, rr) 41 ) 40 , sgn) 39 ) 38 ) 37 ) 34 ) 29 ) 27 ) 25 ) 24 ) 22 ;

I would like to have the following output:

node 23 includes 'ar' and 'tk',
node 32 includes nodes 'egc' and 33 which include both 'kme' and 'ame'
[...]

I can write scripts to capture nodes with two or three children, however, it gets messy when it comes to capturing the nodes at the end.

Cheers,

phylogenetics tree parsing • 5.7k views
ADD COMMENTlink modified 9.4 years ago by jhc2.9k • written 9.4 years ago by User 194080
9
gravatar for jhc
9.4 years ago by
jhc2.9k
Spain
jhc2.9k wrote:

I would not rewrite the newick parser from scratch unless I had a very good reason. Have you tried any of tree manipulation libraries available (bio::phylo, ETE, etc.)?

Here it goes a very easy implementation using Python and ETE. You can customize the output as you wish.

from ete2 import Tree

def children_names(n):
    return ','.join([ch.name for ch in n.children])

nw = "((ar, tk) 23 , (abc, ((xa, xb) 26 , ((lima, limb) 28 , (((spi, sfi) 31 , (eqc, (kme, ame) 33 ) 32 ) 30 , ((fxf, (tva, tvb) 36 ) 35 , (fxe, (cjk, ((mrb, (qq, rr) 41 ) 40 , sgn) 39 ) 38 ) 37 ) 34 ) 29 ) 27 ) 25 ) 24 ) 22 ;"

tree = Tree(nw, format=1) # newick subformat 1 to read internal node names
for node in tree.traverse("postorder"):
    # A verbose output
    if not node.is_leaf() and node.up: # For all internal nodes
        print node.name, "whose parent is", node.up.name, \
        "has", len(node.children), "children named", children_names(node), \
        "and groups the following leaves:", ",".join(node.get_leaf_names())
    elif not node.is_leaf(): # In case we are at the root of the tree
        print node.name, "who is the root of the tree", \
        "has", len(node.children), "children named", children_names(node), \
        "and groups the following leaves:", ",".join(node.get_leaf_names())

I know this is not the most efficient way to browse the content of internal branches but, if your trees are not huge, few lines of code are more than enough.

23 whose parent is 22 has 2 children named ar,tk and groups the following leaves: ar,tk
26 whose parent is 25 has 2 children named xa,xb and groups the following leaves: xa,xb
28 whose parent is 27 has 2 children named lima,limb and groups the following leaves: lima,limb
31 whose parent is 30 has 2 children named spi,sfi and groups the following leaves: spi,sfi
33 whose parent is 32 has 2 children named kme,ame and groups the following leaves: kme,ame
32 whose parent is 30 has 2 children named eqc,33 and groups the following leaves: eqc,kme,ame
30 whose parent is 29 has 2 children named 31,32 and groups the following leaves: spi,sfi,eqc,kme,ame
36 whose parent is 35 has 2 children named tva,tvb and groups the following leaves: tva,tvb
35 whose parent is 34 has 2 children named fxf,36 and groups the following leaves: fxf,tva,tvb
41 whose parent is 40 has 2 children named qq,rr and groups the following leaves: qq,rr
40 whose parent is 39 has 2 children named mrb,41 and groups the following leaves: mrb,qq,rr
39 whose parent is 38 has 2 children named 40,sgn and groups the following leaves: sgn,mrb,qq,rr
38 whose parent is 37 has 2 children named cjk,39 and groups the following leaves: cjk,sgn,mrb,qq,rr
37 whose parent is 34 has 2 children named fxe,38 and groups the following leaves: fxe,cjk,sgn,mrb,qq,rr
34 whose parent is 29 has 2 children named 35,37 and groups the following leaves: fxf,fxe,tva,tvb,cjk,sgn,mrb,qq,rr
29 whose parent is 27 has 2 children named 30,34 and groups the following leaves: spi,sfi,eqc,fxf,fxe,kme,ame,tva,tvb,cjk,sgn,mrb,qq,rr
27 whose parent is 25 has 2 children named 28,29 and groups the following leaves: lima,limb,spi,sfi,eqc,fxf,fxe,kme,ame,tva,tvb,cjk,sgn,mrb,qq,rr
25 whose parent is 24 has 2 children named 26,27 and groups the following leaves: xa,xb,lima,limb,spi,sfi,eqc,fxf,fxe,kme,ame,tva,tvb,cjk,sgn,mrb,qq,rr
24 whose parent is 22 has 2 children named abc,25 and groups the following leaves: abc,xa,xb,lima,limb,spi,sfi,eqc,fxf,fxe,kme,ame,tva,tvb,cjk,sgn,mrb,qq,rr
22 who is the root of the tree has 2 children named 23,24 and groups the following leaves: ar,tk,abc,xa,xb,lima,limb,spi,sfi,eqc,fxf,fxe,kme,ame,tva,tvb,cjk,sgn,mrb,qq,rr
ADD COMMENTlink written 9.4 years ago by jhc2.9k
4
gravatar for DG
9.4 years ago by
DG7.2k
DG7.2k wrote:

No need to reinvent the wheel. If you are coding in Perl use BioPerl's Phylogenetic Tree modules to take care of the tree parsing. Then you can focus on whatever you want to do with this information. Bioperl will store the tree in an appropriate data structure, so for all nodes you can get all descendants of that node.

ADD COMMENTlink written 9.4 years ago by DG7.2k

Hey, thanks. Do you know a script compatible with BioPerl modules that would do what I want?

ADD REPLYlink written 9.4 years ago by User 194080

The [?]Bioperl Phylogenetics and Analysis Scrapbook[?] has a code snippet for returning all Clades in a tree that should be useful for you.

ADD REPLYlink written 9.4 years ago by DG7.2k

The Bioperl Phylogenetics and Analysis Scrapbook has a code snippet here: http://www.bioperl.org/wiki/Finding_all_clades_represented_in_a_tree that should be useful. It returns all Clades in a tree. This will only show the leaf taxa that form all possible clades but could easily be modified to show the names of internal nodes as well if desired.

ADD REPLYlink written 9.4 years ago by DG7.2k
3
gravatar for Pierre Lindenbaum
9.4 years ago by
France/Nantes/Institut du Thorax - INSERM UMR1087
Pierre Lindenbaum131k wrote:

What you need is a lexer/parser like LEX/YACC/FLEX/Bison or javacc.

here is a simple implementation using javacc:

compile:

javacc Biostar10123.jj
javac Biostar10123.java

execute

$ echo "((ar, tk) 23 , (abc, ((xa, xb) 26 , ((lima, limb) 28 , (((spi, sfi) 31 , (eqc, (kme, ame) 33 ) 32 ) 30 , ((fxf, (tva, tvb) 36 ) 35 , (fxe, (cjk, ((mrb, (qq, rr) 41 ) 40 , sgn) 39 ) 38 ) 37 ) 34 ) 29 ) 27 ) 25 ) 24 ) 22 ;" |\
java Biostar10123

Node 22 includes nodes Node 23 includes nodes 'ar' and 'tk' and Node 24 includes nodes 'abc' and Node 25 includes nodes Node 26 includes nodes 'xa' and 'xb' and Node 27 includes nodes Node 28 includes nodes 'lima' and 'limb' and Node 29 includes nodes Node 30 includes nodes Node 31 includes nodes 'spi' and 'sfi' and Node 32 includes nodes 'eqc' and Node 33 includes nodes 'kme' and 'ame'Node 33 includes nodes 'kme' and 'ame'
Node 31 includes nodes 'spi' and 'sfi'
Node 32 includes nodes 'eqc' and Node 33 includes nodes 'kme' and 'ame'
Node 33 includes nodes 'kme' and 'ame' and Node 34 includes nodes Node 35 includes nodes 'fxf' and Node 36 includes nodes 'tva' and 'tvb'Node 36 includes nodes 'tva' and 'tvb' and Node 37 includes nodes 'fxe' and Node 38 includes nodes 'cjk' and Node 39 includes nodes Node 40 includes nodes 'mrb' and Node 41 includes nodes 'qq' and 'rr'Node 41 includes nodes 'qq' and 'rr' and 'sgn'Node 40 includes nodes 'mrb' and Node 41 includes nodes 'qq' and 'rr'
Node 41 includes nodes 'qq' and 'rr'
Node 39 includes nodes Node 40 includes nodes 'mrb' and Node 41 includes nodes 'qq' and 'rr'Node 41 includes nodes 'qq' and 'rr'
(...)
ADD COMMENTlink modified 5.6 years ago • written 9.4 years ago by Pierre Lindenbaum131k
2

That's true, writing the parsers can be fun and a good learning experience I won't deny that :) But as a personal philosophy I think we should be supporting the open Bio coding communities as much as possible.

ADD REPLYlink written 9.4 years ago by DG7.2k
1

"Why reinvent the wheel by writing a new parser?" Writing a parser is FUN + NO dependencies + did I say that writing a parser is FUN ? :-)

ADD REPLYlink written 9.4 years ago by Pierre Lindenbaum131k

Thanks Pierre. I'm downloading Netbeans now to give a try with this.

ADD REPLYlink written 9.4 years ago by User 194080

Thanks Pierre but I could not run it. Can you give me a simple instruction for how to use this implementation?

ADD REPLYlink written 9.4 years ago by User 194080

Perhaps you have to do a "apt-get install javacc" or download and install javacc before running it (it works for me).

By the way, thanks for this post, I will dig a bit on javacc, it will be useful for me.

ADD REPLYlink written 9.4 years ago by Fred750

I downloaded javacc from its website, gunzipped and then tarred. I saved the script on the top as Biostar10123.java, then runned javac Biostar10123.java - it returns 23 errors. And when I try to execute, I get the following error:

Exception in thread "main" java.lang.NoClassDefFoundError: Biostar10123 Caused by: java.lang.ClassNotFoundException: Biostar10123 at java.net.URLClassLoader$1.run(URLClassLoader.java:202) at java.security.AccessController.doPrivileged(Native Method) at java.net.URLClassLoader.findClass(URLClassLoader.java:190) at java.lang.ClassLoader.loadClass(ClassLoader.jav

ADD REPLYlink written 9.4 years ago by User 194080

No the "script" should be called "Biostar10123.jj" not " Biostar10123.java". see my "Compile" paragraph

ADD REPLYlink written 9.4 years ago by Pierre Lindenbaum131k

Why reinvent the wheel by writing a new parser? The tree parsers for Bioperl, Biopython, and Biojava should all do the job and do it well, and can handle any sort of valid newick format tree (and many also support nexus and phyloxml tree files as well. Makes any resulting code much more reusable and will work on non-strictly bifurcating trees as well.

ADD REPLYlink written 9.4 years ago by DG7.2k

Unless, like me, you want to work in Objective C. I would kill for a nice newick parser (or a consistent and speedy algorithm for parsing across OpenBio). I'm currently messing around with ParseKit, though (http://www.parsekit.com).

ADD REPLYlink written 9.1 years ago by Chris F.10
Please log in to add an answer.

Help
Access

Use of this site constitutes acceptance of our User Agreement and Privacy Policy.
Powered by Biostar version 2.3.0
Traffic: 1435 users visited in the last hour