Opened 7 years ago
Last modified 5 weeks ago
#449 _started enhancement
Add function to synchronize roots of two trees
Reported by: | westram | Owned by: | westram |
---|---|---|---|
Priority: | normal | Milestone: | r19 |
Component: | ARB_NTREE | Version: | SVN |
Keywords: | Cc: |
Description (last modified by westram)
Motivation:
- ARB_NTREE/Tree/Move groups does a poor job, if the root of the destination is located at a different branch (even if the 2 topologies are identical).
- using similar roots simplifies topology comparison (#444)
Implementation:
Modes:
- set root of target to an edge similar to root-edge in source
- set root nodes of two (or more) trees such that
- root is nearby the optimal root (as provided by reroot-mode)
- both root-edges are similar
(Note: 1. will not modify the source ; 2. may modify all trees)
Similarity of 2 root-edges:
- each edge divides the X into 2 partitions (pX_{1} and pX_{2})
- comparing two edges in two trees (A and B) needs to calculate 4 pairwise differences pA_{x} Δ pB_{y} between the 4 partitions defined by the two edges. Two combinations of pairwise differences are possible:
- pA_{1} Δ pB_{1} and pA_{2} Δ pB_{2}
- pA_{1} Δ pB_{2} and pA_{2} Δ pB_{1}
- comparing 3 edges in 3 trees needs to calculate 12 pairwise differences.
- the value of a pairwise difference might be e.g.
where |set| is the size of the set.
pA_{x} Δ pB_{y} = |pA_{x} ∪ pB_{y}| - |pA_{x} ∩ pB_{y}|
- the value of a combination might be
- the sum of pairwise differences,
the minimum pairwise difference(wont work, see comment13)
or- some mix of both.
Change History (16)
comment:1 Changed 7 years ago by westram
- Description modified (diff)
comment:2 Changed 7 years ago by westram
- Description modified (diff)
comment:3 Changed 4 years ago by westram
- Milestone work2014 deleted
comment:4 Changed 4 years ago by westram
- Description modified (diff)
comment:5 Changed 3 years ago by westram
- Description modified (diff)
- Milestone set to wishlist
comment:6 Changed 3 years ago by westram
- Milestone changed from wishlist to r18q1
- Owner changed from devel to westram
- Status changed from new to assigned
comment:7 Changed 3 years ago by westram
- Milestone changed from r18q1 to wishlist
comment:8 Changed 2 years ago by westram
- Status changed from assigned to accepted
comment:9 Changed 2 years ago by westram
- Milestone changed from wishlist to r18
comment:10 Changed 23 months ago by westram
- Description modified (diff)
comment:11 Changed 10 months ago by westram
- Milestone changed from r18 to r19
comment:12 Changed 3 months ago by westram
- Status changed from accepted to _started
comment:13 Changed 5 weeks ago by westram
- Description modified (diff)
comment:14 Changed 5 weeks ago by westram
- Description modified (diff)
comment:15 Changed 5 weeks ago by westram
- Description modified (diff)
comment:16 Changed 5 weeks ago by westram
- Description modified (diff)
previous change was stupid → reverted.
Note: See
TracTickets for help on using
tickets.
Why the minimum pairwise difference won't work:
Given 2 trees A and B and one species S present in both trees. The leaf edges between S and the rests of both trees define the following partitions:
Here the minimum would always be
⇒ all leaf edges (at species present in both trees) would match perfectly - regardless how the rest of the matches
⇒ leaf edges would be preferred over other edges (esp. for pairs of trees where topology differs).