.

Crypto Isomorphisms in Phylogenetic Combinatorics

New Plymouth January 05, 2003

.

X-Trees Metrics over X

Split Systems over X Quartet Systems over X

.

X-Trees

Definition

Given a finite set X, an X-Tree T is a finite tree T = (V, E) with vertex set V and edge set E such that

• X is the set of leaves of T,

• there is no vertex of degree 2 in V.

.

Metrics over X

Definition

A metric D over X is a map

D : X × X → R

such that

• D(a, b) = D(b, a),

• D(a, c) ≤ D(a, b) + D(b, c),

• and D(a, a) = 0 holds for all a, b, c ∈ X.

.

Split Systems over X

.

Split Systems over X

Definition

A split system S over X is a subset of the set S(X) consisting of all splits of X, i.e. of all pairs {A, B} of subsets A, B of X with

• A ∩ B = ∅,

• ∅ ≠ A, B,

• and A ∩ B = X.

.

Quartet Systems over X

.

Quartet Systems over X

Definition

A quartet system Q over X is a subset of the set Q(X) consisting of all 2,2-splits of X, i.e. of all pairs {A, B} of subsets A, B of X with

• A ∩ B = ∅ and

• #A = #B = 2.

.

Quartet Systems over X

Definition

A quartet system Q over X is a subset of the set Q(X) consisting of all 2,2-splits of X, i.e. of all pairs {A, B} of subsets A, B of X with

• A ∩ B = ∅ and

• #A = #B = 2.

If A = {a, a′} and B = {b, b′}, we also write aa′|bb′ instead of {{a, a′}, {b, b′}}.

.

Relation with experimental data

.

Relation with experimental data

Experimental data often provide characters for X, i.e. maps

φ : X → C, φ′ : X → C′, …

from the set X in question into some other sets.

.

Relation with experimental data

Experimental data often provide characters for X, i.e. maps

φ : X → C, φ′ : X → C′, …

from the set X in question into some other sets.

Metrics:

Experimental data often provide characters for X, i.e. maps

φ : X → C, φ′ : X → C′, …

from the set X in question into some other sets.

Metrics:

Given a family φ_{i} : X → C_{i} (i ∈ I) of such characters,

• metrics D_{i} on C_{i} (i ∈ I) give rise to a metric D : X × X → R defined by

D(a, b) := ∑_{i∈I} D_{i}(φ_{i}(a), φ_{i}(b)),

for all a, b ∈ X.

.

Relation with experimental data

Experimental data often provide characters for X, i.e. maps

φ : X → C, φ′ : X → C′, …

from the set X in question into some other sets.

Split systems:

Experimental data often provide characters for X, i.e. maps

φ : X → C, φ′ : X → C′, …

from the set X in question into some other sets.

Split systems:

Given a family φ_{i} : X → C_{i} (i ∈ I) of such characters,

• any family (S_{i})_{i∈I} of split systems S_{i} over C_{i} gives rise to an induced split system

S_{i} := ∪_{i∈I}φ_{i}^{−1}(S_{i})

where φ_{i}^{−1}(S_{i}) is defined by

φ_{i}^{−1}(S_{i}) := {{A, B} ∈ S(X) | {φ_{i}(A), φ_{i}(B)} ≤ S_{i}}

Here, we write {A, B} ≤ S for two subsets A, B of a set C and a split system S of C if there exists a split S = {A′, B′} in S with A ⊆ A‘ and B ⊆ B‘.

Quartet systems:

Quartet systems:

Rate matrices R(a, b) = (R(a, b)_{i,j∈I}), one for each pair a, b from a family of aligned sequences

• as considered in the context of log det methods (note that the log det distance of a and b is just, by definition, the trace of R(a, b))

• and recently computed extensively for many sequence families by Alex Grossmann,

give rise, for any 2,2-split ab|cd of distinct sequences a, b, c, d from such a family, rather useful confidence values

Conf(ab|cd) :=

⟨R(a, b) | R(c, d)⟩ = ∑_{i,j} R(a, b)_{i,j}R(c, d)_{i,j}

for the 2,2-split ab|cd to represent the phylogenetically “correct” quartet tree from which quartet systems can easily be gathered.

Quartet systems:

