The Combinatorics of Evolutionary Trees—a Survey

L. A. Székely,* P. L. Erdős, M. A. Steel

ABSTRACT: We survey here results and problems from the reconstruction theory of evolutionary trees, which involve enumeration and inversion.

1. Introduction

Since the work of Darwin, there has been a dream of biologists: to reconstruct the tree of evolution of living things. That tree could be the only scientific basis for classification. In the last two decades the dramatic progress in molecular biology (reading long segments of genetic sequences) led to a new field, the theory of molecular evolution.

One assumes that the process of evolution is described by a tree, in which no degree exceeds 3, since evolutionary events are too rare to coincide. In this tree the leaves denote existing species represented by corresponding segments of aligned DNA sequences, the unlabelled branching vertices may denote unknown extinct ancestors; since fossils do not keep records of the DNA sequence. For a given set of existing species, we define their true tree by taking the subtree induced by them in the tree describing the process of evolution and undoing the vertices of degree two. We term any binary tree, in which leaves are labelled by the species and the branching vertices are unlabelled, an evolutionary tree. The very problem of reconstruction may be put in this way: given a set of species with corresponding segments of aligned DNA sequences, select the true tree from the set of possible evolutionary trees.

In this paper we assume that every bit of the aligned DNA sequence is one of the four nucleotides, A (Adenine), G (Guanine), C (Cytosine), T (Thymine); i.e. we neglect insertions and deletions. Biologists also would like to subdivide an edge of the true tree by a root r to denote a common ancestor and the direction of the evolution. However, if you have a procedure to solve the problem above, it easily can be applied to finding the root by outgroup comparison: add a new species to your list which is known to be far from all

* Research of the first author was supported by the A. v. Humboldt-Stiftung and the U. S. Office of Naval Research under the contract N-0014-91-J-1385 your species, reconstruct the larger true tree, and the neighbor of the new species can be considered the root of the smaller true tree.

It is not always the case, that A, G, C, T are the letters of the alphabet; a two-letter alphabet (identifying purines A = G and pyrimidines C = T), and a 20-letter alphabet of amino acids for protein sequences are also possible.

To solve the reconstruction problem, one needs a mathematical model that distinguishes the true tree in mathematical terms, and one also may expect, that the mathematical model in question corresponds to a known or generally assumed mechanism of molecular evolution. One also may expect several other attributes of the model, as Hendy, Penny, and Steel [PHS1] listed: a polynomial time algorithm for tree reconstruction, convergence on relatively short sequences to the true tree, insensitivity to small errors in input data, and falsifiabilty of the model in a Popperian sense. However, no tree reconstruction method proposed is powerful enough to meet all these criteria; many popular ones do not even correspond to any assumed mechanism of molecular evolution. It is no surprise, that Penny, Hendy, Zimmer and Hamby [PHZH] can show sets of species, for which different evolutionary trees have been published on the basis of different data, and even on the basis of the same data, using different methods. In [PHS1], [PHS2], and other papers, Penny et al. gave a program to put the theory of evolutionary trees on a sound philosophical and mathematical foundation.

It is not the point of the present paper to overview advantages and shortcomings of all tree reconstruction methods. For a comparison of different methods, see [PHS1]. We restrict the present paper to our modest contribution, that involves enumeration and inversion, to that program. Sections 3-5 closely follow [SSE]. We give no proofs.

Cavalli-Sforza and Edwards [CSE] introduced the parsimony principle to the analogy of many minimum principles in science. In many instances the parsimony principle yields reasonably good trees, however no mechanism of evolution is accountable for it, and there are situations—where some branches of the true tree have significantly different rate of change—in which it may be false, see Felsenstein [F]. Section 2 is devoted to the parsimony principle and related enumeration results.

Section 3 describes a Fourier inverse pair depending on trees and Abelian groups, and specializes it to the group Z_{2}^{m}. Section 4 sets Kimura’s models of molecular evolution in terms of Section 3 and outlines the spectral analysis/closest tree method. Section 5 is devoted to the construction of a complete set of invariants for Cavender’s model and Kimura’s 3-parameter model, and Section 6 concludes.

2. The parsimony principle

