Opened 11 years ago

Closed 4 years ago

Last modified 3 years ago

#449 closed enhancement (implemented)

Add function to synchronize roots of two trees

Reported by: westram Owned by: westram
Priority: normal Milestone: arb7.0
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 tree is located at a different branch (even if the 2 topologies are identical).
  • using similar roots simplifies topology comparison (#444)

Implementation:

Modes:

  1. set root of target tree to an edge similar to root-edge in source tree
  2. 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 tree; 2. may modify all trees)

Similarity of 2 root-edges:

  • each edge divides the tree X into 2 partitions (pX1 and pX2)
  • comparing two edges in two trees (A and B) needs to calculate 4 pairwise differences pAx Δ pBy between the 4 partitions defined by the two edges. Two combinations of pairwise differences are possible:
    • pA1 Δ pB1 and pA2 Δ pB2
    • pA1 Δ pB2 and pA2 Δ pB1
    Only the better combination should be considered!
  • comparing 3 edges in 3 trees needs to calculate 12 pairwise differences.
  • the value of a pairwise difference might be e.g.

    pAx Δ pBy = |pAx ∪ pBy| - |pAx ∩ pBy|

    where |set| is the size of the set.
  • 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.

Required by: #734, #451
Related: #512

Change History (18)

comment:1 Changed 11 years ago by westram

  • Description modified (diff)

comment:2 Changed 11 years ago by westram

  • Description modified (diff)

comment:3 Changed 9 years ago by westram

  • Milestone work2014 deleted

comment:4 Changed 8 years ago by westram

  • Description modified (diff)

comment:5 Changed 8 years ago by westram

  • Description modified (diff)
  • Milestone set to wishlist

comment:6 Changed 8 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 7 years ago by westram

  • Milestone changed from r18q1 to wishlist

comment:8 Changed 6 years ago by westram

  • Status changed from assigned to accepted

comment:9 Changed 6 years ago by westram

  • Milestone changed from wishlist to r18

comment:10 Changed 6 years ago by westram

  • Description modified (diff)

comment:11 Changed 5 years ago by westram

  • Milestone changed from r18 to r19

comment:12 Changed 5 years ago by westram

  • Status changed from accepted to _started

comment:13 Changed 4 years ago by westram

  • Description modified (diff)

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:

pA1pA2pB1pB2
containingSrest of ASrest of B

Here the minimum would always be

pA1 Δ pB1 = 0

⇒ all leaf edges (at species present in both trees) would match perfectly - regardless how the rest of the tree matches
⇒ leaf edges would be preferred over other edges (esp. for pairs of trees where topology differs).

comment:14 Changed 4 years ago by westram

  • Description modified (diff)

comment:15 Changed 4 years ago by westram

  • Description modified (diff)

comment:16 Changed 4 years ago by westram

  • Description modified (diff)

previous change was stupid → reverted.

comment:17 Changed 4 years ago by westram

  • Resolution set to implemented
  • Status changed from _started to closed

by [18634]

comment:18 Changed 3 years ago by westram

  • Milestone changed from r19 to arb7.0
Note: See TracTickets for help on using tickets.