In addition, any tree-reconstruction method based on such data and applied to all 4-subsets Y of X (where basically all such methods are fast) provides interesting quartet systems.

Topics to be studied

20

Topics to be studied

How to encode X-trees by split systems, quartet systems, and metrics over X?

Topics to be studied

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

Note that this question includes in particular the question of how to decide whether, given some split or quartet system, or some map defined on a subset of X ×X, when does there exist a consistent extension?

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

Weighted versions.

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

Weighted versions.

Rooted X-trees —the affine versus the projective approach to tree reconstruction.

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

Weighted versions.

Rooted X-trees —the affine versus the projective approach to tree reconstruction.

Restrictions to subsets of X.

.

How to encode an X-tree

T = (V, E)

by a split system over X?

.

How to encode an X-tree

T = (V, E)

by a split system over X?

Given any edge e ∈ E, the two subets A, B of X in the two connected components of

T_{e} := (V, E − {e})

form an X-split S_{e} := {A, B}.

.

How to encode an X-tree

T = (V, E)

by a split system over X?

Given any edge e ∈ E, the two subets A, B of X in the two connected components of

T_{e} := (V, E − {e})

form an X-split S_{e} := {A, B}. One defines

S_{T} := {S_{e} | e ∈ E^{∗}}

where E^{∗} denotes the set of internal edges of the tree T.

.

How to encode an X-tree

T = (V, E)

by a quartet system over X?

.

How to encode an X-tree

T = (V, E)

by a quartet system over X?

For any subset Y of X, let T (Y) denote the Y -tree induced on Y by T, and put

Q_{T} := ∪_{Y ∈\binom{X}{4}}S_{T (Y)}.

.

How to encode an X-tree

T = (V, E)

by a quartet system over X?

For any subset Y of X, let T (Y) denote the Y -tree induced on Y by T, and put

Q_{T} := ∪_{Y ∈\binom{X}{4}}S_{T (Y)}.

Note that S_{T (Y)} contains at most one split for every 4subset Y of X, and that this split — if it exists at all — is always a 2,2-split.

.

How to encode an X-tree

T = (V, E)

by a by metric defined on X?

.

How to encode an X-tree

T = (V, E)

by a metric defined on X?

One defines a metric

D = D_{T} : X × X → R

by letting D_{T}(a, b) denote the length of the (unique) path from a to b, for all a, b in X.

.

Theorem

Given two X-trees T and T′, the following assertions are equivalent:

(i) T and T′ are canonically isomorphic, (ii) the splits systems S_{T} and S_{T′} coincide, (iii) the quartet systems Q_{T} and Q_{T′} coincide, (iv) the metrics D_{T} and D_{T′} coincide.

.

Theorem

Given a split system S ⊆ S(X) over X, there exists an X-tree T with

S_{T} = S

if and only if S is compatible, i.e. there exist subsets A ∈ S and A′ ∈ S′ with

A ∪ A′ = X

for any two splits S, S′ in S.

.

Theorem

Given a quartet system Q ⊆ Q(X) over X, there exists an X-tree T with Q_{T} = Q if and only if

• Q is thin, i.e. one has

#(Q ∩ {ab|cd, ac|bd, ad|bc}) ≤ 1,

for any four distinct elements a, b, c, d in X,

• Q is transitive, i.e. one has

ab|cd, ab|de ∈ Q ⇒ ab|ce ∈ Q

for any five distinct elements a, b, c, d, e in X,

• and Q is balanced, i.e. one has

ab|cd, bc|de ∈ Q ⇒ ab|de ∈ Q,

also for any five distinct elements a, b, c, d, e in X.

.

Theorem

Given a metric

D : X × X → R : (a, b) ↦ ab

there exists an X-tree T with

D_{T} = D

if and only if

• D satisfies the four-point condition

ab + cd ≤ max(ac + bd, ad + bc) for all a, b, c, d ∈ X ,

• there exists, for any a, a′, b ∈ X with a, a′ ≠ b,

some b′ ∈ X ab + a′b′ = 2 + aa′ + bb′.

Remarkably, defining D(ab : cd) and D(ab : c) for all a, b, c, d ∈ X by

D(ab : cd) := \frac{1}{2} max (ac + bd, ad + bc) − (ab + cd)