Let C denote the letters of our alphabet, which frequently will be referred to as a set of colours, and let C_{m} denote the set of m−letter words over that alphabet. Let T be an evolutionary tree with leaf set L. We term a map χ : L ⟶ C_{m} as a leaf-colouration. The colouration χ̄ : V (T) ⟶ C_{m} is an extension of the leaf-colouration χ if the two maps are identical on the set L. The changing number of the colouration χ̄ is the number of pairs of <edge, letter position>, where end-vertices of the edge have different colours at the corresponding letter position according to χ̄. We term the minimum changing number of the tree T over all extensions of χ the length of T. The parsimony principle says, that the true tree has minimum length, i.e. maximum parsimony. Unfortunately, results of Foulds and Graham [FG] show that the decision problem, whether for a set of leaves and assigned words, an evolutionary tree with prescribed length exists, is NP-hard, even when |C| = 2. Therefore, from a statistical point of view, it is reasonable to ask for the expectation and variance of the length of a random evolutionary tree, in order to use this information as a selection principle (Steel [S1]). Not much is known yet on the variance, but there are some results on the expectation. The computation of the expectation can be reduced to the solution of the following enumeration problem.

Problem. Let f_{k}(a_{1}, ..., a_{t}) (t ≥ 2, a_{i} ≥ 1, n = a_{1} + ⋯ + a_{t}) denote the number of binary trees with a_{i} labelled leaves of colour i, with unlabelled branching vertices, with length k. Evaluate f_{k}(a_{1}, ..., a_{t}).

This enumeration problem is still open; not even a conjectured value of f_{k}(a_{1}, ..., a_{t}) is at hand. We list here the solved instances of the problem. Carter, Hendy, Penny, Székely and Wormald [CHPSW] proved the

Bichromatic binary tree theorem.

f_{k}(a, b) = (k − 1)!(2n − 3k)N(a, k)N(b, k)\frac{(2n − 5)!!}{(2n − 2m − 1)!!},  (1)

where a + b = n and

N(x, k) = \binom{2x − k − 1}{k − 1}(2x − 2k − 1)!!.  (2)

For more than 2 colours, results for extreme length values are available. Observe that with k colours present, the length is at least k − 1. For this extreme value, Carter & al.

[CHPSW] proved

f_{k−1}(a_{1}, ..., a_{k}) = \frac{(2n − 5)!!}{(2n − 2k − 1)!!}N(a_{1}, 1) ⋯ N(a_{r}, 1).

For a_{i} ≥ 2, using inclusion-exclusion, Steel [S1] went further to prove

f_{k}(a_{1}, ..., a_{k}) = \frac{(k − 1)(4(n − k)^{2} − 2n + k)(2n − 5)!!}{(2n − 2k + 1)!!}N(a_{1}, 1) ⋯ N(a_{k}, 1).

In another paper Steel [S2] obtained:

f_{2k}(k, k, k) = (k!)^{3} ∑_{s=1}^{k}[x^{k}]\frac{Q(x)^{s}}{s!} \frac{(6k − 5)!!}{(6k − 2s − 1)!!},  (3)

where [x^{i}]Q(x) = \frac{2(4i−3)!(6i−3)}{(3i−1)!i!}. Notice that with 3 colour classes of size k the length is at most 2k, an extreme case, again. D. Penny [personal communication] computed some small values of f for 3 colours, which may be useful for making and/or checking conjectures:

f_{m}(2, 2, 3) = 27, 318, 600 for m = 2, 3, 4;
f_{m}(2, 2, 4) = 165, 2610, 7620 for m = 2, 3, 4;
f_{m}(2, 3, 3) = 99, 1566, 5526, 3204 for m = 2, 3, 4, 5;
f_{m}(3, 3, 3) = 351, 6966, 40554, 60858, 19116 for m = 2, 3, 4, 5, 6;
f_{m}(2, 2, 5) = 1365, 27090, 106680 for m = 2, 3, 4;
f_{m}(2, 3, 4) = 585, 11610, 57420, 65520 for m = 2, 3, 4, 5.

A trivial, but useful formula in establishing more values of f is

f_{k}(a_{1}, ..., a_{r}, 1) = (2n − 5)f_{k−1}(a_{1}, ..., a_{r}).  (4)

Using (1) and (4), one easily extends the little table above for the values of f_{m}(1, a, b).

The first proof of the bichromatic binary tree theorem relied on generating functions, multivariate Lagrange inversion and computer algebra. Later on, Steel gave a proof from a combinatorial decomposition based on Menger’s theorem [S1], and Erdős and Székely [ES2] simplified his proof further. It has turned out, that (2) counts binary forests of k components on x labelled leaves, such that every component contains one vertex of degree two or zero [CHPSW], [E]. The term k!N(a, k)N(b, k) nearly present in (1) can be explained as such forests being built on both colour classes of leaves and then the trees are matched in all possible ways. Then the rest of (1) comes into play at building different trees of length k from the matched forests.

