R Project Sprint 2023 - Dendrapply Refactor

[giscus[bot]]

R Project Sprint 2023 - Dendrapply Refactor

https://contributor.r-project.org/r-project-sprint-2023/projects/dendrapply-refactor/

[ahl27]

Just wanted to add a little more info here since I've been thinking about this--this project shouldn't take the entire sprint in time. If this completes with time to spare, I'd like to investigate improving other functionality with dendrogram objects. Examples of things I've identified thus far are adding a subset.dendrogram S3 method (this is relatively simple with the proposed dendrapply changes) and adding circular plotting for dendrogram objects.

I'm also definitely open to other suggestions and/or seeing if we can identify other opportunities for improvement during the sprint!

[rgentlem]

Hi Aidan, I would be happy to work with you on this. As a prelude it would be good to perhaps get some sense of what has been done in other packages and languages - likely there are others with similar objectives. Also scoping out what the inputs/outputs and functionality are in some sort of document that could be used to guide development could be useful.
Robert

[ahl27]

Hi Dr. Gentleman,

I'm ecstatic that you're interested in helping with this! I think some of the topics you mentioned are briefly addressed in the document submitted and the bugzilla report, but I will work on putting together a more comprehensive document on specifics and comparable implementations and post it here prior to the sprint.

-Aidan

[rgentlem]

got the doc - will read over it and get back to you...

…

On Thu, Aug 17, 2023 at 2:00 PM Aidan Lakshman ***@***.***> wrote: Hi Dr. Gentleman, I'm ecstatic that you're interested in helping with this! I think some of the topics you mentioned are briefly addressed in the document submitted and the bugzilla report, but I will work on putting together a more comprehensive document on specifics and comparable implementations and post it here prior to the sprint. -Aidan — Reply to this email directly, view it on GitHub <#6 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AC7TWA7YFMO7DXTFUXYUZQTXVZL3PANCNFSM6AAAAAAZ2CCWAY> . You are receiving this because you commented.Message ID: ***@***.*** com>

-- Robert Gentleman ***@***.***

[rgentlem]

Dendrograms are a very special kind of graph and it might be better to use existing code and algorithms. Could you describe some use cases - just to get a sense of scale (how many leaves and how deep?). What do you want to do to each node? Are internal nodes interesting or do you need to get to the leaves to do something? How many leaves do you want to handle?

Are you sure you want to do this in custom C, there is the Boost library eg https://www.boost.org, which has some high quality C++ code. Which is one alternative. I certainly agree that the list like structure used in the current dendrogram code might not be the best one for traversal. It has been a few years since I interacted with that code base, but it has been very good and well maintained.

If you look at either the graph package (or I suspect the igraph package) you will see implementations of DFS and BFS search. It might be worth trying to look at more general approaches to graph traversal, especially where high quality algorithms already exist. And also considering whether you want either of those, both(?) or something else.
I am not so sure traversal is always needed - sometimes you just want to do things to the leaves - and that can often be done by getting the leaves and then just a standard apply.

I admit to not having looked at any of the phylogeny code yet - but will try to track that down.

[ahl27]

Dendrograms are a very special kind of graph and it might be better to use existing code and algorithms. Could you describe some use cases...?

The dendrogram objects are essentially replicating tree structures in R, but R unfortunately doesn't easily handle linked list-style objects, so it turns into this nested list structure. This makes working with them a little unintuitive, at least from my and collaborators' experience.

The main goal I was trying to solve with this proposal/bugzilla was refactoring the recursion out of the dendrapply call, which can cause stack overflow issues for really large/deep trees (especially on smaller machines). The scale I'm usually working at for these kinds of applications in my personal research are dendrograms from around ten leaves to over 5,000 leaves, but I was mainly aiming to make a general purpose implementation of dendrapply that could work for any size tree without depending on a recursive call.

What do you want to do to each node? Are internal nodes interesting or do you need to get to the leaves to do something?...I am not so sure traversal is always needed - sometimes you just want to do things to the leaves - and that can often be done by getting the leaves and then just a standard apply.

The overall goal is getting a performance improvement while maintaining the functionality of dendrapply, so everything dendrapply currently does should still be preserved in the new implementation. The added traversal functionality came about because it was fairly simple to include once dendrapply was refactored. My understanding is that dendrapply is currently the only apply family function that can operate on the internal nodes in a single call; if just the leaves are needed, rapply should fulfill that functionality.

One big feature missing from dendrapply is a way to change nodes based on its children. Calculating Fitch Parsimony for binary states on a phylogeny is a fairly simple example that's very challenging to implement with the current structure of dendrogram objects, though newer users may think that it's doable with dendrapply. This unfortunately is not the case due to how dendrapply traverses the tree. It's also not possible to change child nodes' attributes based on parent nodes' attributes in dendrapply.

If this implementation is fixed into something acceptable, it would open the door to adding a lot of functionality to dendrogram objects in R. For example, a subset.dendrogram can be implemented very cleanly (see here for an example), and the result would be a much more intuitive user experience than trying to get cut.dendrogram to work. This functionality is provided in dendextend::prune.dendrogram, but it could be simplified significantly with a dendrapply that could handle this use-case.

It might be worth trying to look at more general approaches to graph traversal, especially where high quality algorithms already exist. And also considering whether you want either of those, both(?) or something else.

This is a good point--I had implemented my tree traversal according to the best algorithms I was aware of...basically creating a linked list, and then adding to and traversing it. Using a queue structure creates a BFS, and a stack creates a DFS/post-order traversal. I don't think the core implementation of the refactor is that complicated, but unfortunately a lot of complexity is added due to interfacing across R and C...making sure we don't lose nodes due to being objects becoming unprotected quickly becomes difficult. There's also a bit of added complexity due to weirdness in the core implementation--this particular case from the unit tests gave me a lot of trouble:

D <- as.dendrogram(hclust(dist(cbind(setNames(c(0,1,4), LETTERS[1:3])))))
dendrapply(D, labels)

If you look at either the graph package (or I suspect the igraph package) you will see implementations of DFS and BFS search.

My understanding of graph/igraph (and also of phylogenetic packages like ape and phytools) is that they get around the limitations of nested list structures by building custom classes/structures that are easier to work with. I'd like to avoid that route if possible, since the dendrogram object is used in a lot of places in R. I think dendextend is a good package to look at for example implementations; a lot of their codebase is workarounds to make dendrapply perform operations in particular ways.

Are you sure you want to do this in custom C, there is the Boost library eg https://www.boost.org/, which has some high quality C++ code. Which is one alternative.

I'm not sure. I know there's quite a bit of added maintenance cost to introducing more C code, but the classic tree traversal algorithms are significantly simpler to implement in C than in R. I'm worried about losing performance by writing only in R, but if it's possible to do then that solution would likely be better (and easier to understand!). Is C++ code allowed for submissions to core R libraries?

[mmaechler]

TLDR: I am happy to collaborate next week

Robert (@rgentlem) and I have e-talked about this a bit. As he won't be present physically next week and both Aidan @ahl27 and I are planning to and I had originally created the function dendrapply() and added it to R (and also worked on improving it..) I will "sponsor" / take over to collaborate with Aidan on this. I think it is clear that this must be addressed; and I do note that the proposal also mentions Tal Galil's {dendrextend} .. the package which indeed made R's stats' dendrogram objects already more useful.

And yes, using Boost from base R's stats is currently out of the question, even using the Matrix package's sparse matrices for this may be cumbersome: stats depending on Matrix which currently strongly depends on stats.

[ahl27]

amazing, looking forward to connecting with you in the UK! Robert and I are planning to connect virtually this week as well, and I'm confident that all of this will result in a good solution that can be implemented/revised/refined during the sprint :)

