Definitions and terminology

[jeromekelleher]

We should be precise about what we mean by various bits of terminology, so here's my effort to lay things out. It's not obvious how this will fit into the narrative of the paper at the moment, but lets see if we can agree on the terms and their definitions here before putting them in.

Genome

The complete set of genetic material that a child inherits from one parent. (What do we say about chromosomes here?)

Individual

A single organism, carrying one or more genomes depending on ploidy. E.g. a diploid individual carries two genomes.

Pedigree

A DAG in which nodes represent individuals and edges represent parent-child relationships between individual organisms.

ARG

A DAG in which nodes represent genomes and edges represent the inheritance of genetic material relative to some set of sample genomes, which has additional annotations to encode the flow of ancestral material within those genomes, so that the trees relating genomes are uniquely defined. The annotations can be either associated with nodes or edges.

Node annotated ARG

An ARG in which nodes with > 1 parent have been annotated to indicate the flow of ancestral material from the child to its parents. In the classical Griffith's approach, recombination nodes have two parents and are annotated with a breakpoint. Conventionally, we then assume that the node has inherited genetic material to the left of this breakpoint from the one parent, and the remainder from the other parent.

Edge annotated ARG

An ARG in which edges are annotated with the set of intervals containing ancestral material.

I'm not sure how formal we want to be about all this, but I think this is the set of concepts we need to work with?

[hyanwong]

I think we also want to define recombination nodes, coalescent nodes, and CA nodes. Note that we may have a node in a tree that is none of these too.

[hyanwong]

Also note that if we are saying a single node is one of the genomes in an individuals (rather than one of the genomes in a cell) then I think a node can be simultaneously both a recombination and a coalescent or CA node. In small pedigrees with long genomes, this is presumably quite common?

[gregorgorjanc]

@hyanwong CA nodes being coalescence nodes?

No, they are nodes that are shared in the pedigree, but in which no genetic material actually coalesces. I would actually prefer a different name for them, as I also find the name "Common ancestor" a bit confusing, and it took me a while to get this.

Common ancestor in the pedigree (genealogical) sense, but not in the genetic (DNA) sense?

[jeromekelleher]

Common ancestor (CA) nodes correspond to events in the stochastic process in which two lineages merge into a single common ancestor. Depending on the distribution of ancestral material carried by these lineages, this may or may not result in coalescence, where the overlapping segments of ancestral material result in coalescences in the marginal trees.

So: in the stochastic process, there are two types of nodes CA and RE (following Hudson's terminology). CA nodes may or may not result in coalescence.

It's debatable whether we want to carry this terminology from the process into descriptions of the structure, but I think it's important highlight that some (actually, most in the stochastic process) CA nodes don't result in any coalescence.

[hyanwong]

Thanks for the clarification Jerome. I see that I was (slightly) wrong. From my reading of the above, CA nodes include coalescent nodes. So we want a terminology for CA nodes that are not coalescent nodes.

I think that msprime might be little misleading in this regard, because it only uses the "NODE_IS_CA_EVENT" flag on nodes that are CA nodes but not coalescent nodes. Perhaps this should be changed so that even the coalescent nodes are thus flagged (when record_full_arg is True), or perhaps we need to invent new terminology and change the flag name? Unless I've misunderstood something.

[jeromekelleher]

Yes, you're right - msprime is abusing the terminology here as CA nodes are the "superclass" and include coalescences.

We should probably rethink the terminology, since we're talking about erroring out for the msprime RE node constant anyway.

I think "coalscence" really should correspond to nodes in a coalescent tree. It's just too confusing to say that some coalescences don't result in marginal coalescence. Other than that, open to suggestions!

[a-ignatieva]

Just a thought - would a short overview of other types of phylogenetic networks be within the scope of this paper (e.g. hybridisation networks, tree-child networks, galled trees, level-k networks etc)? I think the differences between these things can seem subtle, and it might be nice to try to collect together definitive descriptions of these similar structures (that may or may not fall under our definition of ARG).

[jeromekelleher]

Personally I'd find this really helpful and think it would be a great addition. I've never gotten my head around it myself!

[jeromekelleher]

If you've got a paragraph summing up the various structures just drop it in anywhere to the text - we can figure out exactly where it should live later.

[hyanwong]

We previously argued that there was a major distinction between an "edge annotated ARG" (e.g. tree sequence) and a "node annotated ARG" (e.g. the Griffiths-type graph), but @jeromekelleher devised a way to use edge annotations to represent the Griffiths graph. Really, the main distinction is between a local encoding of the breakpoints (the standard for node annotated args), and a global encoding, which is formed when we run the algorithm on the local encoding).

