Threading

[hyanwong]

@a-ignatieva and others are thinking about how samples can be "threaded" through an existing ARG in various ways. This is very similar to matching samples against an ancestors tree sequence in tsinfer. For further research & adoption, it would be extremely empowering to be able to do the threading operation via the super-efficient L&S matching algorithm in tskit / tsinfer. I'm sure there are some gotchas, though, so I think it's worth opening a discussion thread. Here are a few points that occur to me:

1. This is very similar to issue Add augment_samples() functionality #189, which @szhan is thinking about and which already has some details worked-up.
2. The normal threading operation can create new coalescent points in the tree sequence, which would be equivalent to adding new ancestors in the tsinfer pipeline (see Add augment_samples() functionality #189 (comment))
3. The normal "ancestors TS" contains portions of ancestral haplotypes that are not ancestral to any samples in the tree sequence. These get simplified away when converting to a "normal" tree sequence, so threading a sample into an existing tree sequence by converting that tree sequence to an "ancestors TS" may miss some possible regions that would be good matches.