Allow variable branch lengths in tree layout

[jdidion]

I would love to use D3 for creating phylogenetic trees. A phylogenetic tree is basically a hierarchical tree where each node specifies its distance from its parent, and this distance must be reflected by the length of the branch. If there is currently a way to do this with D3, I can't figure it out.

As a side note, the standard format for phylogenetic trees is Newick (http://en.wikipedia.org/wiki/Newick_format). I would be happy to write a function to transform a Newick tree to an appropriate JSON object that could then be used with D3. This would open up D3 to be used by the bioinformatics community and possibly get you some citations in scientific publications when people create trees using D3.

[mbostock]

@jasondavies has implemented phylogenetic trees using D3, using the Newick format even. See his example:

http://www.jasondavies.com/tree-of-life/

[jasondavies]

Yep, it uses https://github.com/jasondavies/newick.js, let me know if you have any questions!

[jdidion]

This is cool, and I'm glad to see there's a newick class for javascript (nice work Jason!). However, the tree does not appear to be honoring the branch lengths defined in life.txt. At every level of the tree, the children are displayed as equidistant from the parent when this is not actually the case.

Also, I'd like to draw a radial (unrooted) tree rather than a circular one, but the radial-tree example doesn't seem to work if I use the JSON object created by newick.js rather than the flare.json object.

Thanks for the help!

[jasondavies]

Ah, excellent point. Turns out it was quite easy to adjust to take into account the branch lengths from the tree data:

function phylo(n, offset) {
  if (n.data && n.data.length != null)
    offset += n.data.length * 115;
  n.y = offset;
  if (n.children)
    n.children.forEach(function(n) {
      phylo(n, offset);
    });
}

Here we are overwriting the y values from the cluster layout with our own, derived from the parsed data.

I've updated http://www.jasondavies.com/tree-of-life/ to show how this works.

[jdidion]

This is great, Jason. However, I'd like to leave the bug open as what I really want is a radial tree with variable branch lengths. I know this is not trivial as I've already wasted a day trying to figure out how to implement it. I got it working to a point (I basically had to translate the x/y values from "distance from root" to "distance from parent") but for trees with more than one or two levels of depth the branches and labels start overlapping. I think a new layout or a significant refactoring of the base hierarchy layout would be required. From a user perspective, the easiest might be to have a method similar to separation that controls the distance between length of a link (i.e. distance between parent and child).

[jasondavies]

Yes, a configurable radial (or y) separation, along with a configurable radial distance could indeed be useful for users instead of having to roll their own. I will put up an example of how this might look when I get a chance.

[KoRMaK]

Along these lines, is there a way to increase the branch lengths? I don't mind if they are all the same length, I just need to increase each of mine by some pixels. I've been reading all over but can't figure it out. Any help would be much appreciated!

[pavo]

Kueda has implemented circular dendrograms http://bl.ocks.org/1036776.

[Chris-Eisenhart]

Hmm this seems to be implemented with the d3 heirarchy class 'cluster' not the d3 heirarchy class 'tree'. I am trying to do variable link lengths on the 'tree' layout, any suggestions?

[mbostock]

Here’s a newer example using the cluster layout:

You can’t apply the same strategy with the “tidy” tree layout because that algorithm assumes that the tree is layered (i.e., each node at a given depth in the tree shares the same y-position in the resulting layout). See #2571 and d3-flextree for an implementation of a non-layered trees, as in Drawing Non-layered Tidy Trees in Linear Time by A.J. van der Ploeg.