We could do with some terms to describe these two forms of ARG encoding, I think. We toyed with the idea of using implicit vs explicit ISTR.

[a-ignatieva]

I think implicit coordinates vs explicit coordinates is good. "Local" is too tied to "local trees" I would say.

[hyanwong]

Yes, I completely agree.

[jeromekelleher]

It depends on how we encode the edges for the "implicit" version I think. Once we have a decision on this, it'll be easier to think about the terminology. I'll start a discussion on this as it's an interesting question

[jeromekelleher]

Yan is right that it's getting very confusing having the same TLA meaning at least three different things. We've moved on a bit from the original takes, so here's some recent thoughts.

• Define the classical Griffith's type ARG data structure as an "Event ARG" or "EARG" (pronouced "E-ARG"?)
• The definition we're proposing, is a "Genome ARG", or "GARG" (pronounced GARG).

Technically, the difference really lies in whether we associated genome coordinate information with nodes (EARG) or edges (GARG), but talking about edge and node annotations feels terribly dry, and distinguishing between events and genomes is much more concrete (and conceptually important I'd argue, but probably not worth getting into that).

How we talk about the stochastic process is another issue. I guess we could just call this the ARG (which is reasonable, this this is what it originally meant), if we consistently use EARG and GARG elsewhere?

[JereKoskela]

We can define a stochastic process more-or-less however we like. Continuing past a local root is certainly possible. But my impression is that that's not how the CwR is usually defined. If that's right, then I think consistency is desirable, and we should also define it as the process simulated by the Hudson algorithm.

I could well be wrong about this, but isn't the little ARG exactly the CwR (as defined above) but without terminating branches at a local root?

[hyanwong]

I'm happy not to use CwR to refer to the Griffiths process: that was one suggestion, but the point Jerome just made about its association with Hudson is a good one. I am (very) keen to avoid "graph" referring to the process. You just did it yourself: you said "The stochastic process produces a graph" implying that the stochastic process is not the graph itself. The graph is what is created by the process. If ARG stood for "Ancestral Recombination process-that-generates-a Graph, that would be fine. But it doesn't.

We could coin "ARP" (ancestral recombination process), but I think the "Griffiths process" is just fine. Hopefully we won't have to mention it much after the initial description anyway.

[hyanwong]

Also, by the way, I think Griffiths didn't coin ARG to explicitly refer to the process. He used it to mean both the process and the graph it generates. It would be helpful to have a word that isn't "ARG" to mean the former without invoking the latter.

[JereKoskela]

I don't have a problem with "graph" as a process term either. It is always possible (and often convenient) to think of a stochastic process as a single random object, e.g. a random vector in the case of a scalar process in discrete time. In this case, that perspective leads to thinking of the ARG as a random graph, whose distribution happens to be conveniently specified via a stochastic process, but need not be. We could also write down the joint distribution of the whole thing in one go in terms of branch lengths, numbers of branchings and coalescences etc, if we had enough patience. From that perspective, the only distinction here is whether we're talking about a random object which takes values in particular kinds of graphs, or a realisation from its distribution.

[hyanwong]

Perhaps it's just me then. But when Jerome said "The stochastic process produces a graph", that's how I imagine most people see it. I still think a phrasing such as "Griffiths process" is less likely to lead to confusion early on in the paper.

[hyanwong]

We could also do with a terminology for the nodes at and below a recombination. I suggest we call the 2 parent nodes the "recombining nodes" and the child the "recombinant node". Or is the similarity in names too confusing?

[jeromekelleher]

I would probably avoid calling them "nodes" at all and instead talk about the genomes - but let's not get into that yet. :canofworms:

[hyanwong]

Sure, "recombining genomes" and "recombinant genomes" works just as well for me.