Collapse Clades In A Newick Tree With Average Distance To Tips < X
3
9
Entering edit mode
10.4 years ago
a1ultima ▴ 840

I have a hierarchical tree in Newick format, such as:

(A:0.556705,(B:0.251059,C:0.251059):0.305646):0.556705;


I need to collapse clades (sub-trees) whose average distances to the tips (terminal nodes/tips/leaves) are less than a given value, x. Such that input and collapsed output are in Newick format. For example, if B and C in the above collapsed into BC, we get something like:

(A:0.556705,BC:0.556705):0.556705;


Is there a simple way to programmatically achieve this collapsing given any Newick tree (e.g. in Python)?

Thanks to jhc and Pierre Lindenbaum 's answers - for anybody who needs to know whether their solutions actually work or not, they converge to the same outcome given some very complex trees! Bravo

tree distance phylogeny • 7.6k views
7
Entering edit mode
10.4 years ago
jhc ★ 3.0k

I had a similar script using ETE. I just wrote a quick example to fit your question:

from ete2 import Tree
def mean(array):
return sum(array)/float(len(array))

def cache_distances(tree):
''' precalculate distances of all nodes to the root'''
node2rootdist = {tree:0}
for node in tree.iter_descendants('preorder'):
node2rootdist[node] = node.dist + node2rootdist[node.up]
return node2rootdist

def collapse(tree, min_dist):
# cache the tip content of each node to reduce the number of times the tree is traversed
node2tips = tree.get_cached_content()
root_distance = cache_distances(tree)

for node in tree.get_descendants('preorder'):
if not node.is_leaf():
avg_distance_to_tips = mean([root_distance[tip]-root_distance[node]
for tip in node2tips[node]])

if avg_distance_to_tips < min_dist:
# do whatever, ete support node annotation, deletion, labeling, etc.

# rename
node.name += ' COLLAPSED avg_d:%g {%s}' %(avg_distance_to_tips,
','.join([tip.name for tip in node2tips[node]]))
# label

# set drawing attribute so they look collapsed when displayed with tree.show()
node.img_style['draw_descendants'] = False

# etc...

# Example
t = Tree("((A,(B:0.1,C:0.1)i1:0.1)i2:0.5,((D:0.1,(E:0.1,F:0.1)i3:0.1)i4:0.5,G)i5:0.3);", format=1)
print t.get_ascii(attributes=["dist", 'name'])
#                  /-1.0, A
#           /0.5, i2
#          |      |       /-0.1, B
#          |       \0.1, i1
#          |              \-0.1, C
#-1.0, NoName
#          |              /-0.1, D
#          |       /0.5, i4
#          |      |      |       /-0.1, E
#           \0.3, i5      \0.1, i3
#                 |              \-0.1, F
#                 |
#                  \-1.0, G

# Now we collapse
collapse(t, 0.5)
print t.get_ascii(attributes=['name'])
#                                       /-A
#      /i2 COLLAPSED avg_d:0.466667 {C,A,B}
#     |                                  |                            /-B
#     |                                   \i1 COLLAPSED avg_d:0.1 {C,B}
#     |                                                               \-C
#-NoName
#     |                                      /-D
#     |   /i4 COLLAPSED avg_d:0.166667 {F,D,E}
#     |  |                                  |                            /-E
#      \i5                                   \i3 COLLAPSED avg_d:0.1 {F,E}
#        |                                                               \-F
#        |
#         \-G

# tree visualization will hide collapsed nodes
t.show()

# collapsed nodes are labeled, so you locate them and prune them
for n in t.search_nodes(collapsed=True):
for ch in n.get_children():
ch.detach()
print t
#   /-i2 COLLAPSED avg_d:0.466667 {C,A,B}
#--|
#  |   /-i4 COLLAPSED avg_d:0.166667 {F,D,E}
#   \-|
#      \-G

print t.write()
# and the the pruned newick
#(i2 COLLAPSED avg_d_0.466667 {C_A_B}:0.5,(i4 COLLAPSED avg_d_0.166667 {F_D_E}:0.5,G:1)1:0.3);

0
Entering edit mode

Aha, brilliant cheers!

0
Entering edit mode

Just wanted to say this has really helped, you deserve a medal!

0
Entering edit mode

Yep, just what I was looking for.

4
Entering edit mode
10.4 years ago
DG 7.3k

You can probably use the ETE python package, it is designed to manipulate, analyze, and visualize phylogenetic trees. One of the ETE tutorials is how to do dynamic node collapsing given any python function while traversing the tree and exporting the new newick format with collapsed nodes:

ETE2 Tutorial: Node Collapse While Traversing

1
Entering edit mode

cheers for the recommendation +1

1
Entering edit mode

good point! I forgot about my own examples in the tutorial. the section on 'stopping criteria' is also interesting for this type of problems: http://pythonhosted.org/ete2/tutorial/tutorial_trees.html#advanced-traversing-stopping-criteria

1
Entering edit mode
10.4 years ago

I wrote a javascript parser for newick using jison and put the converter in a html page.

It seems to work with your example:

0
Entering edit mode

brilliant! cheers +1