It became evident, that a solution of the general enumeration problem requires a good characterization of the fact, that the length of a tree is not less than t; for two colours Menger’s theorem provides for such a good characterization. A natural generalization of the length is the well-known multiway cut problem; given a graph G and N ⊆ V (G), find an edge set of minimum size, whose deletion separates each pairs of N. Dalhaus & al.

[DJPSY] showed that the multiway cut problem is NP-hard (even for planar graphs, if |N| is not bounded). Hence, the existence of such a good characterization is unlikely in general. For r ≥ 2 colours and (not necessarily binary) trees Erdős and Székely [ES3] proved the following min-max theorem to give good characterization:

Theorem. The length of a leaf coloured tree is equal to the maximum number of oriented paths, connecting differently coloured leaves, such that no edge is used by two oppositely oriented paths, and no two paths using the same edge end in the same colour.

However, this is not enough in itself, to solve the problem. Notice that it is unlikely that a product formula like (1) solves the problem, since the given numerical values have some large prime factors e.g. 43, 53, 89; and (3) does not suggest any closed form either.

We would like to close this section with applications and a by-product. The applications are in biology. The well-known astronomer Sir Fred Hoyle has suggested that the Earth is continually bombarded by viruses (including influenza viruses) that originate from comets. Henderson, Hendy and Penny [HHP] showed that his hypothesis may be rejected with very high probability; their basic mathematical tool was the bichromatic binary tree theorem. A further similar application, due to Steel, Hendy and Penny [SHP], applies the bichromatic binary tree theorem to calculate a permutation-based statistic for aligned sequences over the 2-letter alphabet, which allows for a test, whether the alignment is significantly ”tree-like”.

The byproduct is a bijection of Erdős and Székely [ES1] between some trees with unlabelled branching vertices and set partitions, which gives a unified technique to solve a number of tree enumeration problems. The motivation for the bijection came from counting evolutionary trees, which yields a semifactorial function (Cavalli-Sforza and Edwards [CSE]), like the number of partitions of a 2n-element set into 2-element sets. Had not we seen counting of trees with unlabelled branching vertices in biomathematics, we would hardly have ever come to this point.

3. A Fourier calculus

Let us be given a tree T with leaf set L and one arbitrary leaf R, called a root. We do not need that the tree is binary, but we assume that no vertex has degree two. Suppose that we are given a finite Abelian group G and for the edges e ∈ E(T) we have independent G-valued random variables ξ_{e} with p_{e}(g) := P rob(ξ_{e} = g) and ∑_{g∈G} p_{e}(g) = 1. Produce a random G-colouration of the leaves of the tree by evaluating ξ_{e} for every edge and giving as colour to the leaf l the product of group elements along the unique Rl path. Let f_{σ} denote the probability that we obtain a leaf colouration σ : L \ {R} ⟶ G. We need to recall some facts on characters and the Fourier transform, which can be found in [J] or in [EvS].

Lemma. Let G be a finite Abelian group, then (i) the character group Ĝ is isomorphic to G. (ii) if f : G → C is a complex-valued function and f̂: Ĝ → C is defined by

f̂(χ) = ∑_{g∈G} χ(g)f(g),

then for all g ∈ G

f(g) = \frac{1}{|G|} ∑_{χ∈Ĝ} \overline{χ(g)}f̂(χ).

(iii) The characters of a direct product group are exactly the products of characters.

Take G^{n−1} = the set of colourations σ : L \ {R} ⟶ G endowed with pointwise multiplication. Let χ = (χl ∈ Ĝ : l ∈ L \ {R}) be an ordered (n − 1)-tuple of characters. Then χ ∈ Ĝ^{n−1} acts on G^{n−1} according to Lemma (iii). For e ∈ E(T), set L_{e} = {l ∈ L : e separates l from R in T }. Define

r_{χ} = ∏_{e∈E(T)} ∑_{g∈G} p_{e}(g) ∏_{l∈L_{e}} χl(g).  (5)

In [SSE] we obtained the following inverse pair:

Theorem.

r_{χ} = ∑_{σ∈G^{n−1}} f_{σ} ∏_{l} χl(σ(l)) and  (6)
f_{σ} = \frac{1}{|G|^{n−1}} ∑_{χ∈Ĝ^{n−1}} r_{χ} ∏_{l} \overline{χl(σ(l))}.  (7)

