include windows in `genetic_relatedness_vector`
petrelharp opened this issue · 2 comments
Currently it's hard-coded "no windows".
I was a bit worried about how to efficiently deal with clearing out state between windows, but there's a nice way. Naively, we could start at each sample and traverse up the tree to the root to compute the state for that sample. That'd be O(N log N). However, if we clear the state of each node we pass through on the way, that lets us know "we've already been here and everywhere above this"; so we just have to traverse up until we find a node with x == position. This means we hit each edge once; so it's O(N).
Oh, wait - that doesn't work. The issue is that we store things so that the desired value is the sum all the way up the tree; we don't have a notion of "stuff further up the tree doesn't contribute". This was the price we had to pay for not keeping track of siblings and children - we'd need sibs and children to push things back down the tree.
So - I'll do this in the O(N log N) way; I think to do better we need a way to traverse back down the tree.
Meh, log N is small so let's not worry about it. Could easily be cancelled out by a simpler algorithm.