could maybe radically optimize simple neutral models by deferring genome generation

[bhaller]

An idea I had on my walk today. When an offspring individual gets generated, right now SLiM spends a lot of time creating the Individual object and generating that individual's haplosomes from the haplosomes of the parents, with recombination and mutation. In a simple neutral model with no recombination() callbacks, no modifyChild() callbacks, no script asking for the mutations possessed by individuals, no changes in the recombination rate or mutation rate over time, etc., it seems like it would be possible to defer virtually all of that work. Just record, into a "deferred individuals table", the pedigree ID of the new individual and its parent(s) and whether it was generated by cloning, selfing, or crossing – basic info like that, columns in a data table. And then move on. Keep parents around if they are referenced by this table, so that you still have their genetic information if you need it later. At some future point – perhaps the end of the simulation, or perhaps whenever the preconditions for this mode of operation are violated – you can generate the genetics that are needed, on demand. To do that, you start from the extant individuals; if one is deferred, go up to its parents; if one of them is deferred, go up to that individual's parents; and so on, until you reach individuals for whom you have genetics. Then generate the offspring that are needed, drawing recombination breakpoints, doing the recombination, generating the mutations, etc., just as you would have at the time. Continue doing that, unwinding your ascent up the pedigree, until you get down to the bottom again and have generated the genetics for the extant individual.

For individuals that leave descendants, this is the same amount of work, or even a little bit more since there's a bit of overhead for maintaining the "deferred individuals table" and doing the walk up and down the tree. The savings comes from the idea that, given enough generations, most individuals leave no pedigree descendants; most lineages go extinct eventually. So you end up generating only a small fraction of the individuals you would have generated.

In a way this is similar to the concept of recapitation and neutral mutation overlay. But it would work even without tree-sequence recording; in fact, it could build up the relevant tree-sequence recording information in the same deferred fashion, I think, and so it could do a tree-seq burn-in without needing to deal with hybrid-simulation complications. It would have various advantages: it would produce a true SLiM pedigree (WF or nonWF) based upon the SLiM-generated patterns of mating rather than a coalescent-style pedigree (in terms of things like discrete time, polytomies, etc.), it could be influenced by SLiM scripted dynamics (monogamous mating, spatiality, etc.) as long as those dynamics didn't need to consult the genomes of the individuals... lots of advantages. And SLiM could do it automatically, I think; it could detect that the conditions were met and defer offspring generation behind the scenes, and then whenever the conditions were violated later on (or when the end of the simulation was reached), it could transparently generate the genetic information needed to bring things back to a "normal" SLiM state. The whole thing could, I think, be totally invisible to the user.

