Neighbor-Net is a novel method for phylogenetic analysis that is currently being …

• Abstract
• Background
• Preliminaries
• Description of the Neighbor-Net algorithm
• Neighbor-Net is consistent
• References
• Figures
• Tables

Biology Articles » Molecular Biology » Consistency of the Neighbor-Net Algorithm » Description of the Neighbor-Net algorithm

Description of the Neighbor-Net algorithm

- Consistency of the Neighbor-Net Algorithm

3 Description of the Neighbor-Net algorithm

In this section we present a detailed description of the Neighbor-Net algorithm, as implemented in the current version of SplitsTree [9]. The Neighbor-Net algorithm was originally described in [2], where the reader may find a more informal description for how it works. For the convenience of the reader we will use the same notation as in [2] where possible.

In Figure 2 we present pseudo-code for the Neighbor-Net algorithm. The aim of the algorithm is, for a given input distance function d, to compute a circular split weight function ω so that the distance function d_ω gives a good approximation to d. The resulting distance function d_ω can then be represented by a planar phylogenetic network as indicated in the last section.

To this end, NEIGHBOR-NET first computes an ordering Θ of X, and then applies a non-negative least-squares procedure to find a best fit for d within the set of distance functions {d|:Ϭ(X) → _≥0, Ϭ⊆ Ϭ_Θ}. More details concerning the least-squares procedure may be found in [2]: Here we will concentrate on the description of the key computation for finding an ordering Θ of X, which is detailed in the procedure FINDORDERING.

An (ordered) cluster is a non-empty finite set C together with an ordering Θ_C = c₁, ..., c_k of the elements in C, k = |C|. Two elements a, b ∈ C are called neighbors if there exists i ∈ {1, ..., k - 1} such that a = c_i and b = c_i+1, or b = c_i and a = c_i+1. The input of the procedure FINDORDERING consists of a set of mutually disjoint clusters, together with a distance function d on the set . The ordering Θ = y₁, ..., y_n of Y that is returned by FINDORDERING must be compatible with the collection of ordered clusters, that is, for every cluster C ∈ there must exist i, j ∈ {1, ..., n}, i ≤ j, with the property that Θ_C = y_i, ..., y_j or Θ_C = y_j, ..., y_i.

The procedure FINDORDERING calls itself recursively. Apart from the base case (line 5 of Figure 2), where the recursion bottoms out, two different cases are considered – the reduction and selection cases (lines 7–15 and lines 17–22 of Figure 2, respectively). In the reduction case a cluster C ∈ with k = |C| ≥ 3 is replaced by a smaller cluster C'. In particular, in lines 7–11 we let Θ_C = c₁, ..., c_k be the ordering of C with c₁ = x, c₂ = y, c₃ = z, and put C' = (C\{x, y, z}) ∪ {u, v} and Θ_C'= u, v, c₄, ..., c_k, where u and v are two new elements not contained in Y. Then, in lines 12–14, we define a distance function d' on the set Y' = (Y\{x, y, z}) ∪ {u, v} using the formulae:

(1)

where α, β and γ are positive real numbers satisfying α + β + γ = 1 (note that these formulae slightly differ from the ones given in [2] in which there is a typographical error). In the current implementation of Neighbor-Net the values α = β = γ = 1/3 are used.

When FINDORDERING is recursively called with the new collection of clusters and distance function d' it returns an ordering of Y' that is compatible with . Thus, there exists i ∈ {1, ..., n - 2} such that either u = and v = or v = and u = . The resulting ordering Θ of Y is then defined (in line 14) as follows:

(2)

This completes the description of the reduction case.

We now describe the selection case. Note that in view of line 6 this case only applies if every cluster in contains at most two elements. In lines 17–18, two clusters C₁, C₂ ∈ are selected and replaced by the single cluster C' = C₁ ∪ C₂. The clusters C₁ and C₂ are selected as follows: We define a distance function on the set of clusters by

and select C₁, C₂ ∈ , C₁ ≠ C₂ that minimize the quantity

(3)

where m is the number of clusters in . The function Q that is used to select pairs of clusters is called the Q-criterion. Note that this is a direct generalization of the selection criterion used in the NJ algorithm [2]. However, using only this criterion yields a method that is not consistent as illustrated in Figure 3. So, once the clusters C₁ and C₂ have been selected we use a second criterion to determine an ordering Θ_C' in line 19 for the new cluster C'. In particular, for every x ∈ C₁ ∪ C₂ we define

put = m + |C₁| + |C₂| - 2, and select x₁ ∈ C₁ and x₂ ∈ C₂ that minimize the quantity

[d](x1, x2) = ( - 2)d(x1, x2) - R(x1) - R(x2).

(4)

We then choose an ordering Θ_C' in which x₁ and x₂ are neighbors and for which every two elements that were neighbors in C₁ or C₂ remain neighbors. This completes the description of the selection case, and hence the description of the procedure FINDORDERING.