parent pedigree IDs maybe don't need to be in the individual metadata

[bhaller]

@petrelharp and I were puzzling about this. Why are these pedigree IDs there exactly? Could they be reconstructed from the parents column? (I think they are used to make the parents column, but maybe that could be done differently...) Are they needed/useful? If they're not, it'd make the metadata smaller to get rid of them.

[gregorgorjanc]

If parents are in the parent column of the individual table, then storing them also in metadata is indeed duplication.

[bhaller]

If parents are in the parent column of the individual table, then storing them also in metadata is indeed duplication.

Yes; it isn't quite that simple, since parents might get simplified away. For example, if we toss the parental pedigree IDs and some parents get simplified away, we can no longer calculate the relatedness between individuals in SLiM after reloading from the saved tree sequence. I suspect that this issue will get closed in the end; Peter and I just want to better understand why we made the decisions we made in this design. :->

[bhaller]

OK, there are two odd things, to me, here.

One is that the grandparent pedigree IDs are not in the metadata. That seems to imply that we lose that level of the pedigree tracking. The grandparent pedigree IDs could be reconstructed, but only if the parent individual metadata is present in the tree sequence. So I think it is lost. (Yes, it is lost; see worked example below.)

The other is that having tree-sequence recording turned on, but without keepPedigrees=T set, only individual pedigree IDs are accessible anyway; the parent and grandparent pedigree IDs are not user-accessible (i.e., will raise if accessed) unless keepPedigrees=T is set. So it is quite odd to be saving information that is not even user-visible.

So we're kinda saving both too little and too much. I'm not sure what I think about this.

An example that demonstrates the loss of information:

initialize() {
	initializeSLiMOptions(keepPedigrees=T);
	initializeTreeSeq();
	
	initializeMutationRate(1e-7);
	initializeMutationType("m1", 0.5, "f", 0.0);
	initializeGenomicElementType("g1", m1, 1.0);
	initializeGenomicElement(g1, 0, 99999);
	initializeRecombinationRate(1e-8);
}
1 early() {
	sim.addSubpop("p1", 4);
}
5 late() {
	inds = p1.individuals;
	for (ind in inds, index in seqAlong(inds)) {
		catn("Individual #" + index);
		catn("   pedigree ID: " + ind.pedigreeID);
		catn("   pedigree ID: " + paste(ind.pedigreeParentIDs));
		catn("   pedigree ID: " + paste(ind.pedigreeGrandparentIDs));
	}
	sim.treeSeqOutput("out.trees");
}

and then:

initialize() {
	initializeSLiMOptions(keepPedigrees=T);
	initializeTreeSeq();
	
	initializeMutationRate(1e-7);
	initializeMutationType("m1", 0.5, "f", 0.0);
	initializeGenomicElementType("g1", m1, 1.0);
	initializeGenomicElement(g1, 0, 99999);
	initializeRecombinationRate(1e-8);
}
5 late() {
	sim.readFromPopulationFile("out.trees");
	
	inds = p1.individuals;
	for (ind in inds, index in seqAlong(inds)) {
		catn("Individual #" + index);
		catn("   pedigree ID: " + ind.pedigreeID);
		catn("   pedigree ID: " + paste(ind.pedigreeParentIDs));
		catn("   pedigree ID: " + paste(ind.pedigreeGrandparentIDs));
	}
}

The output indicates that the parent pedigree IDs are indeed retained, and the grandparent pedigree IDs are indeed lost. Which is just weird. I'm not sure this is a bug, per se; I don't think we make any guarantees about grandparent pedigree information being preserved. It's just weird.

[bhaller]

This is tangential to another idea, from @gregorgorjanc, that I thought was represented by an open issue but which I can't find a trace of now. That was, IIRC, that we could get rid of the grandparent pedigree IDs in Individual anyway. If we kept "id x has parents y and z" separately from the instantiated individuals, in its own data structure, we could track ancestry back as far as we wanted, with relatively little overhead compared to the present design. That would allow more accurate calculations of pedigree relatedness, which presently go back only to the grandparent level, while probably actually saving memory and time compared to the present design. We could just sweep out the entries beyond a certain age, periodically. That idea is connected to this issue closely enough that probably they should be decided jointly. If we actually want to preserve the pedigree info in .trees files, we would probably write out that pedigree table in another top-level metadata table; if we don't, we should maybe remove the parent pedigree information that is there now (although removing it would break backward compatibility, and maybe we also need it to correctly construct the parents column after a save/reload cycle – which I suspect is why we added it to the metadata in the first place).

And incidentally, this issue: #256 shows that @petrelharp and I were aware, back in 2021, that parent pedigree IDs were being persisted and grandparent pedigree IDs were not. We seem to have been unbothered by that at the time, lol.

[petrelharp]

IIRC, I think that SLiM started storing parent pedigree IDs before that column appeared in the parent table, thus explaining why the information ended up in two places.

