Ultrametric tree generation

[Pythonic]

Hello everyone!


I found ETE to be a great package!!!. One question, I been looking for
some way to generate ULTRAMETRIC trees. I know ETE provides a
populate() method to create a random tree. But I need trees that are
ultrametric (meaning the taxons have evolved under the molecular clock
hypothesis). Please let me know if you know anything about this.

[Jaime Huerta Cepas]

Hi Pythonic,
welcome to the list! There are currently no functions to generate ultrametic trees in the ETE core, however it wouldn't be difficult to implement it.
Here you have something I have just written to convert any tree to ultrametric topology. I think is working as expected, but a double check would be nice. If you test it, improve it, or create your own function, I would be willing to include it as part of next ETE releases.


from ete2 import Tree,  faces

def convert_to_ultrametric(root, tree_length, strategy="balanced"):
    ''' Converts a tree to ultrametric topology (all leaves have the
    same distance two root).'''

    # pre-calculate how many splits remain under each node
    node2max_depth = {}
    for node in t.traverse("postorder"):
        if not node.is_leaf():
            max_depth = max([node2max_depth[c] for c in node.children]) + 1
            node2max_depth[node] = max_depth
        else:
            node2max_depth[node] = 1
    node2dist = {root: 0.0}
    tree_length = float(tree_length)
    step = tree_length / node2max_depth[t]
    for node in t.iter_descendants("preorder"):
        if strategy == "balanced":
            node.dist = (tree_length - node2dist[node.up]) / node2max_depth[node]
            node2dist[node] =  node.dist + node2dist[node.up]
        elif strategy == "fixed":
            if not node.is_leaf():
                node.dist = step
            else:
                node.dist = tree_length - ((node2dist[node.up]) * step)
            node2dist[node] = node2dist[node.up] + 1
        node.dist = node.dist

def ultrametric_layout(node):
    # node balls consume space in the tree picture, so partitions with
    # many splits are not well aligned with partitions having less
    # splits. To solve it,  I set node sphere size to 0
    node.img_style["size"] = 0
    if node.is_leaf():
        faces.add_face_to_node(nameFace, node, 0)
       
if __name__ == "__main__":
    t =  Tree()
    # Creates a random tree (not ultrametric)
    t.populate(100)

    # Convert tree to a ultrametric topology in which distance from
    # leaf to root is always 100. Two strategies are available:
    # balanced or fixed
    convert_to_ultrametric(t, 1.0, "balanced")

    # Print distances from all leaves to root. Due to precision issues
    # with the float type.  Branch lengths may show differences at
    # high precision levels, that's way I round to 6 decimal
    # positions.
    print "distance from all leaves to root:", \
          set([round(l.get_distance(t), 6)for l in t.iter_leaves()])
    nameFace = faces.AttrFace("name")
    t.show(ultrametric_layout)

Jaime

[Stefan Helfrich]

Hey Jaime,

I have tried to use your ultrametric_layout function, but the result isn't really as satisfying as I had hoped for. The problem with the alignment of the leaf nodes cannot be tackled easily, I guess? There is a pdf attached to this post showing the problem I am talking about.

Hence, it would be great to have a ZeroNodeStyle or NoneNodeStyle. So far I haven't found the connection between the NodeStyle.size attribute and the nodeRegion in RectPartition, otherwise I would have come up with a solution myself ;)

Cheers,

Stefan

[Jaime Huerta Cepas]

Stefan,
The problem is that the default width for vertical lines is still 1, so get this unbalance in ultrametric tree pictures. The following code should prevent the effect that you have found.
(Note that you can also add faces to leaves using the "aligned" position, so you can have aligned names even in non-ultrametric trees.)


from ete2a1 import Tree

def ultrametric(node):
    node.img_style["size"]=0
    node.img_style["vt_line_width"]=0
    node.name = "N"
    print node.dist

t = Tree()
t.populate(10)
t.convert_to_ultrametric(10)
t.show(ultrametric)

[Stefan Helfrich]

Thanks,

this also solves the issue with the gaps in the tree representation. Although now the width of a vertical line *1px) denoting a branching event is not the same as the horizontal lines (looks like 2px) anymore ..

[Stefan Helfrich]

Ok. Skip it. Setting the hz_line_width to 0 solves the problem - could have thought of that earlier .. But now I would be interested in why the lines are drawn at all?

[Jaime Huerta Cepas]

It is a Qt4 drawing library issue. They say:
"A line width of zero indicates a cosmetic pen. This means that the pen width is always drawn one pixel wide, independent of the transformation set on the painter."

I could always implement a "None" value to set and invisible line.

[Stefan Helfrich]

This just seems to be a workaround for this specific case ...

Image 1 shows the case where hz_line_width and vt_line_width are 1 and the border.width of the rectangles is 1. Image 2 shows hz and vt are 0 and an border.width is 1 ... this is kind of confusing

[Stefan Helfrich]

Ok, got the problem. However, a border width of 0 really results in a non-existing border. This is where the it really gets confusing in my opinion ..

[Jaime Huerta Cepas]

Opposite to tree branches, face borders do have the feature of being invisible. You are right that current code does not differentiate between border=0 and border=None. I don't really think this is so limiting or confusing but, anyway, it is an easy fix and it is already solved in the last build (ete2a1rev421).

thanks for reporting.
Jaime