Review of ARG inference methods

[jeromekelleher]

Given the terminology developed in the paper for describing ARGs, I think it would be helpful (and a good exercise) to go back through the history of these methods and review and classify them using this terminology. We don't need to go into much detail for the majority, just a mention and a citation. (#12 added a start to this.)

We then discuss the recent methods in detail. At a minimum, we need to discuss:

• ARGweaver
• tsinfer (and tsdate)
• Relate

It would be good to also discuss other recent methods that have been published like SARGE, etc.

[JereKoskela]

To add a few names:

• arginfer (code)
• Arbores (paper, code)
• ClonalOrigin (paper, code)
• KwARG (paper, code)

For completeness, we could also briefly mention early pre-SMC MCMC methods, though probably not at length:

• Kuhner, Yamato, and Felsenstein (2000)
• Nielsen (2000)
• Wang and Rannala (2008)

EDIT: I only noticed there is an issue open for this after the fact. I'll add these to the bibliography when I get the chance and leave them here as a reminder in the meantime.

[jeromekelleher]

Thanks @JereKoskela, this is excellent! Sorry about the multiple discussions/issues thing. I'm trying to open issues for things that can be closed off with a single PR, and use discussions for things that are more open ended. I don't know if I got it right here.

[JereKoskela]

I don't think it was confusing. I was just typing into the first place I saw, rather than taking a look through the overall repo first.

[jeromekelleher]

The current summary in the text is based on a rough timeline (which sort of mirrors earlier discussions) I think we should try to do it by classification. As @a-ignatieva suggested (somewhere? I can't remember where) one categorisation is by backwards-in-time vs along the the genome.

I think there's a few different methods that work backwards in time using the same basic operations that were defined by Lyngso et at 2005. The basic processes of "reducing" the data to informative sites, and working backwards in time by performing mutations, recombinations and coalescences by working with the extant haplotypes are shared by many methods (I think KwARG is in this "lineage" of ARG inference methods @a-ignatieva?). This would probably be a good thing to explain, and bring together in a paragraph.

Then there's the left-to-right methods, which probably go back to Hein's early paper (even though it wasn't explicitly talking about ARGs). I forget the references now, but isn't there a Song method which works left-to-right via SPRs?

ARGweaver is the first "threading" method, based on adding the n + 1th sample into an existing ARG.

Tsinfer is a composite method, as it works both along the genome (to estimate ancestral haplotypes) and forwards in time to match ancestral haplotypes.

I'm sure I'm missing stuff here, but does breaking things down like this and explaining the high-level strategies seem like a useful thing to do?

[JereKoskela]

Sounds good to me! The way I've written things is structured to suit the pre-ARGWeaver MCMC methods (because I'm most familiar with them), and they operate on the whole ARG at once so don't really fall either into any of the categories neatly. But they're also not really relevant for modern data, so should probably just be their own sidenote in the finished product anyway.

[jeromekelleher]

They're also not really inferring ARGs as such, but rather integrating over them. So, we don't really need to talk about them again (they're mentioned earlier on now as part of the historical narrative)

[JereKoskela]

Integrating over ARGs sort of gives you inferred ARGs for free in this case. The methods are constructing (sample by sample) the conditional distribution of an ARG given the observed sequences. You can treat any particular realisation of an ARG along the length of a run as a draw from that conditional distribution, and hence a valid inferred ARG. But I'm not suggesting we allocate any more space to the methods as a result.

[jeromekelleher]

That's true, but I don't think they actually did output them though, right?

[JereKoskela]

I don't know, but probably not.