Therefore, Parsimony may be applied only when the described lengths of edges cannot be met in the tree. Constructing evolutionary species trees is one of the most interesting problems in biology. It means nding the relations and mutual ancestors of existing and extinct species and also the time of formation of new species. Paleontology itself gives very poor information of species trees structure and time lengths of their edges. More precisely species trees can be built by analysis of genomes of species. One considers the set of species faig1N and j N their gene groups fGj g1K , where Gj = fAi gi=1 is a set of some functionally relative to each other genes. For example, one group can be responsible for hemoglobin production, another one can de ne the eye color and so on. Let the gene Aij be discovered in the species ai. Then in each j-th functional group one can establish the relations between the genes in the form of unrooted tree, where the leaves are the set of elements of j-th group. The structure of such trees for di erent groups can coincide (i.e. be topologically identical) or do not coincide. The number of these coincidences de nes the frequency of the corresponding gene tree. These frequencies are the base of pasimony method to constuct evolutionary trees which sometimes gives wrong results. If it is known that a method being applied to some type of problems may fail, why would anyone still use it in this area? Well, in phylogenetics most methods give probabilistic answers. Therefore, getting sometimes wrong answers doesn't necessarily imply that method is bad. To make a nal conclusion about the quality of the method one could estimate how often the wrong results appear. Then one would compare the obtained frequency with the frequencies of other methods' failures. Having this information on the table, a researcher can decide if the method is acceptable. However, we did better than this. We have found the set of all combinations of parameters of 5-taxon species tree when Parsimony is guaranteed to fail. Why tree with 5 taxa? It is known that Parsimony always gives right answers on k-taxon species tree for k = 3; 4. So, considering k = 5 is quite logical from computational point of view. Also the smaller k when things go bad, the louder the warning. The phylogenetics society has intuitive tendency to use Parsimony less and less. Nevertheless, many biologists still do it because of simplicity of the method. They should not be judged for that since simplicity is a strong argument. The results of this paper will show them the danger of Parsimony. However, forewarned is forearmed. If a researcher is sure that their resulting species tree doesn't have the combination of parameters we showed to be bad, they can safely use fast and simple Parsimony on 5-taxon trees. For a speci c rooted species tree with the known time lengths of the edges, using Coalescence method one can obtain the probabilities of gene trees. That allows to nd analytically the rooted species tree and region of
lengths of its edges, when parsimony fails. 2
We consider an evolution tree T (here and after we mean binary tree) of 5 species a, b, c, d and e with some parameters T1, T2, T3 { time in coalescence units between the branching points (see an example in g. 1).
Based on the Coalescent model [Rosenberg], [SemSte], [Wakeley], [Baum] the program COAL [DegnanSalter, WangDegnan] yields the probabilities of all 15 possible unrooted gene trees for 5 genes A, B, C, D, E, such that A is discovered in species a, B is discovered in the species b and so on.
All these species have related genes A, B, C, D, E, respectively. The genes originated from each other or from mutual ancestor. The branching in gene and species trees may not coincide. That creates a problem of inferring species trees from gene trees.
Also, for 5 species there are 15 di erent unrooted species trees or 105 rooted ones. In each species tree, one can t any of 15 di erent gene trees. However, the amount of mutations needed for this tting will di er generally from one gene tree to another. So, for each gene tree from these 15 and each species tree from the same 15 species trees one can correspond some non-negative integer number of mutations (parsimony score). These can be written in a 15 15 matrix M , where rows correspond to species trees and columns correspond to gene trees.
If one knows the frequencies of di erent gene trees P = (p1; :::; p15)T , then the mathematical expectation of the number of mutations for each of 15 possible species trees can be calculated by multiplying the matrix M by the vector-column P .
One can assume that the most probable species tree for the given sample of gene trees (or 15 gene trees with assigned probabilities) corresponds to the minimal expectation of mutations. This is the idea of Parsimony method [AllmanRhodes], its application to the problem of inferring species trees from gene trees is called Matrix Representation with Parsimony (MRP) [WangDegnan].
Here is the main question: Does the species tree with the minimal expectation from M P , where P is the vector of probabilities obtained, for example, from the Coalescent model [DegnanSalter] with given T1, T2, T3 for the tree T , present the unrooted version of the original rooted tree T ? Note that we compare rooted species tree with unrooted species tree. It is because the Coalescent method works with rooted trees while parsimony gives only unrooted ones.
It appeared in our work that on the sample of gene trees obtained from a caterpillar species tree with some parameters T1, T2, T3 by coalescence, the parsimony method gives an incorrect species tree.
Numerical Experiments. Performance of Unrooted MRP for 5-Taxon Species
Any 5 genes can be joined in one unrooted tree in 15 ways as given in the following list: 1: ((B; C); A; (D; E)), 4: ((A; E); B; (C; D)), 7: ((A; B); C; (D; E)), 10: ((A; B); D; (C; E)), 13: ((A; B); E; (C; D)), 2: ((C; D); A; (B; E)), 5: ((A; D); B; (C; E)), 8: ((A; D); C; (B; E)), 11: ((A; C); D; (B; E)), 14: ((A; C); E; (B; D)), 3: ((C; E); A; (B; D)), 6: ((A; C); B; (D; E)), 9: ((A; E); C; (B; D)), 12: ((A; E); D; (B; C)), 15: ((A; D); E; (B; C)).
Each unrooted tree may be transformed into a rooted tree by introducing a root to an edge. As a result, we have 7 rooted versions for each unrooted tree.
Step 1. Compute parsimony scores by Fitch-Hartigan [Hartigan] (Table 1).
Thus, if N~ = (N1; N2; :::; N15)T is the vector of counts of 15 topological trees in the input, M is the matrix of entries in Table 1 and vector-column S~ = (pars( 1); pars( 2); :::; pars( 15))T then S~ = M N~ . Here (pars( i) is parsimony score of species tree on the collection of gene trees 1; :::; 15.
Step 2. Pick the smallest entry or entries in S~ to determine the most parsimonious tree(s).
To study the 5-taxon case further we need to use Coalescent Theory. The coalescent model, introduced by Kingman in [Kingmn], describes the coalescence of lineages as we move backwards in time within a single species (Note that in biology the understanding of the word `species' may vary. Here we use this word in the same meaning as `population'). By \gluing" together such species or populations to form a tree, one gets the Multi-species Coalescent Model, which describes the production of gene trees within species trees.
mij for all 15 possible output trees with respect to the matrix 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Let 3 rooted species tree be 1 := ((((a; b) : T1; c) : T2; d) : T3; e), 2 := (((a; b) : T1; (c; d) : T2) : T3; e) and 3 := (((a; b) : T1; c) : T2; (d; e) : T3). They are rooted versions of 7; 13 and 7 again, respectively (see Fig. 2).
T1 a
T1
T3
Up to taxon names, these three are the only possible species trees. They are usually referred to as the caterpillar ( 1), pseudo-caterpillar ( 2) and pseudobalanced ( 3) species trees. a b c d e b c d e a b
c d e Using the program COAL [DegnanSalter, WangDegnan] to get probabilities of rooted gene trees and the formulas (1) for gij , we calculate the probabilities pi = p( ij 1) for i = 1; 15, which are listed in Table 2 (X := e T1 ; Y := e T2 ; Z := e T3 ;) after simpli cation in Maple 15.
The analytical comparison of these values we form in the following Proposition 1.For any X; Y; Z 2 (0; 1), the following inequalities hold: cat < cat; cat < cat; cat < cat < cat; cat < cat; cat < cat:
However, the 3D-graphs on Figures 3 show that the expressions cat and cat can not be put in one order for all X; Y; Z 2 (0; 1).
There is a large region were cat < cat but, nevertheless, there is also a region where cat < cat. The last de nes the parameters T1; T2; T3 where MRP will fail to recover the tree topology of the true species tree producing the gene tree distribution, even when given an arbitrary large sample of gene trees. Figure 3.left shows that provided Y is not too large, regardless of X; Z, MRP will return the correct species tree. e-T=1 e-T3 =
= e-T2 Let the pseudo-caterpillar species tree be 2 = (((a; b) : T1; (c; d) : T2) : T3; e). We use COAL, the formulas for gij and Maple 15 to calculate the probabilities pipc = p( ij 2) for i = 1; 15. Their list is shown in Table 3 after simpli cations. ppc
1 ppc
2 p1p3c p1p4c In the table 3: X = e T1 , Y = e T2 ; Z = e T3
Now assuming ppc = (p1pc; p2pc; ; p1p5c)T we see that the product spc := M ppc is the vector of expected parsimony scores of possible output trees with a pseudo-caterpillar species tree. We discover that in spc some entries are equal. Let's denote them as following pc := s1pc = s3pc = s5pc = s6pc = 4 XY Z6=90 Y =3 XY =18, pc := s2pc = s4pc = 3 XY Z6=90 X=3 + 2Y =3 + 5XY =18, pc := s7pc = s1p0c = 3 XY Z6=90 + 2X=3 Y =3 + 5XY =18, pc := s8pc = s9pc = s1p1c = s1p2c = 4 XY Z6=90 X=3 XY =18, pc := s1p3c = 2 + 2XY Z6=45 + 2X=3 + 2Y =3 + 2XY =9, pc := s1p4c = s1p5c = 4 + 2XY Z6=45 4XY =9.
Let's compare these expressions.
Proposition 2. For any X; Y; Z 2 (0; 1), the following inequalities hold: pc < pc; pc < pc; pc < pc; pc < pc; pc < pc:
This implies that if the true species tree is 5-taxon pseudo-caterpillar, MRP, for a su ciently large data set, will give with probability 1 the unrooted species tree topology for all T1; T2; T2 2 (0; 1). 6
The last tree we need to consider (since all other are just permutations of taxon names) is the pseudo-balanced species tree 3 = (((a; b) : T1; c) : T2; (d; e) : T3). The chain of actions is exactly the same that in previous two experiments. We omit it here. The result is Parsimony doesn't fail.
So, if the true species tree is 5-taxon pseudo-balanced 3, MRP, for a su ciently large data set, will give with probability 1 the correct unrooted species tree topology for all T1; T2; T2 2 (0; 1). 7 7.1
Caterpillar Subtree.
De nition 2. There is a rooted tree T with number of taxa equal to jT j =: n. Let Tcat(T ) be a caterpillar subtree of this tree. The number Cat(T ) := max jTcat(T )j for a particular tree T is called caterpillar score Tcat(T ) T
Cat(T ) is called caterpillar measure. for the tree T . The number cat(n) := min
jT j=n
It is clear that cat(n) is an increasing function with respect to n. There are may be a few consecutive numbers n such that cat(n) = k for some given natural k.
De nition 3. Let's call number rk := min n the revolution number.
cat(n)=k
Observe that for the caterpillar lengths 1; 2; 3 their revolution numbers are r1 = 1; r2 = 2; r3 = 3, because these trees are caterpillar themselves. Note, that the third and the second revolution numbers are connected by
The induction assumption yields an existence of caterpillar in T 00 with a length no less than k. One edge in T 0 together with the caterpillar in T 00 creates the caterpillar tree C with jCj = k + 1.
So, the revolution number for k + 1 is no greater than 2rk 1. If jT j 2 [rk; 2rk 1), then the worst bifurcation forms two subtrees T 0 and T 00 such that jT 0j; jT 00j < rk. Since rk is a revolution number, there are T 0 and T 00 which have only caterpillars C0; C00 and C00 with jC0j; jC00j < rk. Therefore, rk+1 is the revolution number.
Theorem 7.1 allows to continue the sequence of the revolution numbers for the caterpillar measures 3; 4; 5; 6; 7; ::: as rk = 3; 5; 9; 17; 33; :::, respectively. For trees with number of taxa in [rk; 2rk 1], the caterpillar measure is k.
MRP on trees with the number of taxa greater than 5 Theorem 2. If a true species rooted tree G^ contains 5-taxon caterpillar subtree, then MRP may fail to obtain the unrooted version of G^ from the set of gene trees generated by Coalescent model from G^.
Proof. For the number of species greater than 5 and the same number of genes one can make the following construction.
Take a caterpillar tree of 5 species a, b, c, d, e with T1, T2, T3 and root , such that parsimony fails ( g. 3). Take an arbitrary tree G, where every edge is very close to 0 (Ti 0, i > 4). Connect to G through its root and the edge with the length T4. Make T4 big enough so the genes A, B, C, D, E coalesce in if they didn't in . No matter what is on the upper end of , root of entire tree or inner node created by on some edge of G .
The numeration of n possible gene trees we do in the following way: First 15 trees will have the same subtree G and di erent topology or permutation of A, B, C, D, E. Other n 16 trees can be numerated in any order, and we set their probabilities p16; :::; pn equal to zero, since Ti, i 2 f5; :::; ng, can be taken in nitively small. Therefore, the set of gene trees is numerated and the probabilities of them are presented by vector-column p = (p1; :::; p15; p16; :::; pn)T , where all the entries below 15-th equal zero and the rst 15 are the same that obtained ones for 5-taxon experiment. The matrix Mn n has dimension n n, but only submatrix Mn 15 does participate in calculation of expectations of gene mutations due to p16; :::; pn = 0.
Moreover, the parsimony incorrect choice may be shown on submatrix M15 15 in upper corner. Observe that the elements of M15 15 are the sums of the elements of M obtained earlier in performance of MRP for 5-taxon trees 1 and some constant number generated by the constant subtree G with coalesced gene A + B + C + D + E. This means that each of sc1at, sc2at, ... , sc1a5t from Section 4 must be increased by the constant value V P115 pi, to be a new mathematical expectation for the new big tree. So, the minimum among the rst 15 rows must be achieved in the same index. Therefore, being wrong for 5-taxon caterpillar species tree the parsimony becomes wrong for the constructed tree G^ as well.
Corollary 1. MRP on a set of gene trees with 5 taxa or more may yield wrong result. If one applies MRP on set of gene trees with 9 taxa or more, MRP may fail even more probably, since 9-taxon species tree always has a caterpillar subtree, which may have unfortunate lengths of inner edges from the small region in Figure 3
We have established what these unfortunate lengths are. But how to nd these caterpillar subtrees? One may use the following
Theorem 3. If a tree has three consecutive inner edges not contaning the root betwen them but perhaps one of these edges ending on it then the tree has a 5-taxon caterpillar subtree, which contains these three inner edges.
Proof. At Figure 5 we can see three consecutive edges denoted 1,2 and 3 between nodes a,b, c and d, respectively and the third edge is closest to the root. Since these edges are inner, all the nodes must be bifurcation points and so each of b, c, d has one more edge running towards a taxon or a clade opposite to the root and a has two more such edges. Let d be the root then simply contracting each of the mentioned clades to one of its taxa we get a 5-taxon caterpillar subtree. If d is not the root, throw away one of the edges at d to make d the root of the 5-taxon caterpillar subtree.
Corollary 2.It is enough to know that in a species tree with amount of taxa 5 or more there are three consecutive inner edges not going through the root but perhaps ending on it with lengths T1; T2 and T3 from the small region of cube in Figure 3 to conclude that Parsimony is guaranteed to fail on this tree. 8
The fact that Parsimony may fail is not new. However, here we proved that no mater of what topology the true 9-taxon and greater species tree is the only condition to fail Parsimony is to have in this tree three consecutive inner edges not going through the root but perhaps ending on it with lengths T 1; T 2; T 3 (which are times in coalescence units between the branching points) of some proportions. Obviously, the probability to meet these lengths is growing in general with the size of species tree. So, if one wants to safely use MRP on a set of n-taxon gene trees, it is need to know somehow that the resulting n-taxon species tree cannot have any of \bad" topologies and edge lengths from \bad" regions. This paper makes it possible for n 5. Also, one may apply MRP on a set of 5-taxon gene trees and if the result is the caterpillar tree or topology 3 from Fig. 2, it is true.
One may consider 6-taxon species trees the way we did in this paper and check the existence of 6-taxon topology which forces Parsimony to fail when lengths of inner edges have some proportions. Then prove, perhaps following our ideas, that every tree with some number of taxa greater than 6 has this 6-taxon topology subgraph. Then do the same for 7 taxa and so on.
If one studies all \bad" parameters' regions of all \bad" topologies for all trees with the amount of taxa less or equal some n, it becomes theoretically possible to check either MRP can be applied for a set of gene trees of n taxa (if, of course, the researcher knows enough information about possible results). However, taking into account the factorial growth of the amount of binary trees with respect to the amount of taxa, the problem to nd \safe zone" for MRP becomes extremely hard. Unfortunately, we don't see any way around besides doing that scheme for each k < n. So, someone has to be very motivated to use MRP to go through with the research. Nowadays, there are good coalescence based methods, for example, [YufengWu], [RanYan] and [EmmsKelly]
It could be interesting to study stability questions of the coalescent model with uncertainty in data applying the thoughts from [Zubov].
Biorxiv