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 » Preliminaries

Preliminaries

- Consistency of the Neighbor-Net Algorithm

2 Preliminaries

In this section we present some notation that will be needed to describe the Neighbor-Net algorithm. We will assume some basic facts concerning phylogenetic trees, more details concerning which may be found in [11].

Throughout this paper, X will denote a finite set with cardinality n. A split S = {A, B} (of X) is a bipartition of X. We let Ϭ = Ϭ(X) = {{A, X\A}|Ø ⊂ A ⊂ X} denote the set of all splits of X, and call any non-empty subset of Ϭ(X) a split system. A split weight function on X is a map ω: Ϭ(X) → _≥0. We let Ϭ_ω denote the set {S ∈ Ϭ|ω(S) > 0}, the support of ω.

Let Θ = x₁, ..., x_n be an ordering of X. A split S = {A, B} is compatible with Θ if there exist i, j ∈ {1, ..., n}, i ≤ j, such that A = {x_i, ..., x_j} or B = {x_i, ..., x_j}. Note that if a split is compatible with an ordering Θ it is also compatible with its reversal x_n, ..., x₂, x₁ and with ordering x₂, ..., x_n, x₁. We let Ϭ_Θ denote the set of those splits in Ϭ(X) which are compatible with ordering Θ. A split system Ϭ' is compatible with Θ if Ϭ' ⊆ Ϭ_Θ. In addition a split system Ϭ' ⊆ Ϭ(X) is circular if there exists an ordering Θ of X such that Ϭ' is compatible with Θ. Note that any split system corresponding to a phylogenetic tree is circular [[11], Ch. 3], and so circular split systems can be regarded as a generalization of split systems induced by phylogenetic trees. A split weight function ω is called circular if the split system Ϭ_ω is circular. A distance function on X is a map d: X × X → _≥0 such that for all x, y ∈ X both d(x, x) = 0 and d(x, y) = d(y, x) hold. Note that any split weight function ω on X induces a distance function d_ω on X as follows: For a split S = {A, B} ∈ Ϭ(X) define the distance function or split metric d_S by

and put

for all x, y ∈ X. A distance function d is called circular if there exits a circular split weight function ω such that d = d_ω. An ordering Θ of X is said to be compatible with d if there exists ω such that d = d_ω and Ϭ_ω ⊆ Ϭ_Θ. Note that the representation of a circular distance function d is unique, i.e., if d = and d = for circular split weight functions ω₁ and ω₂ then ω₁ = ω₂ holds [10].

Circular distances were introduced in [10] and have been further studied in, for example, [12] and [13]. Just as any tree-like distance function on X can be uniquely represented by a phylogenetic tree [[11], ch. 7], any circular distance function d can be represented by a planar phylogenetic network such as the one pictured in Figure 1[14]. The program SplitsTree [9] allows the automatic generation of such a network for d by computing a circular split weight function ω with d = d_ω.