[KlausVigo]

Hi Aidan,
I totally agree that traversing dendrogramobjects is slow and a better workflow is needed. But now an unpopular and totally biased opinion, and I have to confess that I am co-author to ape and contributed to most packages I will mention below. I think you make your life easier adapting the phylo format from the ape package instead of the dendogram format. Especially in the phylogenetic R community, phylo is the de facto standard (https://cran.r-project.org/web/views/Phylogenetics.html).
If you want to give it a try dendextend::as.phylo.dendrogram is your friend.

phylo has also its quirks as the ape package is on CRAN since 2002, but has hundreds of reverse dependencies and a broad user base and a lot of functionality built on top of it. It is likely more widely used than dendrogram and most functions are not recursive and much faster. I know it is not base R, but ape has mostly R base dependencies and you can blame me for the Rcpp dependency. But the phylo class defined in ape is maybe one of the objects in R which comes most closely to a base R object.

For pretty much all the use cases you have described, there are already functions available:

E.g. ape alone offers three obvious functions to subset a tree (keep.tip, drop.tip and extract.clade). A lot of other packages have more specific functions to do this on whatever criteria.

And there exist at least three different widely used implementations of circular plots for phylo objects with different focus:
A generic plot.phylo, plot(x, type="fan") in ape, plotTree(tree, type="fan") in phytools and ggtree(tree, layout="circular") in ggtree offering ggplot2 style. All these packages have been cited thousands of times.

Also dendrogram objects seem usually to derive from hclust objects. It might be worth noting that "average linkage" also known as "UPGMA" was introduced to estimate phylogentic trees (Sokal & Michener 1958) and just later adopted for clustering. Now the problem is that hclust objects are binary, ultrametric, rooted trees.

However phylogenetic trees might

• have multi-furcations (consensus trees), .i.e are not binary,
• do not have a root, e.g. parsimony trees derived with the Fitch algorithm, NJ and many maximum likelihood implementations (RAxML, iqtree, PhyML),
• be tip dated,
• have no edge weights,
• might be more general graphs not trees. ape contains a class evonet which is derived from phylo objects to represent explicit phylogentic networks and my own package phangorn contains another class extending phylo to represent split graphs.

I had mixed experiences even getting some of these into a dendrogram object. And some functions in dendextent seem not to have been properly tested if trees are not binary or ultrametric. But this was years ago and I cannot comment if things improved since then.

Probably it would be a good idea to improve dendextend::as.phylo.dendrogram and also ape::as.dendrogram.phylo and promote it more and possibly move both functions into stats. And trying to drop as many of the implicit the restrictions on the way e.g. ultrametric, binary. ape::as.dendrogram.phylo transforms via an hclust object and this is likely too restrictive.

[ahl27]

Hi Klaus,

Thanks for your comment! I'm a big fan of ape, I use it often for benchmarking some of my work. I'm happy with the amount of traction this project proposal is getting; I think the discussion is incredibly useful for it overall.

I'm very familiar with the ape/phytools/... system. While my lab falls within the minority of people that aren't using phylo objects for phylogenetics, I'm definitely aware of how powerful the package is for these kinds of analyses. I'm also not inherently opposed to your point on considering adopting the phylo object framework. Our most recent release of DECIPHER/SynExtend adds a lot of the capabilities you mention to building trees using dendrogram objects rather than phylo, if you ever felt the urge to try using them for phylogenetics again 😂. Unrooted trees are definitely tricky to handle with dendrograms.

To your points on this project--I think there are a couple of counterpoints for consideration.

First is regarding the state of the dendrogram object. Robert also mentioned that he thinks overhauling dendrogram could be helpful for future capabilities. I definitely agree with that point, but it also has to be considered that reworking dendrogram objects is going to come at the cost of a nontrivial amount of development and continued maintenance over time. Maintaining backwards compatibility with existing dendrogram tools while implementing a new framework for nested list structures seems like a large task to me, but I could be overestimating the workload. I don't disagree that it would probably make trees easier to work with, specifically for phylogenetics, but I'm not sure if those applications are relevant enough to the broader R community to merit moving large portions of the ape ecosystem into stats.

My personal view is that having that package set be externally maintained is good overall for R and phylogenetics, but I'm happy to discuss that more (either virtually or in-person, if you'll be at the sprint). The larger point here is I'm not convinced that updates to dendrogram are within the scope of this project, but I'm happy to revisit it in the future. If your point was to say that phylo objects should be integrated into R alongside dendrogram objects--I'm not sure that that makes sense for stats, but I'd be happy to discuss more with you and/or R-core.

