matsengrp / larch

Inference and manipulation of history DAGs
2 stars 2 forks source link

Merge tree fragments #43

Closed willdumm closed 1 year ago

willdumm commented 1 year ago

This is one of the first steps towards implementing #6.

Given a history DAG $G$ and a history $t$ on the same leaves, but with $t$ possibly not a history in $G$, we'd like to be able to merge a sub-structure $s$ of $t$ into $G$ for which:

Here's a picture showing the history $t$ on the left, and on the right side, such a sub-structure $s$ is highlighted in yellow, with blue arrows pointing to the boundary nodes:

image

Merging a structure like $s$ will be (in theory) straightforward:

This fits in with #6 because given a move, we'd like to be able to produce a sub-structure like $s$ from the (hypothetical) tree resulting from applying only that move. This small sub-structure will contain all the nodes which are different (have different child clade sets or compact genomes) as a result of applying the move. Since this sub-structure will be much smaller than the entire tree, we'd like to be able to produce only the sub-structure, and merge it into the hDAG, as part of the move callback.

willdumm commented 1 year ago

Let's replace the term "boundary nodes" with "anchor nodes" to avoid any confusion with "boundary alleles".