Opened 6 years ago

Last modified 2 months ago

#449 accepted 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 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|

  • the value of a combination might be
    • the sum of pairwise differences,
    • the minimum pairwise difference
      (might work better for trees built upon different sets of species)
      or
    • some mix of both.

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

Change History (11)

comment:1 Changed 6 years ago by westram

  • Description modified (diff)

comment:2 Changed 6 years ago by westram

  • Description modified (diff)

comment:3 Changed 4 years ago by westram

  • Milestone work2014 deleted

comment:4 Changed 3 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 2 years ago by westram

  • Milestone changed from r18q1 to wishlist

comment:8 Changed 17 months ago by westram

  • Status changed from assigned to accepted

comment:9 Changed 17 months ago by westram

  • Milestone changed from wishlist to r18

comment:10 Changed 15 months ago by westram

  • Description modified (diff)

comment:11 Changed 2 months ago by westram

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