and

D(ab : c) := min (D(ab : cx) | x ∈ X, D(ab : cx) > 0),

(with D(ab : c) := ∞ in case D(ab : cx) ≤ 0 holds for all x ∈ X, of course), the four-point condition is obviously equivalent with the condition that D(ab : cd) ≥ 0 holds for all a, b, c, d ∈ X while, assuming that the four-point condition holds, the second condition is equivalent with the assertion that

D(ab : c) = 1

holds for all a, b, c ∈ X with a, b ≠ c.

And both conditions together imply that

1/2(ab + bc + ca) ∈ Z

and, hence, in particular ab ∈ Z holds for all a, b, c ∈ X.

From split to quartet systems and back

43

From split to quartet systems and back

Given any split system S over X, one can associate with S the quartet system Q = Q_{S} over X defined by

Q_{S} := {aa′|bb′ ∈ Q(X) | aa′|bb′ ≤ S}

or, equivalently, by

Q_{S} := ∪_{{A,B}∈S} Q_{{A,B}}

where Q_{{A,B}} denotes the set of all 2,2-subsplits of a split {A, B} ∈ S(X), i.e. the set

Q_{{A,B}} := {aa′|bb′ ∈ Q(X) | a, a′ ∈ A; b, b′ ∈ B}.

Given any split system S over X, one can associate with S the quartet system Q = Q_{S} over X defined by

Q_{S} := {aa′|bb′ ∈ Q(X) | aa′|bb′ ≤ S}.

And given any quartet system Q over X, one can associate with Q the split system S = S_{Q} over X defined by

S_{Q} := {{A, B} ∈ S(X) | Q_{{A,B}} ⊆ Q}.

Clearly, one has

Q_{S_{T}} = Q_{T} and S_{Q_{T}} = S_{T}

for every X-tree T.

This sets up a Galois correspondence between split and quartet systems over X: Indeed, given any split system S and any quartet system Q over X, one has

Q_{S} ⊆ Q ⇔ S ⊆ S_{Q}.

Thus, putting Q := Q_{S} for some S as above, we see that

S ⊆ S_{Q_{S}}

holds for every split system S, and putting S := S_{Q} for some Q as above, we see that, conversely,

Q_{S_{Q}} ⊆ Q

holds for every quartet system Q.

Further, applying this last observation for some split system S and Q_{0} := Q_{S}, we get

Q_{S_{Q_{0}}} ⊆ Q_{0} = Q_{S}

while S ⊆ S_{Q_{S}} = S_{Q_{0}} implies

Q_{S} ⊆ Q_{S_{Q_{0}}}.

So, we have

Q = Q_{S_{Q}}

for some quartet system Q over X if and only Q is of the form Q = Q_{S} for some split system S.

Similarly, one sees that

S = S_{Q_{S}}

holds for some split system S over X if and only S is of the form S = S_{Q} for some quartet system Q.

It has been observed moreover in [A Relational Approach to Split decomposition] that the quartet systems Q over X with Q = Q_{S_{Q}} can be characterized by a 7-point condition, and that {A_{1} ∪ A_{2} ∪ A_{3}, B_{1} ∩ B_{2} ∩ B_{3}} ∈ S_{Q_{S}} hold for any three splits {A_{1}, B_{1}}, {A_{2}, B_{2}}, {A_{3}, B_{3}} in a split system S in case one has

A_{1} ∪ A_{2} = A_{2} ∪ A_{3} = A_{3} ∪ A_{1}.

Moreover, many split systems including the compatible split systems and the cyclic split systems, i.e. the split systems S ⊆ S(X) for which there exists a linear order ≤ on X such that for every split S ∈ S there exists some A in S with A = {x ∈ X | a ≤ x ≤ a′} for some a, a′ ∈ A, are known to satisfy the relation S = S_{Q_{S}}.

Note that the quartet systems Q = Q_{S} corresponding to maximal cyclic split systems can be characterized as follows: ...

From split systems to metrics and back

Given a split system S over X, one can associate with S the metric

D = D^{S} : X × X → R : (a, b) ↦ ab^{S}

over X that associates to any a, b in X the number ab^{S} of splits in the subset S(a|b) of S consisting of all splits in S that separate a from b, i.e. those S in S for which some A ∈ S with a ∈ A and b ∉ A exists, i.e. we define