In [SSE] we observed that (6) and (7) are equivalent by Lemma (ii) for any f : G^{n−1} ⟶ C and r : Ĝ^{n−1} ⟶ C; and it is no longer difficult to prove (6) with our f_{σ} and r_{χ}, as soon as the correct definition (5) is discovered. Let us specialize the Theorem for G = Z_{2}^{m}, since it admits a combinatorial description and has practical significance at the same time. Fourier calculus over Z_{2}^{m} occured many times in the literature (see [SSE] for some references), but not for the same purpose.

For every l ∈ L \ {R}, take a copy of G, G = Gl = Z_{2}^{m} and Ĝ = Ĝl by
Gl = {(σ_{1}, ..., σ_{m}) : σ_{i} ⊆ {l}}, Ĝl = {(X_{1}, ..., X_{m}) : X_{i} ⊆ {l}},

both endowed with the positionwise symmetric difference operation as group multiplication. For χl = (X_{1}, ..., X_{m}) ∈ Ĝl and gl = (σ_{1}, ..., σ_{m}) ∈ Gl define the action

χl(gl) = (−1)∑_{i=1}^{m} |σ_{i} ∩ X_{i}|.

For the direct product of Gl’s and Ĝl’s one has

G^{n−1} = {(σ_{1}, ..., σ_{m}) : σ_{i} ⊆ L \ {R}}, Ĝ^{n−1} = {(X′_{1}, ..., X′_{m}) : X′_{i} ⊆ L \ {R}}.

For the combinatorial interpretation the key observation is that the latter formula can be identified with

Ĝ^{n−1} = {(X_{1}, ..., X_{m}) : X_{i} ⊆ L, |X_{i}| even},

endowed by the positionwise symmetric difference operation as group multiplication and character action

(X_{1}, ..., X_{m})(σ_{1}, ..., σ_{m}) = (−1)∑_{i=1}^{m} |σ_{i} ∩ X_{i}|

under the correspondence

