Closed marybarker closed 11 months ago
EDIT 1/13/23: Mary and I talked through lots of details, and I've attempted to update everything to reflect the details that we worked out. We think we've figured everything out, so hopefully this is a good starting point for an implementation.
EDIT 1/11/23: I've made various changes based on our conversation with Cheng, but I may have missed things, and anyone can feel free to make more corrections if you see them.
So we need a way to take an SPR move and build a tree fragment (like those in #43) summarizing all the changes (to CG's) that result from applying that SPR move to the original tree (sampled from the DAG).
Here's a description of how to do this in different words than Mary's that's still kind of vague:
Although we don't want to actually apply the SPR move to a copy of the original tree, we could use a class storing references to the original tree and the SPR move data, to encapsulate the logic involved in getting node neighbors and other node data in the hypothetical tree resulting from applying that SPR move. I'll call this the hypothetical tree
resulting from an SPR. Given a node in this hypothetical tree
, class methods should allow easy computation of:
the node's fitch set at each site. For some sites, the fitch set is omitted, but this only happens when the fitch set is a singleton, and the parent fitch set is the same. In this case, the base at that site in the compact genome that we've chosen for the parent node (in the BuildFragment routine) is the base in this singleton set, as long as there are no changes to the fitch set at this site. If there are changes, I think we need to traverse up the tree to the last node that has a recorded fitch set at this site, to figure out what it is. See this comment for details about how the new node's fitch set changes are encoded https://github.com/matsengrp/larch/issues/44#issuecomment-1381021310
the original compact genome for each node, before the SPR move. For the new node (red node in the picture) we will use the target node's compact genome.
the node's children. This is straightforward, except for when the parent of the source node only has one child after the SPR move. In this case, it may be convenient to just skip this node. That is, using the node IDs in this picture, the children of node 4 in the hypothetical tree should not be 3 and 5, but rather 1 and 5, and the parent of node 1 should be 4 rather than 3. This should not cause any problems because the fitch sets of node 1 and 3 after the SPR move are guaranteed to be the same.
the node's LeafSet (using a map from DAG nodes to unmodified MAT nodes) ... all as they would be if we really had applied the SPR move to the original MAT.
The mapping between nodes in this hypothetical tree and the original MAT can be via the node IDs, like in this picture:
The highlighted nodes, which are on a path from the source node to the target node, are exactly the nodes whose LeafSets will be changed by the SPR move, so the mapping between the two trees on those nodes doesn't fully make sense. However, for the nodes which aren't highlighted, the natural mapping via node IDs is the one we want. Also, there may not be a mapping for the parent of the target node (the red node in the picture).
Define a recursive function BuildFragment(node
, parent fragment node
) which takes a node in the hypothetical tree
resulting from an SPR move, and the tree fragment node built for the node's parent.
Definition of BuildFragment(node
, parent fragment node
):
chosen CG
be the compact genome for node
, before the SPR move. If node
is the new node (red node in the picture above) then use the target node's old CG.Fitch set
for site
at node
node
at site
:
parent fragment node
is not the UA node, let parent base
be the base in parent fragment node
's (new chosen) compact genome at site
, and if parent base
is in Fitch set
, then let chosen base
be parent base
.chosen base
be the base at site
on corresponding node in unmodified tree, if that base is in the fitch set, otherwise choose a base randomly from fitch set
.chosen CG
to have chosen base
at site
and record that a change was made to chosen CG
at that site, if necessary. (Which sites required changes will affect which sites must be considered when computing the compact genomes of any children of this node (**)).v'
with the same leaf set as node
, and containing chosen CG
, and add v'
as a child of parent fragment node
.v'
is not an anchor node (*see below for explanation):
c
of node
, do BuildFragment(c
, v'
).Besides the anchor node which is a tree fragment's root (which we determine below when deciding which node to start BuildFragment on) a node is an anchor node (meaning it's guaranteed to be the same as a node in the DAG, and there are no changes in the tree below that node resulting from the SPR move) if the following are all true:
Normally, we need only iterate through the sites at which either the base on the parent node changed (relative to the parent node's CG before the SPR move), or at which there's a Fitch set change. However, there are exceptions:
node
.node
is the source node, then none of its fitch sets have changed. We used the target node's CG as the template for choosing the CG of the parent fragment node
which is the fragment node resulting from the "new node" (red node in the picture). However, the old parent of the source node may have had a very different CG. Therefore, we should iterate through all the sites at which the new CG for parent fragment node
differs from the old CG of the source node's old parent (node 14 in the picture).Now given a (unmodified) MAT being optimized, and a proposed SPR move on that MAT, the corresponding tree fragment should be what we get from BuildFragment(earliest changed node
, parent history node
).
Here earliest changed node
is the earliest node in the SPR move's hypothetical tree
which has changed major alleles, or the latest common ancestor of the source and target nodes of the SPR, whichever is closer to the tree root. parent history node
is the history DAG node corresponding to the parent of earliest changed node
. If earliest changed node
is the root of the tree, then parent history node
is the universal ancestor node.
Finally, we can merge the resulting fragment into the DAG using #43.
parent history node
is part of a maximally parsimonious labeling of the sampled tree's topology. This may not be true in an hDAG, but is more likely to be true when the sampled tree achieves the maximum parsimony score seen in the DAG.By the way, the boundary allele set is not used in the matOptimize implementation of the Fitch algorithm. It is just one by-product useful for quickly calculating the parsimony score change from a single move.
$C_n$ is simply the alleles that happen most frequently in the $C_n$s of the children nodes.
One suggestion about applying Fitch set changes: I assume in Larch, multiple alleles in the Fitch set are represented as different clade nodes with the same split. For example, on the source side, a new split will be created corresponding to the parent split of the removed source node ( which may have multiple clade nodes if multiple major alleles are present) (Otherwise, if such a split already exists, then we can stop on the source side). Then, when deciding who are the incoming clades of the new split, we can look at the incoming clades of the original split. If none of their state at every site are in the removed allele set, connect the new split to it. Then, look at the added allele set, and create new clade nodes using the clade node where the parent node is sampled from as a template.
matOptimize represents Fitch set as mutations internally and is not exported, but I will write about its omission conditions anyway.
Thanks Cheng for the really helpful meeting, and your ideas.
Here's a summary of what we talked about (thanks Mary for the first draft of these)
One suggestion about applying Fitch set changes: I assume in Larch, multiple alleles in the Fitch set are represented as different clade nodes with the same split.
This is true, but not all alternative alleles are represented, only whichever ones happen to have been chosen in a tree that was merged into the DAG. I think this could make your next suggestion (below) even simpler.
For example, on the source side, a new split will be created corresponding to the parent split of the removed source node ( which may have multiple clade nodes if multiple major alleles are present) (Otherwise, if such a split already exists, then we can stop on the source side). Then, when deciding who are the incoming clades of the new split, we can look at the incoming clades of the original split. If none of their state at every site are in the removed allele set, connect the new split to it. Then, look at the added allele set, and create new clade nodes using the clade node where the parent node is sampled from as a template.
I think this is somewhat equivalent to what we're suggesting, although possibly simpler. I'll defer to @ognian- on whether we'd like to replace the tree fragment merging scheme with a more direct modification of the DAG. Either way, I'll reframe this in the context of an implementation of BuildFragment (updated above in the description of BuildFragment)
Cheng provided some additional clarification about how fitch set changes are represented for an SPR move, in nodes_with_changed_major_alleles set. Some of the following is directly copied from our conversation, and some is edited slightly.
For example, with this SPR with source node 7 and target node 9:
there is a fitch set change on node 10, and on the new node which is colored red and has the new label 11.
Node_With_Major_Allele_Set_Change{
node=9,
major_allele_set_change=
......
Mutation_Count_Change{
.....
incremented_allele=5,
decremented_allele=0
}
Where the incremented_allele and decremented_allele values are one-hot-encoded subsets of {A,G,C,T}.
The fix to properly present new node fitch sets as changes to the target node is here: https://github.com/yceh/usher/commit/793036ec630f2fb65c05a0ae5b3d3d7c2df117c7
Finally, in the case when the source node has only one sibling, its parent remains in the tree after the SPR move despite having only one child. We will of course want to change this to avoid unifurcation when building an SPR move's fragment.
This is a beginning step toward implementing #6
Since the callback has access to the altered/updated nodes for a given move, we can fully resolve these nodes without using the entire tree if we use the Fitch set changes that the move provides access to through the
node_with_major_allele_set_change
vector.The Fitch algorithm is an alternative to the Sankoff algorithm, where Fitch sets are assigned to nodes instead of cost vectors. Each site in the sequence for node
n
is assigned a Fitch set: a set containing the possible choices of base that minimize the subtree cost below that node.Fitch Algorithm
(for simplicity, written for a length-1 sequence, but generalizes to length-k sequence if we allow a Fitch set for each site in the sequence)
Notation: given a node
n
n
n
n
Then we assign Fitch sets to the nodes in a postorder traversal as follows:
n
, the Fitch set is the singleton set that containsn
n
:Using the Fitch sets and boundary allele sets, the sequences are assigned in a preorder traversal:
p
ofn
has base that is in $F_n$ then set the base ofn
equal to that base.n
to be that base.n
to be an element of $F_n$.