augur clades inheritance doesn't enforce inheritance

[jameshadfield]

In the mutation-definition TSV supplied to augur clades we can define a clade as inherited from another clade. For instance, the TSV line

Y	clade	X

means that clade Y inherits from clade X. Intuitively, I think that clade Y in the tree must be a descendant of clade X (or perhaps equal to it). The current implementation instead simply copies the clade-X defining mutations and adds them to the list of mutations used for clade Y. PR #1836 adds a (failing) test to demonstrate this, which I'll use here:

We have a very simple tree with mutations labelled on 3 branches:

and the following clades.tsv:

clade	gene	site	alt
# There's two options for clade X - each of the root's children
# match this. The upper clade "wins" as it has more descendants
X	nuc	1	T
# Clade Y "inherits" from clade X with an additional mutation.
# Intuitively, this means Y must be a descendent of X, however
# this isn't the way `augur clades` is currently implemented
Y	clade	X
Y	nuc	2	T

The resulting clades chosen are, IMO, wrong:

Here's what I think is correct:

[huddlej]

The cause of this bug seems to be the same as the cause of #1711, too: the fact "clades" aren't defined by hierarchical relationships but through inheritance of allele definitions from parent clades.

This practical example and the related PR really help clarify the essence of the problem.

[corneliusroemer]

This works as designed, but probably could be documented better.

I added the clade inheritance syntax as a tool to make the clades.tsv DRY and easier to maintain. It's syntactic sugar, doesn't change the underlying algorithm.

Looking at this through a feature lens: What's the use case for ensuring strict nesting and how would you expect it to work algorithmically? One ould add an option --strict-clade-nesting

[jameshadfield]

Looking at this through a feature lens: What's the use case for ensuring strict nesting

I guess I'd flip this and ask in what circumstances we'd want to specify Y as inheriting from X but not nesting within X? Enforcing inheritance should make it easier to find unique mutations since they only have to be unique in the context of the parent clade.

how would you expect it to work algorithmically?

We already construct a graph (tree) of the clade relationships, and then traverse this pre-order to assign clades. So for a child clade (e.g. Y above) it'd simply being a matter of restricting the search to all nodes downstream of the (already identified) clade X start node. (And probably include the start node of X in this search.) I can make a trial implementation on the linked PR.

[jameshadfield]

I can make a trial implementation on the linked PR.

Done in 81684d2.