If we kept "id x has parents y and z" separately from the instantiated individuals, in its own data structure, we could track ancestry back as far as we wanted, with relatively little overhead compared to the present design.

Well, keeping track of everyone's parents for any fraction of coalescent time is O(N^2). But maybe you're suggesting just keeping track of this back, say, 10 generations? Maybe, but I think if you wanted to do calculations with the last 10 generations, you'd just Remember the last 10 generations, and then you'd have all that info in the individual table (and the genetic relatedness as well). If we wanted to compute pedigree relatedness going back 10 generations on the fly, every generation, during a simulation, then we'd need to do something different, true. But I'm reluctant to commit to a particular design here lacking concrete use cases.

The best argument I'm seeing here in favor of keeping pedigree IDs in tree sequence metadata is that when you reload, if the parental individual isn't in the tree sequence, then we can't reconstruct their pedigree ID. This would break somone's script if, say, they needed to identify siblings after reloading; the fix for them would be to also Remember the parental generation. Given the easy fix and the uncommonness of this situation, this isn't a very strong argument.

Another argument is convenience when reloading, so SLiM doesn't have to go looking around for the pedigree ID, I guess?

Ah: and then there's backwards compatibility. This is maybe the strongest argument for keeping them.

[bhaller]

IIRC, I think that SLiM started storing parent pedigree IDs before that column appeared in the parent table, thus explaining why the information ended up in two places.

Ah, yes, perhaps that makes sense.

If we kept "id x has parents y and z" separately from the instantiated individuals, in its own data structure, we could track ancestry back as far as we wanted, with relatively little overhead compared to the present design.

Well, keeping track of everyone's parents for any fraction of coalescent time is O(N^2). But maybe you're suggesting just keeping track of this back, say, 10 generations? Maybe, but I think if you wanted to do calculations with the last 10 generations, you'd just Remember the last 10 generations, and then you'd have all that info in the individual table (and the genetic relatedness as well). If we wanted to compute pedigree relatedness going back 10 generations on the fly, every generation, during a simulation, then we'd need to do something different, true. But I'm reluctant to commit to a particular design here lacking concrete use cases.

Yes, the goal is to have this information available during simulation, not after, so remembering individuals is orthogonal. We have the pedigree tracking feature now, and the relatedness() function. I'm not sure concrete use cases are really needed, because the proposed redesign here would be primarily motivated by performance – to keep the same information that pedigree tracking keeps now, you'd use less memory and less CPU. The performance benefits alone already motivate it. By default, it would keep the same information pedigree tracking keeps now – to grandparent level. But this design would open up the possibility of keeping it for longer – 5 generations, or eight, or ten – for much less overhead, in memory and performance, than it would take to do that with the present design.

The best argument I'm seeing here in favor of keeping pedigree IDs in tree sequence metadata is that when you reload, if the parental individual isn't in the tree sequence, then we can't reconstruct their pedigree ID. This would break somone's script if, say, they needed to identify siblings after reloading; the fix for them would be to also Remember the parental generation. Given the easy fix and the uncommonness of this situation, this isn't a very strong argument.

Another argument is convenience when reloading, so SLiM doesn't have to go looking around for the pedigree ID, I guess?

Ah: and then there's backwards compatibility. This is maybe the strongest argument for keeping them.

Yes, backwards compatibility kind of forces it. Who knows whether anyone is relying on it, but we don't want to randomly break people. Switching to a new internal representation would have benefits, though, as discussed above. I think it's a win; it's just a matter of the time it takes to do it (which I suspect will not be large, actually).

[bhaller]

Marked as "priority" since if this is going to happen it would be good to do it in SLiM 6. @petrelharp thoughts on my reply above? I guess, given our comments about backward compatibility, maybe I am proposing keeping the parent pedigree IDs in the individuals table metadata, but also, probably if and only if pedigree tracking is enabled, adding a top-level binary metadata table with deeper pedigree information based upon the proposed new internal implementation of the pedigree tracking. Does that make sense? I'd like to shift the internal representation of this pedigree information over, for performance reasons, and then persist it in the tree sequence somewhere since I'm shifting towards persisting more information now (like adding all the individual tag properties).

[petrelharp]

I see. I am currently not clear: if we just store this information in individual metadata then in some circumstances might we not be able to completely reconstruct the internal representation? Like, is there any information loss to storing this in individual metadata?

[bhaller]

Well, suppose we want to know the pedigree IDs of ancestors back 5 generations, for each individual in the individuals table. That'd mean storing 2^5 == 32 pedigree IDs per individual. For a population size of 512, that'd be 16384 pedigree IDs stored. Storing just parent IDs in a table, for five generations, for 512 individuals per generation, would be 5120 pedigree IDs stored. The disparity would only grow larger as you go back more generations. And as you simulate forward, you'd actually be storing (and then throwing away most of) 16384 * 5 = 81920 pedigree IDs; with the table approach the total number of pedigree IDs stored (and not thrown away) would be the same 5120. (After more generations you'd start throwing them away, but the number thrown away would be much smaller). That's the efficiency. If you only stored parent pedigree IDs, but remembered every individual, then the two approaches would be the same; but the point is that we don't, in general, want to remember every individual. We only want to store the pedigree information for every individual. (Back to the number of generations requested.) Am I making sense?