X_{i} = \{ \begin{matrix}X′_{i}, & if |X′_{i}| even, \\ X′_{i} ∪ \{R\}, & if |X′_{i}| odd. \end{matrix}

Now (5) turns into

rX_{1}, ..., X_{m} = ∏_{e∈E(T)} ∑_{g⊆M}(−1)|g ∩ {i : e ∈ P (T, X_{i})}|p_{e}(g),

where P (T, X_{i}) = {e ∈ E(T) : |L_{e} ∩ X_{i}| odd} (the unique T-join of the set X_{i} for a graph theorist); and (6)-(7) turns into (8)-(9)

rX_{1}, ..., X_{m} = ∑_{σ_{1},...,σ_{m}}(−1)∑_{j=1}^{m} |σ_{j} ∩ X_{j}|f_{σ_{1},...,σ_{m}},  (8)

f_{σ_{1},...,σ_{m}} = \frac{1}{2^{m(n−1)}} ∑_{X_{1},...,X_{m}}(−1)∑_{j=1}^{m} |σ_{j} ∩ X_{j}|rX_{1}, ..., X_{m}.  (9)

It is an important fact that the connecting matrices in (6)-(7) are— after normalization— unitary, and hence the connecting matrices in (8)-(9) are Hadamard.

4. Kimura’s models of molecular evolution

After the work of Kimura, the general assumption for the mechanism of molecular evolution is that changes in the DNA are random. It is assumed that changes at different sites are independent and of identical distribution. In case the data violates too much the condition on identical distribution, one may thin out the sequences by considering one site of each of the codons (the consecutive triplets of nucleotides encoding amino acids), particularly the third position, which is more redundant in the coding scheme than the other two positions, and therefore less influenced by natural selection. For m = 1, the model described in Section 3 specializes to a model of Cavender [C1], for which Hendy and Penny found the special case of the calculus above and applied it in their spectral analysis/closest tree method for tree reconstruction from sequences over a 2-letter alphabet [H], [HP1], [HP2]. Our part was the generalization for other groups; the practical importance of this generalization is mostly for m = 2, i.e. for sequences over the 4-letter alphabet A, G, C, T. We explain the m = 2 case in details, the explanation also applies, mutatis mutandis, to m = 1. It is an interesting paradox of the theory of evolution, that evolution is random at the molecular level and follows natural selection at a high level.

From now on we describe Kimura’s 3-parameter model [K2, K3] and some restricted versions of it, which are known as Kimura’s 2-parameter model [K1] and Jukes-Cantor model [JC], (the Jukes-Cantor model is more explicit in Neyman [N]). We follow the group theoretical setting of these models from Evans and Speed [EvS]. Take the symmetric difference group of the subsets of M = {1, 2}, which is the Kleinian group Z_{2} × Z_{2} with generators {1} and {2}. We compromise at this point and do not assume any longer, that evolutionary trees and the true tree are binary, but we assume, that they have no vertex of degree two. Take the true tree with a common ancestor r, a random subset of M is assigned under a certain (unknown) distribution to r. To every edge of the tree a random element of the Kleinian group is assigned independently. In the group theoretical setting of the Kimura’s models [EvS], the elements of the Kleinian group are identified with nucleotides, A ↔ ∅, G ↔ {2}, C ↔ {1}, T ↔ M. The random group element at r tells the original nucleotide value there, and the random variable at an edge describes the nucleotide change on that edge. In terms of biology, multiplication by ∅ on an edge causes no change in the nucleotide, multiplication by {2} causes transition, and multiplication by {1} or M causes one of the two possible types of transversions. To every leaf l the product of group elements along the unique path rl and in r itself is assigned. We have a random 4-colouration of the leaves (in fact, of all vertices) of the tree. That is Kimura’s 3-parameter model of molecular evolution. Kimura’s 3-parameter model allows for every edge e of the tree 4 arbitrary probabilities which sum up to 1, i.e. 3 free parameters, which may be different on different edges. Kimura’s 2-parameter model is similar, but further restricted by p_{e}({2}) = p_{e}(M) for all edges, and finally, the Jukes-Cantor model requires in addition p_{e}({1}) = p_{e}(M) for all edges.

It is very interesting, that the models above were equipped with substitution mechanisms for transitions and transversions that fit perfectly the group theoretical description, although this was not the motivation for their invention.

The model, in which we work, slightly differs from Kimura’s models, namely, we do not have a root r for an unknown common ancestor. This is in no way a serious loss, since, as we have already explained, it easily can be found by outgroup comparison. The root that we use, is, like in Section 3, one arbitrary leaf R, which represents an existing species. At every site of the sequence of R, we find a group element, and for normalization, in every leaf we multiply at the same site with the inverse of that group element. We refer to the sequences obtained as normalized sequences, note, that the normalized sequence of R contains identity elements only. From the normalized sequences we can read a leaf colouration at every bit; we count relative frequencies of leaf colourations and we treat these relative frequencies as if they were the f_{σ_{1},σ_{2}} leaf colouration probabilities from the model of Section 3. Observe that the propagation of group elements along the tree is direction dependent unless p_{e}(g) = p_{e}(g^{−1}) for all e and g; and without this condition the normalization would not make sense. However, for G = Z_{2}^{m}, the condition holds automatically.

We had a set of species with corresponding segments of aligned DNA sequences. We selected an arbitrary species for R and we normalized the sequences from R, and obtained an f′_{σ_{1},σ_{2}} relative frequency of the colouration (σ_{1}, σ_{2}) among the bits. Now we face the following problem: which tree T and probability distributions p_{e}(g) over its edges yield a leaf colouration probability f_{σ_{1},σ_{2}} = f′_{σ_{1},σ_{2}} for all (σ_{1}, σ_{2})? Working with real data, we must be satisfied with the best approximation in a reasonable norm. Having the p_{e}’s on the edges of the true tree allows for estimating a time scale, i.e. how far ago in time the evolutionary events in question did happen. The following theorem will give a solution for the problem; we formulate it for G = Z_{2}^{m}.

Let H denote the connecting Hadamard matrix in (8). Let f denote the vector of f_{σ_{1},...,σ_{m}}’s in (8). We adopt the convention of writing [v]j for the j^{th} coordinate of the vector v. Let K denote the Hadamard matrix, in which rows and columns are indexed with subsets of M, and the general h, g entry is

(−1)|h ∩ g|;

let p_{e} denote the vector, for which [p_{e}]h = p_{e}(h). For a positive vector v, we denote by log v the vector, for which [log v]i = log[v]i. We define an important set here, which is essential also for our results on invariants:

C(T) = \{(σ_{1}, ..., σ_{m}) : e ∈ E(T), h ⊆ M, σ_{i} = \{ \begin{matrix}L_{e}(T), & if i ∈ h, \\ σ_{i} = ∅, & otherwise \end{matrix} \}.  (10)

We generalized with Hendy [SHSE] the spectral analysis/closest tree method as follows:

Theorem. In the model of Section 3 for G = Z_{2}^{m},

[H^{−1} log Hf]_{σ_{1},...,σ_{m}} =
\{ \begin{matrix}0, & if (σ_{1}, ..., σ_{m}) ∉ C(T), \\ [K^{−1} log Kp_{e}]h, & if (∅, ..., ∅) ≠ (σ_{1}, ..., σ_{m}) ∈ C(T) \\ & defined by e and h in (10), \\ − ∑_{e∈E(T)} ∑_{∅≠h∈M} [K^{−1} log Kp_{e}]h, & if (σ_{1}, ..., σ_{m}) = (∅, ..., ∅), \end{matrix}  (11)

if all the logarithms are to be taken of positive numbers.

We note here, that the model of Section 3 does not imply the existence of the logarithms; however, for real data, there is no problem with them, due to the fact, that the probabilities p_{e}(g) are sufficiently small for g ≠ (∅, ..., ∅). Working with f arising from the model of Section 3, (11) and (10) tell the edges of the tree, and from (11) one can obtain p_{e} for all edges as well.

Working with empirical f′, the closest tree method, which is a branch-and-bound algorithm, determines then the evolutionary tree and the p_{e}’s over its edges, which yields f, such that H^{−1} log Hf approximates H^{−1} log Hf′ best in the Euclidean norm. The actual computation can be facilitated by writing H into a symmetric form achieving H^{−1} = 4^{1−n}H and by an adaptation of the fast Fourier transform. The inverse pair (8)-(9) is a necessary tool in proving (11).

5. Invariants

There is a continuing interest in the theory of invariants of evolutionary trees. Roughly speaking, an invariant is a polynomial identity, which holds on one evolutionary tree no matter what the probabilities assigned to the edges are, and usually does not hold on other evolutionary trees. The great advantage of using invariants is that one may discriminate against some trees without (strong) assumptions regarding the probabilities. Invariants were introduced by Cavender and Felsenstein [CF], [C2], [C3] and Lake [L]; and recently Evans and Speed [EvS] gave an algebraic technique based on Fourier analysis to decide if a polynomial is invariant or not for Kimura’s 3-parameter model.

Here we give explicitly a complete set of invariants for the mathematical model described in Sections 3-4 for G = Z_{2}^{m}. We still do not assume, that the tree is binary, but we assume, that no vertex has degree two. For a formal definition, let us be given a tree T and another tree T′ on the same leaf set L and root R. Introduce the indeterminates x_{σ_{1},...,σ_{m}} for all σ_{i} ⊆ L \ {R}, i = 1, 2, ..., m. A multivariate polynomial q(..., x_{σ_{1},...,σ_{m}}, ...) is an invariant of the tree T, if q vanishes after the substitution of f_{σ_{1},...,σ_{m}}^{T}’s into x_{σ_{1},...,σ_{m}}’s, for any ξ_{e} independent random variables over the edges of T. We expect from an invariant, that it is non-zero on a typical f_{σ_{1},...,σ_{m}}^{T′}; and hence searching for the true tree T′, having the observed f_{σ_{1},...,σ_{m}}^{T′}, we may reject a wrong candidate T, using its invariant(s).

A set of invariants of T is complete, if for any other tree T′, at least one of the polynomials does not vanish on some f_{σ_{1},...,σ_{m}}^{T′}. (Then, it comes for free, that it discriminates against almost all probability distributions.) For m = 1, our complete set of invariants was already found by Hendy [H], although it is not explicit there. These invariants are very similar to (11), but note, that (11) is not a polynomial identity. Define the polynomials

R_{X_{1},...,X_{m}} = ∑_{σ_{1},...,σ_{m}}(−1)∑_{i=1}^{m} |σ_{i} ∩ X_{i}|x_{σ_{1},...,σ_{m}}

for X_{i} ⊆ L, |X_{i}| even, i = 1, 2, ..., m. Now for an arbitrary given (ρ_{1}, ..., ρ_{m}) (ρ_{i} ⊆ L \ {R}, i = 1, 2, ..., m), define the polynomial δ_{ρ_{1},...,ρ_{m}} of all the variables x_{σ_{1},...,σ_{m}}:

δ_{ρ_{1},...,ρ_{m}} = ∏_{(X_{1},...,Xm): ; ∑{m \atop i=1} |X_{i}∩ρ_{i}|≡0 mod 2} R_{X_{1},...,X_{m}} − ∏_{(X_{1},...,Xm): ; ∑{m \atop i=1} |X_{i}∩ρ_{i}|≡1 mod 2} R_{X_{1},...,X_{m}}.

Theorem. The polynomials {δ_{ρ_{1},...,ρ_{m}} : (ρ_{1}, ..., ρ_{m}) ∉ C(T)} make a complete set of invariants of T.

It is worth making the following comment here. Evans and Speed [EvS] made the following conjecture: ”the number of algebraically independent invariants and the number of free parameters among the p_{e}(g)’s obtained by an informal parameter count add up to the number of variables x_{σ_{1},...,σ_{m}}”. Their first problem seems to have been to set candidates for these independent invariants. Assume that for g ≠ ∅, p_{e}(g) is a variable and p_{e}(∅) = 1 − ∑_{g≠∅} p_{e}(g), then the number of variables f_{σ_{1},...,σ_{m}} is 2^{m(n−1)}, the number of free parameters is |E(T)|(2^{m} − 1), the number of invariants given in the theorem is 2^{m(n−1)} −|C(T)| = 2^{m(n−1)} −|E(T)|(2^{m} −1)−1; and actually, we have one more invariant, ∑ f_{σ_{1},...,σ_{m}} = 1. The numerology works, but a positive result here would seem to involve algebraic geometry.

If it comes to application of these invariants, then values of polynomial functions must be computed instead of the polynomials, since computer algebra in many variables is rather prohibitive.

Problem. Generalize the above set of invariants to the case of arbitarary finite Abelian group.

6. Conclusion

The spectral analysis method has the advantage of using all the genetic information from the sequences, a property, which is not shared by most other reconstruction techniques. As it was pointed out in [H], [PHS1], [PHS2], it satisfies the Popperian program of falsifiability. Namely, the probabilities p_{e}(h) resulting from (11) might be negative numbers in the closest tree. That this can happen for artificial data but not for real data is a circumstancial evidence for the truth of Cavender’s model and Kimura’s 3-parameter model. There is an additional Popperian test for Kimura’s 3-parameter model, namely, that in (11), for (σ_{1}, σ_{2}) ∉ C(T), σ_{1} ≠ σ_{2}, [H^{−1} log Hf]_{σ_{1},σ_{2}} = 0; and this test does not even assume any knowledge on the closest tree.

Compared with spectral analysis, the parsimony principle is a rather rough exploratory method. However, with small binary trees and uniform small probabilities p_{e}(g) for any change (g ≠identity), p_{e}(g)^{2} << p_{e}(g), changing twice for a nucleotide is highly unlikely, and the parsimony principle turns into an approximation of Kimura’s model. The parsimony principle and the closest tree method are both minimum principles, although with different objective functions.

The second author proposes the development of randomized algorithms for tree reconstruction. In view of the successes of randomized algorithms in situations where deterministic algorithms fail, this approach could be promising, although nothing is done yet.

REFERENCES

[C1] J. A. Cavender, Taxonomy with confidence, Math. Biosci. 40(1978), 271–280.

[C2] J. A. Cavender, Mechanized derivations of linear invariants, Mol. Biol. and Evol. 6(1989), 301–316.

[C3] J. A. Cavender, Necessary conditions for the method of inferring phylogeny by linear invariants, Math. Biosci. 103(1991), 69–75.

[CF] J. A. Cavender and J. Felsenstein, Invariants of phylogenies in a simple case with discrete

states, J. Class. 4(1987), 57–71.

[CHPSW] M. Carter, M. D. Hendy, D. Penny, L. A. Székely, N. C. Wormald, On the distribution of

length of evolutionary trees, SIAM J. Discrete Math. 3(1990), 38–47.

[CSE] L. L. Cavalli-Sforza, A. W. F. Edwards, Phylogenetic analysis: models and estimation pro-

cedures, Evolution 21(1967), 550–570.

[DJPSY] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriu, P. Seymour, M. Yannakakis, The complexity

of multiway cuts, Extended abstract, 1983.

[E] P. L. Erdős, A new bijection on rooted forests, in: Proceedings of the 4^{th} French Combina-

torial Conference, Marseille, 1990, to appear.

[ES1] P. L. Erdős, L. A. Székely, Applications of antilexicographic order I: An enumerative theory of trees, Adv. Appl. Math. 10(1989), 488–496.

[ES2] P. L. Erdős, L. A. Székely, Counting bichromatic evolutionary trees, to appear in Discrete Appl. Math.

[ES3] P. L. Erdős, L. A. Székely, Evolutionary trees: An integer multicommodity max-flow–min-cut theorem, to appear in Adv. Appl. Math.

[EvS] S. N. Evans, T. P. Speed, Invariants of some probability models used in phylogenetic inference,

manuscript.

[F] J. Felsenstein, Cases in which parsimony or compatibility methods will be positively misleading, Syst. Zool. 27(1978), 401–410.

[FG] L. R. Foulds, R. L. Graham, The Steiner problem in phylogeny is NP-complete, Adv. Appl. Math. 3(1982), 43–49.

[H] M. D. Hendy, A combinatorial description of the closest tree algorithm for finding evolution-

ary trees, Discrete Math. 96(1991), 51–58.

[HHP] I. M. Henderson, M. D. Hendy, D. Penny, Influenza viruses, comets and the science of evolutionary trees, J. Theor. Biol. 140(1989), 289–303.

[HP1] M. D. Hendy, D. Penny, A framework for the quantitative study of evolutionary trees, Systematic Zoology 38(4) (1989), 297–309.

[HP2] M. D. Hendy, D. Penny, Spectral analysis of phylogenetic data, preprint, University of Biele-

feld, ZiF-Nr. 91/23.

[J] N. Jacobson, Basic Algebra II, W. H. Freeman and Co. San Francisco, 1980.

[JC] T. H. Jukes, C. Cantor, Evolution in protein molecules, in: Mammalian Protein Metabolism (H. N. Munro, ed.), 21–132, New York, Academic Press, 1969.

[K1] M. Kimura, A simple method for estimating evolutionary rates of base substitution through comparative studies of nucleotide sequences, J. Mol. Evol. 16(1980), 111–120

[K2] M. Kimura, Estimation of evolutionary sequences between homologous nucleotide sequences, Proc. Natl. Acad. Sci. USA 78(1981), 454–458.

[K3] M. Kimura, The Neutral Theory of Molecular Evolution, Cambridge University Press, Cambridge, 1983.

[L] J. A. Lake, A rate-independent technique for analysis of nucleic acid sequences: Evolutionary parsimony, Mol. Biol. Evol. 4(1987), 167–191.

[N] J. Neyman, Molecular studies of evolution: A source of novel statistical problems, in: Statistical Decision Theory and Related Topics, (S. S. Gupta and J. Yackel, eds.) 1–27, New York, Academic Press, 1971.

[PHS1] D. Penny, M. D. Hendy, M. A. Steel, Progress with methods for constructing evolutionary trees, Trends in Ecology & Evolution 7(1992)(3), 73–79.

[PHS2] D. Penny, M. D. Hendy, M. A. Steel, Testing the theory of descent, in: Phylogenetic Analysis of DNA Sequences, eds. M. M. Miyamoto, J. Cracraft, Oxford University Press, New York– London, 1991, 155–183.

[PHZH] D. Penny, M. D. Hendy, E. A. Zimmer, R. K. Hamby, Trees from sequences: panacea or

Pandora’s box? Aust. Syst. Bot. 3(1990), 21–38

[S1] M. A. Steel, Distributions on bicoloured binary trees arising from the principle of parsimony, to appear in Discrete Appl. Math.

[S2] M. A. Steel, Decompositions of leaf-coloured binary trees, to appear in Adv. Appl. Math.

[SHP] M. A. Steel, M. D. Hendy, D. Penny, Significance of the length of the shortest tree, J. Classification 9(1992), 71–90.

[SHSE] M. A. Steel, M. D. Hendy, L. A. Székely, P. L. Erdős, Spectral analysis and a closest tree method for genetic sequences, subbmitted to Appl. Math. Letters.

[SESP] L. A. Székely, P. L. Erdős, M. A. Steel, D. Penny, A Fourier inversion formula for evolutionary trees, submitted to Appl. Math. Letters.

[SSE] L. A. Székely, M. A. Steel, P. L. Erdős, Fourier calculus on finite sets and evolutionary trees, submitted to Discrete Math.

L. A. Székely, Eötvös University, Budapest, Hungary

and Institut für diskrete Mathematik, Bonn

P. L. Erdős, Hungarian Academy of Sciences, Budapest, Hungary M. A. Steel, University of Canterbury, Christchurch, New Zealand