S(a|b) := {{A, B} ∈ S | a ∈ A, b ∈ B}

and

D^{S}(a, b) = ab^{S} := #S(a|b).

Conversely, given a metric D : X × X → R : (a, b) ↦ ab, one can associate with D the split system S = S_{D} over X that contains exactly those splits

S = {A, B} ∈ S(X)

for which

aa′ + bb′ < min (ab + a′b′, ab′ + a′b)

holds for all a, a′ ∈ A and b, b′ ∈ B.

One can also associate with D the, generally larger, split system S = S^{D} over X that contains exactly those splits

S = {A, B} ∈ S(X)

for which

aa′ + bb′ < max (ab + a′b′, ab′ + a′b)

or, equivalently,

D(aa′ : bb′) > 0

holds for all a, a′ ∈ A and b, b′ ∈ B.

Note that S_{D} = S^{D} holds for all metrics D that satisfy the four-point condition.

Moreover, denoting the set of all one-splits, i.e. of all splits of X of the form {X − {x}, {x}} for some x in X by S_{1}(X):

S_{1}(X) := {{X − {x}, {x}} | x ∈ X},

one has

S_{T} ∩ S_{1}(X) = ∅

as well as

D^{S_{T} ∪S_{1}(X)} = D_{T}

and

S_{T} ∪ S_{1}(X) = S_{D_{T}} = S^{D_{T}}

for every X-tree T.

Note also that further interesting variations for associating a split system with a metric are possible.

Theorem

Given any split system S ⊆ S(X), the following assertions are equivalent:

• S = S_{D} holds for D := D^{S},

• S is of the form S_{D} for some metric D over X,

• S is compatible,

• S − S_{1}(X) is of the form S_{T} for some X-tree T.

Moreover, the metric D^{S∪S_{1}(X)} associated with S ∪S_{1}(X) is also of the form D_{T} for some X-tree T if these assertions hold.

Conversely, we have also the following

Theorem

Given any metric

D : X × X → R : (a, b) ↦ ab,

the following assertions are equivalent:

• D = D^{S} holds for S := S_{D},

• D is of the form D = D^{S} for some compatible split system S ⊆ S(X),

• there exists a tree T = (V, E) and a map φ : X → V with D(a, b) = D_{T}(φ(a), φ(b)) for all a, b ∈ X

(where D_{G}(u, v) denotes the length of the path from u to v in a connected graph G = (V, E), for any two vertices u, v ∈ V),

• one has

D(ab : cd) ≥ 0

and (ab + bc + ca)/2 ∈ Z for all a, b, c, d ∈ X, as well as

D(ab : c) = 1

for all a, b, c ∈ X with a, b ≠ c.

Note that, while S_{D} is always a compatible split system, the split system S^{D} is only weakly compatible, i.e. given any three splits

S_{1} = {A_{1}, B_{1}}, S_{2} = {A_{2}, B_{2}}, S_{3} = {A_{3}, B_{3}},

one of the four sets

A_{1} ∩ A_{2} ∩ A_{3},
A_{1} ∩ B_{2} ∩ B_{3},
B_{1} ∩ A_{2} ∩ B_{3},

or

B_{1} ∩ B_{2} ∩ A_{3}

is always empty, and that a split system S is weakly compatible if and only it is of the form S = S^{D} for some metric D in which case one has S = S^{D} in particular for D := D^{S}.

From split systems to metrics and back

Next, we define

S(A|B) := {{A′, B′} ∈ S | A ⊆ A′, B ⊆ B′} as well as

D_{S}(A|B) := #S(A|B)

for any split system S and all subsets A, B of X, and S(a_{1} … a_{n}|b_{1} … b_{m}) := S({a_{1}, …, a_{n}}|{|b_{1}, …, b_{m}}) as well as

D_{S}(a_{1} … a_{n}|b_{1} … b_{m}) := #S(a_{1} … a_{n}|b_{1} … b_{m}) for all a_{1}, …, a_{n}, b_{1}, …, b_{m} ∈ X.

From split systems to metrics and back

Noting that

ab^{S} = D_{S}(a|b) =

