table of contents table of contents

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

Home » Biology Articles » Molecular Biology » Consistency of the Neighbor-Net Algorithm » 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 Θ = x1, ..., xn 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 = {xi, ..., xj} or B = {xi, ..., xj}. Note that if a split is compatible with an ordering Θ it is also compatible with its reversal xn, ..., x2, x1 and with ordering x2, ..., xn, x1. 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 dS 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 ω1 and ω2 then ω1 = ω2 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ω.

rating: 1.00 from 1 votes | updated on: 1 Sep 2007 | views: 8750 |

Rate article: