a pyslim helper to find the metadata for a given mutation ID with SLiM 6 metadata is perhaps needed?

[bhaller]

Hi @petrelharp! It looks like the python code for recipe 19.13 needs updating due to the changes in mutation metadata in SLiM 6. I started poking around with it, and in the end I decided that maybe pyslim ought to have a helper function, or I'm just too clueless in Python. The issue is that where before the script used to loop over mutations and their metadata directly, now it needs to look up their metadata in the separate top-level mutation metadata table. That in itself is something I could no doubt figure out. The problem is that I guess that mutation metadata table ends up as an array in Python, and finding the element in that array that has a mutation ID equal to a given mutation ID (coming from a derived state) would be O(N) in the number of mutations, so the recipe algorithm will end up being O(N^N) I think. It feels like maybe pyslim ought to provide a hash table that indexes into the mutation metadata array, so that looking up metadata for a given mutation ID is O(1) instead. So I figured I'd open this issue and see what you think.

Of course (a) the SLiM recipe could make a hash table itself (somehow?), and serve as an example of how to do that; but this seems like it will be a thing that EVERYBODY will want to do, so (b) it should maybe be functionality built into pyslim. Do you agree? (If you think (a) is the better path, a pointer on how I might implement it would be useful to me. :->)

[petrelharp]

I came to just the same conclusion in working on pyslim. Currently this is how you'd loop over mutations and get the metadata for each (potentially stacked) SLiM mutation:

mut_info = pyslim.mutation_metadata(ts)  # the hash table
for mut in ts.mutations():
    for k in mut.derived_state.split(","):
        metadata = mut_info[int(k)]
        # do something with this mutation's metadata

Here pyslim.mutation_metadata returns a dict (hash table) that maps integer mutation IDs to metadata records. Better would be if ts.metadata["SLiM_mutation_list"] was already a dictionary, so no such processing was necessary, but there's currently no nice way to do this. (To do that we'd need to define a new metadata type for the struct codec which returns you a dictionary. This would be probably not tooooo bad - so i will think about it? - but require some mucking around with metadata that I'm not excited about.)

How's this sound?

[bhaller]

This seems good? I guess probably internally the memory cost for the table is paid twice (once for the original table, once for the hash table), whereas if it was done with a new metadata type it'd get decoded directly into the hash table. Probably with a large number of mutations that would matter a bit, but probably small compared to the size of the tree sequence itself if it is large enough to have such a large number of mutations. Maybe the speed penalty would be significant too, and maybe that matters more? Not sure whether these prices are large enough to care. The other drawback of it being a pyslim API instead of the main metadata API is just that some people will not be aware of the existence of the pyslim API at all; but that's life. :-> I'm fine with this. But if it's ever going to be a new metadata type, now would be the time to do that; switching that over later would cause lots of confusion.

[petrelharp]

Closed in #431.