[bhaller]

So no, no information loss, necessarily; just massive information redundancy. And a variable metadata record size, depending on how many generations you want to store. Those are the problems that this redesign would solve.

[bhaller]

OK, @petrelharp and I talked about this and came to some decisions:

• SLiM's internal representation of pedigree tracking should shift over to a pedigree table as proposed: each row would have a pedigree ID and then pedigree IDs for the two parents, because that is fast to record (we've got the info directly at hand)
• That table should be written to top-level metadata, but perhaps with a change to its representation: each row would have a pedigree ID and then two indexes into the table, pointing to the rows for the two parents
• All this will happen only when pedigree tracking is enabled; when only tree-sequence recording is enabled, all we need are pedigree IDs for the individuals, no pedigree tracking is needed
• The parent pedigree ID information that is currently in the individual table metadata should be removed; this will break backward compatibility, but (a) probably relatively few people are using it, (b) the individuals table now has the parent column in it, which serves much the same purpose, and (c) if people want to use the pedigree table in the top-level metadata they can probably port their code over to using that fairly easily
• pyslim will not provide any sort of wrapper for the new top-level metadata table for the time being (no hash table conversion, no relatedness calculation function, etc.)

So this means a new schema and binary format for SLiM's individual metadata, but it feels like a step in the right direction. I'll do this ASAP, so that Peter can then adapt to it in pyslim as needed.

[bhaller]

Hi @petrelharp. OK, I got a ways down this road, and discovered this method:

void Species::AddParentsColumnForOutput(tsk_table_collection_t *p_tables, INDIVIDUALS_HASH *p_individuals_hash)
{
	// Build a parents column in the individuals table for output, from the pedigree IDs in the metadata...

This happens at Species::WriteTreeSequence() time; Species::AddLiveIndividualsToIndividualsTable() gets called to add extant individuals to the individuals table, and that calls Species::AddIndividualsToTable(), which calls MetadataForIndividual() to construct the individual metadata. That metadata is then used by Species::AddParentsColumnForOutput(), a little down the road, to make the parents column. (Things are a little different with remembered individuals, which get their metadata generated at the time they are remembered, but that is unimportant to the storyline here.) If it can find an individual in the individuals table for a given parent, it fixes the parents column to point to that individual; if it can't (probably the common case), it puts TSK_NULL representing "this parent did exist, but was not put in the table, or was simplified away". So, long story short, tree-sequence recording relies upon the parent pedigree IDs being available. I think we had both more or less forgotten this detail. :-<

So. I suppose we don't want to break this. Our plan was that "The parent pedigree ID information that is currently in the individual table metadata should be removed". I suppose we don't want to break the parent column of the individual table; we want to continue to write out correct information there, keeping backward compatibility even though the metadata no longer contains the parent pedigree IDs. So, we have four options I guess:

(1) Continue to keep the parent pedigree IDs when tree-seq recording is enabled (using the new pedigree table mechanism, rather than recording them in the individuals, as per the new design). This is a bit unfortunate; I was hoping to make the pedigree table mechanism be optional in both non-tree-seq and tree-seq models, to squeeze a little more performance out;

(2) Allow the parent column of the individuals table to contain no information, breaking backward compatibility, unless the user explicitly turns on pedigree tracking, in which case it would use the pedigree table mechanism to find parents and fill in the column (much as it does now);

(3) Same as (2), but if tree-seq recording is enabled, pedigree tracking would default to enabled as well, preserving backward compatibility at the cost of extra runtime overhead, unless the user explicitly turns pedigree tracking off (so this is like (1) except it allows the user to turn off the parent information if they don't need it);

(4) The best option, but I think it's not possible: keep the parents column as it is now, but without using the pedigree table. Maybe we can do this by walking upward from node to node? Starting at the node for an extant individual, walk upward to the next node, and see if there is an individual associated with it; if there is, call that the parent, and put a reference to it in the parents column. The problem with this is, I think, that the actual parent might have been simplified away, and so the next node up the chain might be some more distant ancestor. So I'm 99% sure this idea is a non-starter. If there were a simplify node that preserved any individual that is a parent of an extant individual – skipping any simplification of the parents of the extant individuals – then it would work, but AFAIK no such mode exists, and I don't think I want to propose that we add such a mode just to get us out of this little dilemma.

I think (1) is the way we have to go, sadly. I am tempted by (2) but the backward compatibility break would probably annoy people in the real world. (3) seems kinda useless since it is basically (1) unless the user is savvy enough to turn the feature off, which would be 0.1% of users. And (4) doesn't work.

Agreed?