The second point is that dendrapply specifically has merit to be updated regardless of the existence of other tools for phylogenetics. dendrapply is currently the only way to apply a function to all levels of a nested list structure. That's great for a lot of phylogenetic methods, but it's also useful for people just generally working with dendrogram objects (which don't have to be phylogenetic in nature!). I think it would be fine to direct people to use ape and family for more intensive phylogenetics, but I'd like to see base functionality in stats at least improved to point where the help page for dendrapply doesn't list it as an experimental function. dendrogram objects provide general tree-like structures, and that's a broadly useful data structure for many non-phylogenetic algorithms.

---

I also think it would help to clarify the goal of this project. This project started specifically because the help page for dendrapply asked for updated implementations to remove the recursion in the function. While I typically use phylogenetics as a go-to example for things one could do with dendrapply, the project is not focused on phylogenetics. Rather, the short term goal is to "finish" the implementation of dendrapply (quotations because the current implementation does certainly work), and the long term goal is simply to add support for dendrogram objects. Adding support doesn't mean that I'd like to see ape/phytools/dendextend subsumed into stats, it just means I'd like to see functions you'd expect to find for built-in types to be present.

When we look at other built in objects like lists or vectors, they have ways to construct them, ways to subset them, and ways to apply functions to them. dendrograms have a way to construct them, and relatively unintuitive ways to subset and apply functions to them. My personal vision for this looks like having a dendrapply that feels like it's applying a function to the "General Tree Structure" that dendrogram claims to be, and add in some base capabilities to work with those objects. More targeted functionality for specific fields can live within external packages, and these improvements can help simplify package builders' efforts (e.g. having a postorder application method for dendrapply could make a lot of the code in dendextend significantly more concise).

I'm not completely decided on what those "base capabilities" look like. I threw out circular plotting because I think it's an interesting feature that would be a fairly easy addition to the current plotting system, but in my mind the only main two things that are really missing are a better *apply and some leaf-based subset method. Better *apply because nested list structures are extremely difficult to deal with, and dendrapply provides a better way to handle them. That function needs to be relatively powerful to try to keep dendrogram objects from being extremely unwieldy. Leaf-based subset methods because dendrogram did grow out of hclust, and sometimes it's of interest to look at a subset of the clustered datapoints. That's currently extremely difficult for individuals in different clades, since dendrogram subsetting is purely top-down rather than bottom-up.

However, all of that is definitely debatable. One of the reasons I really wanted to come to this sprint was to discuss if those are reasonable expectations, or if we should be doing something different.

dendrogram objects are (in my mind) in a bit of a weird place in R at the moment, and having discussions like these could help clarify what they should look like in the future. My personal bias is to err on the side of small changes that preserve current functionality, since that seem to be the overall design practice of R-core...but I'm also honestly not sure how much dendrogram objects are even used by the R community. Maybe it is a good opportunity to overhaul the implementation. If it came to that I'd be happy to take the lead on implementation and maintenance, but a change like that would probably need a great deal more discussion prior to implementation.

Thanks again for taking the time to give input on this. Looking forward to hearing from you, and please come say hi if you'll be attending the sprint!

-Aidan

[ahl27]

See latest update at #29 (comment)