D_{S}(acd|b) + D_{S}(ac|bd) + D_{S}(ad|bc) + D_{S}(a|cdb) holds for any elements a, b, c, d ∈ X, we get that ab^{S} + a′b^{′S} − aa^{′S} − bb^{′S} = 2(D_{S}(aa′|bb′) − D_{S}(ab|a′b′)) and, therefore, D^{S}(aa′ : bb′) = D_{S}(aa′|bb′)−min (D_{S}(ab|a′b′), D_{S}(ab′|a′b)) holds for any four elements a, a′, b, b′ in X.

Thus, taking into account that a split system S is weakly compatible if and only if at least one of the three sets S(aa′|bb′), S(ab|a′b′), S(ab′|a′b) is empty for any four elements a, a′, b, b′ in X, we see that

max(D^{S}(aa′ : bb′), 0) = D_{S}(aa′|bb′)

holds for any four elements a, a′, b, b′ in X.

Consequently, the metrics D with D = D^{S} for S := S^{D} can be characterized as follows:

Theorem

Given any metric

D : X × X → R : (a, b) ↦ ab,

the following assertions are equivalent:

• D = D^{S} holds for S := S^{D}

• D is of the form D = D^{S} for some weakly compatible split system S ⊆ S(X),

• one has

max(D(ab : cd), 0) ≤

max(D(ax : cd), 0) + max(D(ab : xd), 0),

D(ab : c) ∈ {1, ∞},

and

(ab + bc + ca)/2 ∈ Z

for all a, b, c, d ∈ X.

Please check wether this is really true?

In consequence, associating the split system S_{D^{S}} to a split system S defines an idempotent operator or projection that maps the set of all split systems over X onto the set of all compatible split systems over X, while associating S^{D^{S}} to S defines a projection that maps the set of all split systems over X onto the set of all weakly compatible split systems over X.

Question: Given an arbitrary split system S, how can we describe the compatible or weakly compatible split systems directly that result from applying either one of these projections?

Associating with a single split S = {A, B} in S(X) the metric D^{S} := D^{{S}} that maps any x, y in X onto 0 in case x, y ∈ A or x, y ∈ B holds, and onto 1 else, does not only induce the map S ↦ D^{S} from split systems to metrics considered above. It also induces a linear map

λ = λ_{X} : R^{S(X)} → M(X) : w ↦ ∑_{S∈S(X)} w(S) D^{S}

from the space R^{S(X)} of all maps w from S(X) into R into the space M(X) = M(X, R) of all symmetric maps D from X × X into R that vanish on the diagonal, as well as — by restriction — an additive map

λ|_{Z} : Z^{S(X)} → M(X, Z)

from the Z-lattice Z^{S(X)} of all integer-valued maps w in R^{S(X)} into the Z-lattice M(X, Z) of all integer-valued maps in M(X, R).

Remarkably,

• the support

supp(r) := {S ∈ S(X) | r(S) ≠ 0} of every non-zero element r in the kernel of λ has cardinality at least 7 (for a simple proof,

see next page),

• defining, for each partition of X into four non-empty subsets A_{1}, A_{2}, A_{3}, A_{4}, the map r_{A_{1},A_{2},A_{3},A_{4}} ∈ Z^{S(X)} from S(X) into Z by

r_{A_{1},A_{2},A_{3},A_{4}}({A_{i}, X − A_{i}}) := 1

for i = 1, …, 4,

r_{A_{1},A_{2},A_{3},A_{4}}({A_{i} ∪ A_{j}, X − (A_{i} ∪ A_{j})}) := −1 for 1 ≤ i < j ≤ 3, and r_{A_{1},A_{2},A_{3},A_{4}}(S) := 0 for every other split S in S(X), we get elements in this kernel whose support contains exactly 7 distinct splits,

• every other element r in this kernel is an R-linear — and in case r ∈ Z^{S(X)} even a Zlinear — combination of these specific elements.

Please check whether this is really true.

One can prove the fact that the support of every non-zero element r in the kernel of λ has cardinality at least 7 by induction on n = #X as follows: In case n ≤ 3, the metrics of the form D^{S} with S ∈ S(X) are linearly independent, and in case n = 4, the only linear relation between such metrics is — up to a scalar — the relation

