biocore / biocore/empress

Clean up arc approximations for big trees with polytomies

Open
#463 0 comments 0 reactions 0 assignees View on GitHub
bug
Dominant language
JavaScript
Stars
56
Forks
32
PR merge metrics
No merged PRs in 30d

Description

Relates to the same tree as discussed in #462: https://twitter.com/yoshikivb/status/1336848912364175362

This tree has a lot of [polytomies](https://en.wikipedia.org/wiki/Polytomy), where one internal node has many (> 2) child nodes. (We support polytomies in EMPress, but in practice I think most of the 16S/shotgun trees we've been working with are limited to internal nodes with at most 1 or 2 children.)

The issue is that, when you zoom in closely in the circular layout, many of the internal nodes with polytomies seem "disconnected" from their child nodes' start points:

![arcthing](https://user-images.githubusercontent.com/4177727/101952010-d215f480-3bac-11eb-91ff-16944a700a97.gif)

This is because the current code ensures that the "leftmost" and "rightmost" children of an internal node are connected, but if there are a zillion other children then the approximation will very slightly miss them. (The problem gets extra difficult when there are hundreds of thousands of tips, as there are in this tree, since now there is more room for precision issues.)

We may be able to handle this by biting the bullet and actually trying to figure out a way to draw "perfect" arcs using WebGL (... idk how that'd work), but probably an easier way to handle this will just be modifying the arc generation code (e.g. [this stuff](https://github.com/biocore/empress/blob/1b7a8d3a8da2c2a980ffc12f0f04ea6220d7e5e5/empress/support_files/js/empress.js#L665-L693)) to draw arcs in such a way that the children of every internal node are connected.

The way I imagine this working is, for each internal node, we iterate over all of its children (if there are > 1 children), and draw arcs between the "start point" of each child node and the next child node, using the same approximation stuff as is currently done. I guess we should also consider the "endpoint" of the internal node as another point to connect with the arc. I don't think this should be a big performance hit, and it'll guarantee that the tree looks as expected.

Shoddy diagram of how this would work, for an internal node with four children:

![IMG_20201211_124249](https://user-images.githubusercontent.com/4177727/101953139-b1e73500-3bae-11eb-88a9-6bb0acd980e8.jpg)

Contributor guide

Open the contributing guide

Research direction

Start in empress/support_files/js/empress.js around the arc generation code at lines 665-693, using the linked tree and the discussion in issue #462 as context. Inspect how arcs connect the leftmost and rightmost children, then verify the circular layout on a tree with large polytomies. Done means every child start point is connected to the internal node's arc without an unacceptable performance hit.

Written by the indexing model from the issue text.

Assessment

Tech stack
javascript
Domain
data-visualization
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.