Algorithm For Rooting A Phylogenetic Tree

Question

[Zeke]

I'm creating a web application and one of the features is visualizing phylogenetic trees. The application is mainly written in JavaScript, and I am using jsPhyloSVG to draw the trees from Newick files that are provided.

One of the things that users need to be able to do is to root the tree on a given leaf/node. JsPhyloSVG doesn't provide functionality to do that - it just draws a tree from a Newick file. I'd like to create a function that takes as input a Newick file and a chosen node and produces as output the Newick file for that tree, rooted on that node. Then I could just use jsPhyloSVG to draw the new, rooted tree.

Using the 'retree' program in the Phylip package seems to work okay and as an example I can use it to root the following tree on N1:

((N1:0.5,N2:0.75),N3:0.3); ----> (N1:0.5,(N2:0.75,N3:0.30000):0.5);

I'd rather not use Phylip, however, because it would require a client-server interaction and it doesn't seem like this should be a terribly complex thing to implement in JavaScript for example. Can anyone point me in the direction of an algorithm for rooting a phylogenetic tree that I might be able to adapt to JavaScript or better yet, a JavaScript package that might provide this functionality?

Thanks.

EDIT - Response to lh3:

Thank you, your code worked very well but is there any way to recalculate the distance values when the tree is rerooted? They are missing from the result.

>>> tree = kn_parse("(((1984: 0.00178,676: 0.00059): 0,((((1494: 0,1486: 0): 0.00178,1080: 0.00119): 0,712: 0.00059): 0,1032: 0): 0): 0,960: 0.00297);")
Object { n_tips=8, error=0, node=[15], more...}
>>> tree.root = kn_reroot(tree.root,tree.node[1],-1.0)
Object { child=[2], d=-1, hl=false, more...}
>>> tree.node = kn_expand_node(tree.root)
[Object { parent={...}, child=[0], name="676", more...}, Object { parent={...}, child=[0], name="1984", more...}, Object { parent={...}, child=[0], name="960", more...}, Object { parent={...}, child=[0], name="1494", more...}, Object { parent={...}, child=[0], name="1486", more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { parent={...}, child=[0], name="1080", more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { parent={...}, child=[0], name="712", more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { parent={...}, child=[0], name="1032", more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { parent={...}, child=[2], d=NaN, more...}, Object { child=[2], d=-1, hl=false, more...}]
>>> nh_str = kn_write_nh(tree)
"(676, (1984, (960, ((((1494, 1486 ), 1080 ), 712 ), 1032 ) ) ) ) "

As you can see, the input had distance values but the output does not. Thanks again for your help.

EDIT #2:

Ok, that worked. Thanks again. However, I am getting the following error for some trees:

p.node is undefined 
[Break On This Error] p.node[k] = p.node[j]; 
knhx.js (line 339)

An example of a tree that causes this error is:

((((((AF225:0.00122,AF279:0.00061):0.00010,AF271:0.00061):0.00010,AF255:0.00010):0.00010,AF217:0.00010):0.00010,AF207:0.00010):0.00010,AF245:0.00010,(AF190:0.00122,AF263:0.00122):0.00010);

You can replicate this error by using jstree to draw the tree and then trying to reroot on AF225. I will attempt to debug as well.

[lh3]

Please remove the space after each colon. My NH parse is unfortunately does not work with that.

[lh3]

Please remove the space after each colon. My NH parse is unfortunately does not parse the branch length separated by space.

[Zeke]

Ok, that worked. Thanks again. However, I am getting the following error for some trees:

p.node is undefined [Break On This Error] p.node[k] = p.node[j]; knhx.js (line 339)

An example of a tree that causes this error is:

((((((AF225:0.00122,AF279:0.00061):0.00010,AF271:0.00061):0.00010,AF255:0.00010):0.00010,AF217:0.00010):0.00010,AF207:0.00010):0.00010,AF245:0.00010,(AF190:0.00122,AF263:0.00122):0.00010);

You can replicate this error by using jstree to draw the tree and then trying to reroot on AF225.

[Zeke]

Ok, that worked. Thanks again. However, I am getting an error for some trees. See my edit, thank you.

[lh3]

That is a very silly typo. Fixed. It is now working.

[Zeke]

perfect, thank you

Answer 1

[lh3]

Answer first. If you are looking for a javascript program, see my knhx.js and search "kn_reroot". As jsPhyloSVG parse the tree into a different structure, you cannot use my code directly, but you can get an idea how it is implemented. If you want to put the root at the i-th node in the input NH string [example: ((0,1)2,(3,4)5)6, the parent of (0,1) is the "2nd" node; root is always the last node], you can do this:

var tree = kn_parse(nh_str);
tree.root = kn_reroot(tree.root, tree.node[i], -1.0)
tree.node = kn_expand_node(tree.root)
nh_str = kn_write_nh(tree)

A working example: jstree. Note that it does not work in chrome due to a recent DOM change.

EDIT: For knhx.js, I have separated javascript from DOM interactions to make it a little javascript library for parsing and manipulating phylogenetic trees. The parser is literally translated from knhx.c and the tree manipulation from TreeBeST, so the APIs are all C-like.

[Zeke]

thank you, please see my edit

[Rutger Vos]

Because I am an avid internet archeologist (4.0 years later) and because I want to assign credit where it's due I'd like to add that I've ported this kn_reroot algorithm to Bio::Phylo, as per this commit: https://github.com/rvosa/bio-phylo/commit/7a82ee9cc7f04724d75b98deb4638356409a0c97 - thank you Dr. Li.

Answer 2

[Leszek]

I'm using ETE to work with trees and recommend it strongly! There is great documentation (f.e tree rooting). You can use JS (AJAX) and call ETE inside python scripts (modpython). This is how it's done in phylomeDB. In the latest version, there is a webplugin that creates interactive images - the same as in phylomeDB website. Exactly, what you need:)

[Zeke]

Thank you for the suggestion, I'll take a look at this