PCG icon indicating copy to clipboard operation
PCG copied to clipboard

Add Distance Wagner method

Open Boarders opened this issue 4 years ago • 5 comments

Ward mentioned that we should add a new build method which uses the distance Wagner. This is described in detail on p. 165 of the Systematics text book. Roughly it works as follows: given an already constructed tree:

               [...]            [...]      
                 │      e_ij      │ 
                 v_i  ────────── v_j
                 │                │
               [...]            [...] 

If we wish to add vertex v_k to this tree then we compute the distance:

d(v_k, e_ij) = 1/2 (d(v_k, v_i) + d(v_k,v_j) - d(v_i,v_j)

If v_i and v_j are already internal nodes in the tree then these distances are computed in terms of computations involving only the distances between the leaves in the subtrees to which they are attached. One then adds a new internal vertex and attaches v_k to the edge with the minimal distance. One nice thing about this method is that we do not need to compute any medians or perform any traversals as it is based entirely on the distance matrix between the leaves. This means we do not need to construct intermediate trees but instead can use a smaller data structure for tracking the distance information.

Note: I think it is the case that if the metric is an ultrametric then this is exactly the distance but otherwise is an overestimate because of the triangle inequality. The textbook indicates that this method might cause problems for non-metric distances.

Ward noted that having this kind of distance information might also be useful when performing refinements as this can provide candidate edges along which to perform SPR-type moves.

Boarders avatar Feb 27 '20 22:02 Boarders