∑_{S∈S(X)} r_{A_{1},A_{2},A_{3},A_{4}}(S) D^{S} = 0

with A_{1}, A_{2}, A_{3}, A_{4} being the only partition — up to relabeling — of X into four distinct nonempyty subsets involving all 7 non-trivial splits of X. Now assume that there are no elements r in the kernel of λ_{Y} with support of cardinality less than 7 for all proper subsets Y of X. And assume that r ∈ R^{S(X)} is an element in the kernel of λ_{Y} with a support of cardinality at most 6. Clearly, the relation

∑_{S∈S(X)} r(S) D^{S} = 0

and our inductive assuption applied to Y := X − {x} for any x ∈ X implies that for every split S = {A, B} in suppr with x ∈ A ≠ {x}, we must have 0 ≠ r(S) = −r({A − {x}, B ∪ {x}}) and therefore {A − {x}, B ∪ {x}} ∈ suppr. However, this implies that suppr = S(X) must hold in contradiction to #X > 3 and #suppr ≤ 6 because we can transform any split S ∈ S(X) into any one-split {a, X − {a}} by removing, step by step, any element x ≠ a from the subset A ∈ S with a ∈ A. So, assuming that there is at least one split in suppr, suppr must contain every other split as well. More precisely, the above argument shows that there is — up to scaling — exactly one r in R^{S(X)} that “restricts” to 0 on every proper subset Y of X in case #X is even, and none if #X is odd.

It follows in particular that we can view the

pair (Z^{S(X)}, ke(λ|_{Z})) as a 3-error correcting code over Z.

Reducing modulo 2, this code is in fact well known as the ??? code with parameters ???.

Furthermore, it is easy to check that, given any split system S over X, one must have

1/2(ab^{S} + bc^{S} + ca^{S}) ∈ Z

as before for any three elements because the sum ab^{S} + bc^{S} + ca^{S} counts each split in

S(a|bc) ∪ S(b|ca) ∪ S(c|ab)

exactly twice. However, it is not so easy to replace the condition

max(D(ab : cd), 0) ≤
max(D(ax : cd), 0) + max(D(ab : xd), 0),

above by one that, together with appropriate integrality conditions of the type considered above, is necessary and sufficient for D to be of the form D = D^{S} for some arbitrary split system S over X.

Please check what exactly is known or can be deduced about this.

From quartet systems to metrics and back

Given any quartet system Q over X and any two distinct elements a, b ∈ X, one can associate with Q and a, b the graph

G = G_{Q|a,b} := (X, E_{Q|a,b})

where E_{Q;a,b} is defined by

E_{Q|a,b} := \{\{c, d\} ∈ \binom{X − \{a, b\}}{2} | ab|cd ∈ Q\},

and then define a map

D = D_{Q} : X × X → R

by defining D_{Q}(a, b) to the number of connected components of G_{Q|a,b} diminished by 1.

Note that, in general, this need not be a metric.

From quartet systems to metrics and back

Conversely, given any metric

D : X × X → R,

one can associate with D the quartet system Q = Q_{D} over X consisting of all those ab|cd in Q(X) for which

D(a, b) + D(c, d) <
min (D(a, c) + D(b, d), D(a, d) + D(b, c))

or, alternatively, the quartet system Q = Q^{D} over X consisting of all those ab|cd in Q(X) for which

D(a, b) + D(c, d) <
max (D(a, c) + D(b, d), D(a, d) + D(b, c))

holds.

Also here, further interesting variations are possible.

How to encode X-trees by split systems, quartet systems, and metrics over X?

Consistency conditions: Which metrics, split, or quartet systems over X are induced by — and thus encode — an X-tree?

How to recode the distance, split, or quartet code of an X-tree in terms of its corresponding other codes? This works for larger classes of objects, too, and the resulting maps have adjoint functor interpretations.

How to decode X-tree codes? Applied to inconsistent data, this can produce X-diagrams or X-networks.

How to remove inconsistencies in metrics, split, and quartet systems?

Weighted versions.

Rooted X-trees —the affine versus the projective approach to tree reconstruction. Restrictions to subsets of X.

How to decode X-tree codes?

71

How to remove inconsistencies?

72

Weighted versions

73

Rooted X-trees

74

Restrictions to subsets of X

75