This scheme depends on a vague idea I have that over sufficient time most individuals don't leave any pedigree descendants. So if a complete pedigree, starting from the original individuals and going forward in time, would contain N individuals, but only M of those individuals appear in the simplified pedigree where all branches of the pedigree that went extinct are removed, then my hope is that if this optimized regime lasted a large number of generations – 10,000, or 100,000, etc. – the fraction M/N would get somewhat small (assuming, say, a randomly-mating WF population), making this optimization worthwhile – maybe very worthwhile. My vague understanding is that this is true, but I am probably thinking of the related claim that most individuals don't leave any genetic descendants (even if they do still appear in the pedigree of ancestors of the extant individuals). Clearly M/N is smaller for genetic descendants than for pedigree descendants, but the genetics-based optimization is much harder to do. (I think I had a somewhat similar idea, months or years back, that @petrelharp shot down, in fact – using recorded tree-seq information to defer the SLiM generation of individuals, such that we wouldn't bother generating the ancestors at all if they left no genetic descendants. That turned out to be hard. :->) But if M/N is sufficiently small even for pedigree descendants, over sufficiently long time periods, then this idea remains viable. And it might be particularly viable if something about the script being run reduces Ne – spatiality, monogamy, social dominance hierarchies, etc. So it might be very useful in some contexts even if it isn't much of a win for a vanilla panmictic WF model.

Seems like a good idea? Any thoughts, @philippmesser or @petrelharp or anybody else? Any roadblocks to doing this? I suppose this idea probably isn't new (since so few ideas are new); is anybody aware of a forward simulator that does this already? (If so, I want to go read about it! :->)

[petrelharp]

Interesting! But, hm:

given enough generations, most individuals leave no pedigree descendants

Hm - it depends on the offspring distirbution, but IIRC, something around 50% of individuals leave pedigree descendants? (And even for "genetic descendants", if there's recombination, still on a reasonable chromosome (so that there's a reasonable chance that the offspring gets genetic material from both parents) something like 20%-50% of individuals will leave pedigree descendants?

That said, I think that Paul Marjoram et al got decent speedups by doing this sort of thing, in this paper and/or this paper. The speedup would definately plateau quickly, although maybe would reach 10x, but given it's restricted to neutral models, I don't know that it's worth the work?

[bhaller]

Interesting! But, hm:

given enough generations, most individuals leave no pedigree descendants

Hm - it depends on the offspring distirbution, but IIRC, something around 50% of individuals leave pedigree descendants? (And even for "genetic descendants", if there's recombination, still on a reasonable chromosome (so that there's a reasonable chance that the offspring gets genetic material from both parents) something like 20%-50% of individuals will leave pedigree descendants?

Do you mean over one generation, or over limit-as-number-of-generations-approaches-infinity generations? And hmm, I'm having trouble understanding your second sentence here at all – you switch from genetic descendants to pedigree descendants somehow. :-O

That said, I think that Paul Marjoram et al got decent speedups by doing this sort of thing, in this paper and/or this paper.

Interesting, I'll check those out, thanks! (Random aside: I like authors whose names are food. Marjoram should do a paper together with Rice and Salt! Echoes of the classic Alpher, Bethe, Gamow paper. :->)

The speedup would definately plateau quickly, although maybe would reach 10x, but given it's restricted to neutral models, I don't know that it's worth the work?

I think a 10x speedup seems pretty awesome! Neutral models remain quite common, especially for burn-in periods, and recapitation does not always fit the bill. In particular, one of the most common FAQs is "I've got a spatial model / monogamous-mating model / whatever-weirdness model, and I need to do a neutral burn-in, and it's taking FOREVER, what can I do?" It would be fabulous to speed up such neutral burn-ins in SLiM by a factor of 10x, right? Right now we have to say "Well, you probably need to do a coalescent burn-in even though it doesn't really mirror what you're trying to model, so maybe do some additional forward-simulated burn-in to try to erase the bias introduced by that mismatch, but nobody knows how long that additional forward-simulated burn-in ought to be to really erase the bias, so you'll just need to experiment and try to make an informed guess...". If doing such neutral burn-ins in SLiM was 10x faster, it would (at least partially) solve a lot of problems, it seems to me!

[petrelharp]

Do you mean over one generation, or over limit-as-number-of-generations-approaches-infinity generations?

The latter: infinity generations. However, note that whether or not an individual will have pedigree descendants is pretty much entirely determined within 3-5 generations.

I think a 10x speedup seems pretty awesome!

Agree! I think if you're enthusiastic, it's worth looking at those papers carefully and doing some benchmarking (ie counting how many indivs can be discarded in practice).

[bhaller]

Do you mean over one generation, or over limit-as-number-of-generations-approaches-infinity generations?

The latter: infinity generations. However, note that whether or not an individual will have pedigree descendants is pretty much entirely determined within 3-5 generations.

I think a 10x speedup seems pretty awesome!

Agree! I think if you're enthusiastic, it's worth looking at those papers carefully and doing some benchmarking (ie counting how many indivs can be discarded in practice).

Yep. OK. This is back burner for now, but Philipp also thinks the idea is worth investigating so I'll delve into it some time after multitrait is finished. :-> Thanks for the feedback!

[bhaller]

A thought from today's walk. Gregor Gorjanc suggested a while back that pedigree tracking could essentially chain through records about individuals; rather than each individual recording the pedigree IDs of its two parents and four grandparents, it could just record its two parents, and the two parents – having themselves recorded their own parents – would provide the grandparents. This would cut down on storage space, and also on runtime since there would be less writing of redundant pedigree information. However, it was a bit tricky in practice, because the parents might no longer be alive, so you'd have to keep the pedigree ID information in a separate table so you'd have the information needed even if some parents were no longer extant. And you'd want to garbage-collect that table to get rid of information about branches that went extinct, and about individuals beyond a certain age. That, it seems to me, is pretty much exactly the same data structure that I'm proposing here. In essence, we can use pedigree tracking (following Gregor's suggested approach) to keep the pedigree for the simulation without actually generating the individuals (unless they are needed).