Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merge tree fragments #43

Closed
willdumm opened this issue Dec 13, 2022 · 1 comment
Closed

Merge tree fragments #43

willdumm opened this issue Dec 13, 2022 · 1 comment
Assignees

Comments

@willdumm
Copy link
Contributor

willdumm commented Dec 13, 2022

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:

  • $s$ is connected
  • $s$ may contain any number of internal nodes and/or leaf nodes
  • all nodes in $s$ with neighbors not in $s$ (which we'll call 'boundary nodes of $s$') are already in $G$.

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:

  • all of the boundary nodes of $s$ already exist inside the DAG, so only non-boundary nodes of $s$ may need to be created if they're not already in the DAG.
  • Since the boundary nodes define where $s$ gets patched into the DAG, there's no confusion about what other edges to add: we only need to add the edges between nodes in $s$.

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
Copy link
Contributor Author

willdumm commented Jan 9, 2023

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

@ognian- ognian- mentioned this issue May 4, 2023
ognian- added a commit that referenced this issue May 5, 2023
Implementation for #44 and #43

---------

Co-authored-by: Mary Barker <mbarker2@quokka.fhcrc.org>
Co-authored-by: Will Dumm <wrhdumm@gmail.com>
Co-authored-by: marybarker <marybarker103@gmail.com>
Co-authored-by: David Rich <31897211+davidrich27@users.noreply.github.com>
Co-authored-by: david.rich27 <david.rich@umotana.edu>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants