© 2004 Society of Systematic Biologists
Distances that Perfectly Mislead
Edited by Junhyong Kim: Associate Editor
1 Center for Bioinformatics, Tübingen University Tübingen Germany; E-mail: huson{at}informatik.uni-tuebingen.de
2 Biomathematics Research Centre, University of Canterbury Private Bag 4800, Christchurch, New Zealand; E-mail: m.steel{at}math.canterbury.ac.nz
 |
Abstract |
|---|
 Top Abstract Perfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
Given a collection of discrete characters (e.g., aligned DNA sites, gene adjacencies), a common measure of distance between taxa is the proportion of characters for which taxa have different character states. Tree reconstruction based on these (uncorrected) distances can be statistically inconsistent and can lead to trees different from those obtained using character-based methods such as maximum likelihood or maximum parsimony. However, in these cases the distance data often reveal their unreliability by some deviation from additivity, as indicated by conflicting support for more than one tree. We describe two results that show how uncorrected (and miscorrected) distance data can be simultaneously perfectly additive and misleading. First, multistate character data can be perfectly compatible and define one tree, and yet the uncorrected distances derived from these characters are perfectly treelike (and obey a molecular clock), only for a completely different tree. Second, under a Markov model of character evolution a similar phenomenon can occur; not only is there statistical inconsistency using uncorrected distances, but there is no evidence of this inconsistency because the distances look perfectly treelike (this does not occur in the classic two-parameter Felsenstein zone). We characterize precisely when uncorrected distances are additive on the true (and on a false) tree for four taxa. We also extend this result to a more general setting that applies to distances corrected according to an incorrect model.
Keywords: Additive metric; distance-based phylogeny reconstruction; inconsistency
Received August 27, 2003; Revised November 17, 2003; Accepted November 28, 2003
When distances between species have been estimated from character data and then either corrected or left uncorrected, they often fail to fit exactly on any tree. It is easy to measure how treelike (additive) any collection of distances is by, for example, looking at their splits graph (Bandelt and Dress, 1992; Huson, 1998) or other quartet-based approaches such as delta-plots (Holland et al., 2002). When the distances are perfectly additive (i.e., there is some tree T with positive edge weights so that each given distance between two tip species exactly matches the path distance in the tree), then the splits graph will display T exactly. Often however the splits graph will be a nontree network, and in the case of four species we may always represent any set of distances exactly by path lengths in a rectangle with one short side (of length S, equal to zero precisely when the distances fit a tree) and one long side (L
S) (Fig. 1).
|
The extent to which distances are treelike (as measured, for example, by 1–[S/L]) is often taken as an indication of their suitability and likely accuracy for tree reconstruction. Investigators are generally less happy inferring trees from distances when they display conflicting signals, as indicated, for example, by fat rectangles in the splits graph, than when the distances fit near perfectly on a tree.
Here, we provide two results that demonstrate that additivity is no guarantee of accuracy for uncorrected distances. Informally, these uncorrected distances simply count the proportion of characters for which the taxa have different states. More formally, given a sequence C = (f1, ..., fk) of characters on a set X of species, let
|
|
The distance measure dC has some appealing properties. For example, if the characters evolve under any of the usual stochastic models (e.g., allowing a general time reversible stationary process, with rates across sites) and a molecular clock applies, then dC is statistically consistent for tree topology reconstruction. In one recent simulation study, Holland et al. (2003) found the use of dC more accurate for tree reconstruction in this setting than the use of corrected distances. One does not need to know the fine details of the model (e.g., for aligned DNA sequences, these would include parameters relating to rate variation across sites or nucleotide transition frequencies; for gene order, relevant parameters would relate to the relative rates of different rearrangement processes); one can simply apply methods such as neighbor joining directly to the uncorrected values dC(i,j). The branch lengths in this case may not be consistently estimated (they will generally be underestimated, and consistent estimation requires knowing more of the fine details of the model).
We show here how the characters C can perfectly favor one tree (through the eyes of character-based methods such as compatibility, parsimony, and likelihood), yet the induced dissimilarities dC can appear to perfectly fit a totally different tree. We also describe precisely when dC is perfectly additive on an incorrect tree when the characters evolve under a certain Markov model. The proofs of our main results appear in the Appendix.
|
Perfect Characters with Perfectly Misleading Distances |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
For any sequence C of perfectly compatible binary characters, the induced distance dC is additive on the tree(s) that these characters support (see Semple and Steel, 2003, proposition 7.1.9). In the case of nonbinary characters, this statement no longer holds; the distance dC derived from perfectly compatible characters may no longer be additive on all or even any of the trees on which the characters in C are homoplasy free. It might be hoped that in these cases the induced distances would reveal their misleading nature by being not particularly additive (on any tree). However, the following theorem shows just how wrong this intuition can be. There exist data sets where the distances look perfectly additive (indeed clocklike) on one tree, yet they are homoplasy free only on a completely different tree. This condition holds for any number of taxa provided the there is a large enough number of character states. A binary phylogenetic tree is one that has no polytomies (i.e., it is fully resolved).
Theorem 2.1
Let T1 and T2 be any two binary phylogenetic trees on the same set X of species. Then there exists a sequence C of multistate characters for which
- C is homoplasy free for T1 and for no other phylogenetic tree on X (including T2).
- The distances dC derived from C are perfectly additive on T2 yet they are not additive on any other phylogenetic tree on X (including T1). Furthermore, we may insist that the distances dC fit a molecular clock (i.e., are ultrametric) on T2.
Figure 2 illustrates Theorem 2.1 in the simplest case where |X| = 4.
|
We may modify Theorem 2.1 to obtain a sequence C of multistate characters for which T1 has a strictly larger likelihood score under a symmetric Poisson model than does any other tree, yet dC is additive only on T2. This follows by adding to C a sufficiently large number of constant sites and then invoking theorem 7 of Tuffley and Steel (1997). Our proof of Theorem 2.1 (Appendix) uses a construction for which the number of character states is 1 less than the number of taxa; however, we suspect this is merely an artifact of our proof, and a more intricate argument might be possible using fewer states.
|
Evolving Perfectly Misleading Uncorrected Distances |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
The data sets just described were deliberately chosen to illustrate an extreme phenomenon. Here, we investigate when precisely characters that evolve under a Markov process can also provide perfectly deceptive induced distances. We describe precise conditions for a four-taxon tree.
Suppose that n sites or characters are generated independently on the tree T1 (Fig. 3a). Under the usual models of DNA evolution, uncorrected distances are generally not exactly additive; however, they can be additive both on the "true" tree that generated them and, in another slice of parameter space, on a false tree. In the later case, their appearance of being exactly additive may be deceptive, because it shows no evidence of causing a problem, nevertheless the wrong tree will be inferred from them.
|
Uncorrected distances will usually fail to be exactly treelike, but when they are treelike there are two possibilities:
- The distances are exactly treelike on the true topology that generated the data.
- The distances are exactly treelike on an incorrect topology.
Situation 1 occurs when there is a molecular clock (Steel and Penny, 2000: theorem 4); however, there is a strictly larger region of parameter space where this can occur.
Regarding situation 2, distance methods can be inconsistent (Felsenstein, 1978). However, situation 2 requires much more than mere inconsistency; not only must the distances favor a false tree over the true tree, but they must show no support for any tree other than the false tree. The subspace of parameter space where this occurs is the region of perfect inconsistency. This region does not intersect with the original two-parameter zone described by Felsenstein (1978); in that zone there is always conflicting support but more support for a false tree. Near the region of perfect inconsistency, the close fit of the uncorrected distances could mislead the unwary investigator into concluding that the reconstructed tree was accurate (or that the distances did not need correcting). We illustrate this region with an example and end by describing a more general result.
First, we will analyze exactly when situations 1 and 2 can arise when the underlying model is the equal input model on r states. This is a time-reversible model whose transition rate matrix has as its ith row a common nondiagonal entry 
i (which represents the expected frequency of state i in the data). When r = 4, this is the Tajima–Nei (1984) model, which has a three-parameter rate matrix, allowing for an arbitrary base composition. As a special case, when all the base compositions are equal this model becomes the symmetric Poisson model (Jukes–Cantor [1969] when r = 4, and the Mk model of Lewis [2001] when r = k 4). For the tree T1 displayed in Figure 3a the values 
i represent the expected number of substitutions on edge i.
Let us generate a sequence C of k characters independently under this model. As k becomes large, dC(i,j) converges to its expected value, i.e., the probability that i and j are in different states under the model, which we denote p(i,j). Let p = [p(i,j)] be the matrix of values of p.
We now describe conditions on the i values for which the values of p will be perfectly treelike in situations 1 (= treelike on T1) and 2 (= treelike on a different tree, say the tree T2 with topology 13|24, shown in Fig. 3b). To describe these results it is useful to let p
= 1 – 
i = 1r i2, and for i = 1,..., 5, let xi = exp (–i/p). Note that p is the limiting probability that two species are in different states as their evolutionary distance tends to infinity.
Theorem 3.1
Suppose that p is the matrix of uncorrected distances generated by tree T1 with edge parameters xi = exp (–i/p) under the equal-input model.
- The matrix p is additive on T1 (and only on T1) if and only if both of the following two conditions apply:
and
- The matrix p is additive on T2 (and only on T2) if and only if the following two conditions apply:
and
We can express the conditions described in Theorem 3.1 purely in terms of the p(i,j) values because the xk values are determined by the p(i,j) values. For example,
|
|
|
|
In part 1, the constraint on parameter space described is strictly weaker than the constraint imposed by a molecular clock. For example, suppose we set x = (x1,x2,x3,x4,x5) = (0.5, 0.5, 0.2, 0.1, 0.1). These values for x satisfy the condition in part 1 of Theorem 3.1 and so are additive on T1. However, if we consider the values of the function p on the pairs of elements chosen from {1,3,4}, we obtain three distinct values (i.e., p(1,3), p(1,4) and p(3,4) are all different, as can be verified by applying Equation 5 of the Appendix), and so p is not an ultrametric. Consequently, because p is a monotone increasing function of evolutionary distance, the values cannot satisfy a molecular clock.
The phenomena described by part 2 of Theorem 3.1 cannot arise under the simple two-parameter Felsenstein zone setting for which x1 = x3 and x2 = x4 = x5 (i.e., two long equal-length edges and three short equal-length edges).
The region for which we have exact additivity (either on the true tree T1 or on an alternative tree T2) requires an equality to hold and so is unlikely to hold exactly in practice. Nevertheless, the result suggests there will be situations where one will be very close (perhaps indistinguishably close) to additivity.
Example
Suppose x = (x1,x2,x3,x4,x5) = (0.95, 0.5, 0.75, 0.7, 0.9615385). This value of x satisfies the conditions described in part 2 of Theorem 3.1. Given a tree based on these values, we used the program SeqGen (Rambaut and Grassly, 1997) to generate 100 simulated data sets for each of the sequence lengths 100, 500, 1,000, 5,000, 10,000, and 100,000. Table 1 summarizes the results, which show an increasing tree-likeness score with sequence length, both for the uncorrected distances (which converge to a false tree) and the corrected distances (which converge to the true tree).
|
An extension
The region of perfect inconsistency is not particular to the equal input model; it may also arise when distances are corrected according to an incorrect model. For most models of site substitution where uncorrected or miscorrected distances can be inconsistent, there is a corresponding and nonempty region of perfect inconsistency. By a standard model, we mean any model of nucleotide substitution for which p(i,j) can be written as some function f of the total evolutionary distance (sum of the edge lengths) separating sequences i and j. Virtually all models used in molecular systematics are standard, including the general time reversible (GTR) model (with or without rate variation) and covarion-type models. To emphasize the dependence of p on
= (1, ..., 5), we will write p. Suppose that g is some continuous function that is applied to dC. We think of g either as the identity function (i.e., uncorrected distances) or some function that attempts to correct distances but is subject to an incorrect model (perhaps due to undercorrection). For any distance function d on X = {1,2,3,4} and ordering i,j,k,l of X, let sij|kl(d) = g[d(i,j)]+g[d(k,l)], and let S(d) = [s12|34(d), s13|24(d), s14|23(d)]. For a sequence C of characters on the set X = {1,2,3,4}, most distance methods, such as neighbor joining, applied to the distances g[dC(i,j)] will select tree ij|kl precisely if sij|kl(dC) is the smallest value of S(dC) (Gascuel, 1997).
To investigate inconsistency, we replace dC in the above expressions by its expected value, p. Let min S(p) and max S(p) denote the minimal and maximal elements of S(p). Then is a strong inconsistency parameter value under g-correction if the following two conditions hold:
- s12|34(p)
{min S(p), max S(p)} (SI1).
- If 'i = i for i = (3,4,5) and '1 and '2 both lie between 1 and 2, then s12|34(p')
min S(p') (SI2).
One motivation for this definition is that strong inconsistency values arise in classic Felsenstein zone settings with uncorrected distances. For example, under the equal input model, if we set x1 = x3 = 
(long edges) and x2 = x4 = x5 = 1– (short edges), then for a sufficiently small positive value of it can be verified that conditions SI1 and SI2 both hold.
For a range of models, and at least some functions g (e.g., those that are close to the identity function, which correspond to undercorrection), we may therefore expect there to be a corresponding strong inconsistency parameter value . In such cases, the following result guarentees there is a corresponding nonempty region of perfect inconsistency.
Theorem 3.2
For sequences generated by the standard model on T1, suppose that there is a strong inconsistency parameter value under g-correction. Then, there exists a nonempty region of perfect inconsistency for this model, i.e., parameters for which the expected sequence dissimilarities, after they have been corrected according to g, are perfectly additive on a tree that is different from T1.
|
Concluding Comments |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
For topology estimation under clocklike models, the use of dC may be preferable to corrected distances that have higher variance or when the fine details of the model are unclear. The catch is the invocation of a molecular clock. Where evolution is not clocklike, the raw distance measure dC can be seriously misleading. These distances can favor incorrect topologies. We have demonstrated that this can occur without any hint that there is a problem in terms of conflicting signal. Techniques such as SplitsTree (Huson, 1998) often provide a useful visual representation of conflicting phylogenetic signal present in distance data. Generally, the absence of conflict should provide some confidence in the output, because the conditions for perfect inconsistency are quite special. Nevertheless, that there even exists such a region should be taken as a caution. The message is simple: a (near) perfect fit of raw distance data to some tree does not necessarily confer confidence in the accuracy of the tree.
|
Appendix |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
Proof of Results
Proof of Theorem 2.1
Throughout this proof, let n = |X|,
. Let D1(i,j) denote the number of interior edges in T1 that separate i and j. On T2, assign edge weight 1 to all interior edges, and assign to each exterior (pendant) edge a nonnegative integer edge weight in such a way that the induced metric on X (denote by D2) is an ultrametric. Thus, D2 is additive on T2 and no other tree, and we can represent D2 on T2 with a edgeweighting that satisfies a clock (i.e., the distance from some vertex or the midpoint of some edge to all the leaves is the same).
Let S = i,j[D2(i,j)–D1(i,j)], and select a positive integer r sufficiently large that for all i,j 
X we have
|
| (1) |
Let C1 be the set of n–3 binary characters (one for each interior edge of T1) that correspond to the splits of T1. Thus, T1 is the only phylogenetic tree on X on which C1 is homoplasy free. For a pair of species i,j X, a character is of type ij if i and j are the only two species in X that are assigned the same character state.
Let C2 consist of the following sequence of characters. For each distinct pair i,j X, place nij characters of type ij in C2 where
|
| (2) |
X, if we let DC be the (nonnormalized) Hamming distance defined by DC(i,j) = |[s: fs(i) fs(j)]|, then
|
| (3) |
i,j nij. Let D2'(i,j) = B· D2(i,j) + rB for each i,j X. Then, D2' is an ultrametric that is additive on T2 and no other tree (because D2 has this property). Furthermore, substituting Equation 2 into Equation 3 and reducing the resulting equation gives DC(i,j) = D2'(i,j) for all i,j X. Thus, DC(i,j) is precisely the distance in T2 with the edge weighting as specified. Consequently, DC and thereby dC are perfectly additive on T2, as claimed. By the assumption that T2 is binary and because all the edge weight assignments described are positive, it follows that dC is additive only on T2. This completes the proof.
Proof of Theorem 3.1
This proof relies on elementary algebra, with repeated application of the formal identity:
|
| (4) |
|
| (5) |
Proof of part 1
By the four-point condition, p is additive (only) on T1 precisely if
|
|
|
| (6) |
|
| (7) |
Proof of part 2
By the four-point condition, p is additive (only) on T2 precisely if
|
|
|
| (8) |
Proof of Theorem 3.2
Let be a strong inconsistency value under g-correction. Without loss of generality, by SI1 we have
|
|
* be the parameter value obtained by interchanging 1 and 2 in : |
|
|
|
For t [0, 1], let t = t + (1–t)* and let h(t) = s14|23(pt)–s12|34(pt). Thus, h(0) < 0, h(1) > 0, and so. Because h is continuous, there exists a value t0 (0,1) for which h(t0) = 0. Let 0 = t0. Note that 0i = i for i = (3,4,5), and so by (SI2) we have
|
|
0 is a point of perfect inconsistency. This completes the proof. |
Acknowledgments |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
We thank the New Zealand Institute for Mathematics and Its Applications (Phylogenetic Genomics Programme). We also thank Junhyong Kim, Kevin Atteson, and an anonymous reviewer for several helpful comments on an earlier version of this manuscript.
|
References |
|---|
|
TopAbstractPerfect Characters with...Evolving Perfectly Misleading...Concluding CommentsAppendixAcknowledgmentsReferences |
|---|
-
Bandelt H.-J., Dress A. W. M. A canonical decomposition theory for metrics on a finite set. Adv. Math. (1992) 92:47–105.[CrossRef]
Felsenstein J. Cases in which parsimony or compatibility methods will be positively misleading. Syst. Zool. (1978) 27:401–410.
Gascuel O. Concerning the NJ algorithm and its unweighted version, UNJ. In: DIMACS series in discrete mathematics and theoretical computer science, Volume 37. Mathematical hierarchies and biology—Mirkin B., McMorris F. R., Roberts F. S., Rzhetsky A., eds. (1997) Providence, Rhode Island: American Mathematical Society. 149–170. Pages.
Holland B., Huber K., Dress A. W. M., Moulton V. Delta-plots: A tool for the analysis of phylogenetic distance data. Mol. Biol. Evol. (2002) 19:2051–2059.
Holland B., Penny D., Hendy M. D. Outgroup misplacement and phylogenetic inaccuracy under a molecular clock—A simulation study. Syst. Biol. (2003) 52:229–238.
Huson D. H. SplitsTree: A program for analyzing and visualizing evolutionary data. Bioinformatics (1998) 14(10):68–73.
Jokes T. H., Cautor C. R. Evolution of protein molecules. In: Mammalian protein evolution—Munro H. N., ed. (1969) New York: Academic Press. 21–132. Pages.
Lewis P. O. A likelihood approach to estimating phylogeny from discrete morphological character data. Syst. Biol. (2001) 50:913–925.
Rambaut A., Grassly N. C. An application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Comput. Appl. Biosci. (1997) 13:235–238.
Semple C., Steel M. Phylogenetics. (2003) New York: Oxford Univ. Press.
Steel M., Penny D. Parsimony, likelihood and the role of models in molecular phylogenetics. Mol. Biol. Evol. (2000) 17:839–850.
Tajima F., Nei M. Estimation of evolutionary distance between nucleotide sequences. Mol. Biol. Evol. (1984) 1:269–285.[Abstract]
Tuffley C., Steel M. Links between maximum likelihood and maximum parsimony under a simple model of site substitution. Bull. Math. Biol. (1997) 59:581–607.[Web of Science][Medline]
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  H.-J. Bandelt and M. Fischer Perfectly Misleading Distances from Ternary Characters Syst Biol, August 1, 2008; 57(4): 540 - 543. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 W. White, S. Hills, R Gaddam, B. Holland, and D. Penny Treeness Triangles: Visualizing the Loss of Phylogenetic Signal Mol. Biol. Evol., September 1, 2007; 24(9): 2029 - 2039. [Abstract] [Full Text] [PDF]
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||