Implement Tree.has_isolated_samples

[jeromekelleher]

The topological definition of missing data is that we have an isolated sample (a sample node with no children or parents). #1894 added a quick definition of this to the Python API, but we should implement it in C and test it out to make sure it's correct in various corner cases.

   def has_isolated_samples(self):
          for root in self.roots:
            if self.left_child(root) == NULL:
                return True
        return False

Some that occur to me:

1. Is this correct when we have a tree sequence with a single sample node and no edges? (Yes, I think?)
2. What about the empty tree sequence? (Do we get trees empty trees returned by trees()?)
3. What if we have non-sample topology below this root? Is this considered isolated or not?

[jeromekelleher]

See also #1896 - the implementation of filling in missing data in the alignment should guide us on what the best definition of topological missingness is.

[petrelharp]

On this topic, recall that in this discussion I think we said that an isolated sample with a mutation above it (i.e., on the branch-thats-not-in-the-edge-table above it) should not be missing. This is important becaues otherwise we have no way to say that a sample is genotyped and yet not related to any other samples.

[petrelharp]

Some more discussion of corner cases in this thread, pointing out that simplify can turn non-missing into missing (by removing a unary root).

[jeromekelleher]

On this topic, recall that in this discussion I think we said that an isolated sample with a mutation above it (i.e., on the branch-thats-not-in-the-edge-table above it) should not be missing. This is important becaues otherwise we have no way to say that a sample is genotyped and yet not related to any other samples.

Yes, agreed. But, it gets a bit hairy when you start thinking about alignments. Suppose we have a sequence of length 10, and a tree in which node a is an isolated sample on the full genome. There is two sites, and 0 and 9. At site 0, there is a mutation over a.

Is a missing data at site 1 then? Does the existence of a mutation above a node anywhere indicate that it is non-missing everywhere, or just at that site? Under the current definition it's just at the present site, as it'll be marked as -1 at site 9 (and by implication, it should be missing at all the reference sites in between 0 and 9 too).

This probably isn't the place to get into it, but it's tricky!

[jeromekelleher]

So anyway, my point is that Tree.has_isolated_samples is a well defined operation, which may indicate the presence of missing data, but will be a useful operation to have defined when we start wrangling with these details.

[hyanwong]

Is this essentially a dupe of #362? There I suggested we might want to return a count of missing samples, rather than a boolean, but I guess they are very similar operations.

[jeromekelleher]

I don't think so - has_isolated_samples can return after the first isolated root is found, whereas #362 wants an efficient way of counting them. So closely related, but has_isolated_samples is an easier operation to implement (well).

[benjeffery]

Do we remove the undoumented _has_isolated_samples?

[jeromekelleher]

Are we using it internally? I'd be inclined to not change things at this point unless there's a good reason

[benjeffery]

Turns out we are using it in alignments and the divmat tests, so keeping it.

Closing for inactivity and labelling "future", please re-open if you plan to work on this.