Parsimony via concensus
Title:
Parsimony via consensus
Trevor C. Bruen and David Bryant
Running Head: Parsimony via consensus
Key Words: maximum parsimony, compatibility, supertree, matrix representation with
parsimony, homoplasy
Corresponding Author: David Bryant
Abstract
The parsimony score of a character on a tree equals the number of state changes
required to fit that character onto the tree. We show that for unordered, reversible
characters this score equals the number of tree rearrangements required to fit the tree
onto the character. We discuss implications of this connection for the debate over
the use of consensus trees or total evidence, and show how it provides a link between
incongruence of characters and recombination.
Introduction
The (Fitch) parsimony length of a character on a tree equals the minimum number of state
changes (substitutions) required to fit the character onto a tree (Fitch, 1971). We turn this
definition on its head and show how the parsimony length of a character equals the minimum
number of changes in the tree required to fit the tree onto the character. This may be a
back-to-front way to look at parsimony, but it is also a useful one. We detail two applications
of the result.
The first application is that this reformulation of parsimony provides a closer link between
parsimony based analysis and supertree methods. We demonstrate that the maximum parsi-
mony tree can be viewed as a type of median consensus tree, where the median is computed
with respect to the SPR distance (see below). As well, the result shows how to conduct a
parsimony based analysis not just on characters but on trees, without having to recode the
trees as binary character matrices. This opens the way to a hybrid between the consensus
approach and the total evidence approach, where the data is a mix characters, trees, and
subtrees.
The second application of our observation on parsimony is to the analysis of pairs of
characters. We show that the score of the maximum parsimony tree for two characters is a
simple function of the smallest number of recombinations required to explain the incongru-
ence between the characters without homoplasy. This result provides the basis of a highly
efficient test for recombination (Bruen et al., 2006).
Here and throughout the paper we assume that all phylogenetic trees are fully resolved
(bifurcating) and that by ‘parsimony’ we refer to Fitch parsimony, where the character states
are unordered and reversible. Some of the results presented here can be extended to other
forms of parsimony, and possibly to incompletely resolved trees (Bruen, 2006), lie beyond
the scope of this paper.
Note that in this paper we are dealing with unrooted SPR rearrangements, which are those
used in tree searches. There is a related, but distinct, concept of rooted SPR rearrangements,
where the rearrangements are restricted to obey a type of temporal constraint Song (2003). It
is this latter class of rooted SPR rearrangments that are used to model lateral gene transfers
and recombination. It would be a worthwhile, but challenging, goal to investigate whether
any of the results on unrooted SPR rearrangements in this paper can be extended to rooted
SPR rearrangements.
Linking Parsimony with SPR
A subtree-prune and regraft (SPR) rearrangement is an operation on phylogenetic trees
whereby a subtree is removed from one part of the tree and regrafted to another part of
the tree, see Figure 1, (Felsenstein, 2004; Swofford et al., 1996). These SPR rearrangements
are widely used by tree searching software packages like PAUP (Swofford, 1998) and Garli
(Zwickl, 2006). The SPR distance between two trees can be defined as the minimal num-
ber of SPR rearrangements required to transform one tree into the other (Hein, 1990; Allen
and Steel, 2001; Goloboff, 2007). For example, the two trees T1 and T3 in Figure 1 can be
transformed into each other using a minimum of two SPR rearrangements, via the tree T2,
so their SPR distance is two.
Figure 1: Two trees, T1 and T3, separated by two SPR rearrangements via the intermediate
tree T2. A binary character of parsimony length 3 is indicated on tree T1 by the node
colours. The character is compatible with a tree (T3) within SPR distance two, illustrating
Theorem 1..
The parsimony length of a character on a tree is the minimum number of steps required
to fit that character on the tree, as computed by the algorithm of (Fitch, 1971). We will
always assume unordered reversible characters The length of a character Xi on a tree T is
denoted `(Xi, T ). A character with ri states therefore has parsimony length at least (ri−1),
as every state not at the root has to arise at least once. A character is compatible with a
tree if it requires at most (ri − 1) changes on that tree (Felsenstein, 2004).
So far, one thinks of fitting a character onto a tree; we could just as well fit the tree onto
the character. If the character and the tree are compatible then we have a perfect fit. When
there is not a perfect fit we can measure how many SPR rearrangements are required to give
a tree that does make a perfect fit. It turns out that this measure gives an equivalent score
to parsimony length. More formally:
Theorem 1. Let Xi be a character with ri states and let T be a fully resolved phylogenetic
tree. It takes exactly `(Xi, T ) − (ri − 1) SPR rearrangements to transform T into a tree
compatible with Xi. The result still holds if Xi has some missing states.
As an example, consider the character X1 mapping taxa A,C,D,F to one and B,E,G to
zero. The length of this character on tree T1 of Figure 1 is three, and the number of SPR
rearrangements needed to transform T1 onto some tree T3 compatible with with X1 is two.
Note that there could be other trees compatible with X1 are are further than two SPR
rearrangements away: the result only gives the number of rearrangements required to obtain
the closest tree.
Once stated, the theorem is not too difficult to prove. First show that performing an SPR
rearrangement decreases the length by at most one step. Hence it takes at least `(Xi, T )−
(ri − 1) SPR rearrangements to transform T into a tree compatible with the character Xi.
Then show that this is the minimum required. A formal proof is presented in the Appendix.
A restricted (binary character) version of this theorem was proved in (Bryant, 2003).
The theorem captures an issue that is central to the interpretation of incongruence: is
an observed incongruence to be explained by positing homoplasy or by modifying the tree.
Define the SPR distance from a tree T to a character Xi to be the SPR distance from T
to the closest tree T ′ that is compatible with Xi. Theorem 1 then tells us that the SPR
distance from T is equal to the difference between the length `(Xi, T ) of Xi on T and the
minimum possible length of Xi on any tree.
Consensus trees, supertrees and parsimony
In their insightful overview of supertree methods Thorley and Wilkinson (2003) characterise
a family of supertree methods that all minimise a sum of the form
d(T, ti) = d(T, t1) + d(T, t2) + ...+ d(T, tn). (1)
Here t1, t2, . . . , tn are the input trees and d(T, ti) is a measure of the distance between the
input tree ti with the supertree T . There are many choice for the distance measure d,
and it need not be the case that the distance measure satisfies the symmetry condition
d(T, ti) = d(ti, T ). Gordon (1986) was the first to propose this description of supertrees.
Many supertree methods can be described in these terms, including Matrix representation
with parsimony (MRP) (Baum, 1992; Ragan, 1992); Minimum Flip supertrees Chen et al.
(2006); the Median Supertree (Bryant, 1997), Majority Rule Supertree (Cotton and Wilkin-
son, 2007) and the Average Consensus Supertree (Lapointe and Cucumel, 1997).
Let ds(T,Xi) denote the SPR distance from T to the closest fully resolved tree Ti that is
compatible with Xi. By Theorem 1, a maximum parsimony tree for X1, . . . , Xm is one that
minimises the expression
ds(T,Xi) = ds(T,X1) + ds(T,X2) + ...+ ds(T,Xm). (2)
In this way, maximum parsimony is a form of median consensus. The significance of this
observation doesn’t come from the fact that we can write the the parsimony score of T in the
form (2); it is from the close connection with SPR distances, and from the way we will now
use this connection to combine different kinds of data in the same theoretical framework.
An SPR median tree for fully resolved trees t1, . . . , tn on the same leaf set is a tree T that
minimises
ds(T, ti) = ds(T, t1) + ds(T, t2) + ...+ ds(T, tn),
where here d(T, ti) denotes the SPR distance from T to ti (Hill, 2007). We extend this
directly to a supertree method by mimicking the situation for characters. Suppose that ti is
a phylogenetic tree, not necessarily fully resolved, on a subset of the set of leaves. We say that
a fully resolved tree T on the full set of leaves is compatible with ti (equivalently, T displays
ti) if we can obtain ti from T by pruning off leaves and contracting edges. In this general
situation, we let ds(T, ti) denote the SPR distance from T to the closest fully resolved tree
Ti that is compatible with ti. This is equivalent to the more traditional definition whereby
we first prune leaves off T then compute the distance from this pruned tree to ti.
Now suppose that we have both characters and trees in the input. Both types of phylo-
genetic data can be into an SPR median tree T , chosen to minimise the sum
ds(T, ti) +
ds(T,Xi).
We have, then, a way to bring together both the supertree/consensus methodology and the
total evidence methodology. In the case that the data comprises only trees, the tree is a
median supertree; in the case that the data comprises only character data, the tree is the
maximum parsimony tree.
It is important to note the difference between this approach and the MRP method (Baum,
1992; Ragan, 1992), which could be used to combine trees and characters. In MRP, the trees
are broken down into multiple independent characters. This is a problem, since the characters
encoding a tree are nowhere near independent. In contrast, the SPR median tree approach
treats a tree as a single indivisible unit of information.
There is one critical issue that has been side-stepped: computation time. At present,
computational limitations make the construction of SPR median trees infeasible for all but
the smallest data sets: just computing the SPR distance between two trees is an NP-hard
problem (Hickey et al., 2006). In contrast, Total evidence and MRP approaches are possible
for at least 100 taxa. However there are now good heuristics for unrooted SPR distance
Goloboff (2007) and exact special case algorithms Hickey et al. (2006) that could be applied
to the problem. Below we describe a lower bound method for the SPR distance that should
also aid construction of these SPR median trees.
Parsimony on pairs of characters
Another valuable application of Theorem 1 follows when we consider parsimony analysis of
just two unordered and reversible characters. The concept of pairwise character compatibil-
ity was introduced by Le Quesne (1969) (see also Felsenstein (2004)). Two binary characters
with states 0 and 1 are incompatible if and only if all four combinations of 00, 01, 10, and 11
are present as combination of states for the two characters (Le Quesne, 1969). In a standard
setting, character incompatibility is interpreted as implying that at least one of the charac-
ters has undergone convergent or recurrent mutation (homoplasy). In other words, for every
possible phylogeny describing the history of the two characters, at least one homoplasy is
posited for one of the characters. Another interpretation of incompatibility of two characters
is that characters evolved without homoplasy on two different phylogenies, where the phylo-
genies differ by one or more SPR rearrangement (Sneath et al., 1975; Hudson and Kaplan,
1985).
Define the total incongruence score i(X1, X2) for two multi-state unordered characters
X1 and X2 (with r1 and r2 states respectively) as
i(X1, X2) = min
`(X1, T ) + `(X2, T )
− (r1 − 1)− (r2 − 1). (3)
This is the maximum parsimony score of the two characters X1, X2 minus the minimum
number of changes required for each character. Equation (3) generalises the incompatibility
notion for two binary characters. It is also equivalent to the incongruence length difference
statistic applied to only two characters (Farris et al., 1995). Importantly, the total incongru-
ence score can be computed rapidly (Bruen and Bryant, 2006). The following consequence
of Theorem 1 strengthens the connection between incongruence and SPR rearrangements.
Theorem 2. The total incongruence score i(X1, X2) for two characters equals the minimum
SPR distance between a tree T1 and T2 such that X1 is compatible with T1 and X2 is compatible
with T2.
Although the notion of total incongruence for two characters has been considered before
in the context of character selection and weighting (Penny and Hendy, 1986), it has not been
considered in the context of genealogical similarity. Essentially, Theorem 2 shows that the
total incongruence score equals the minimum possible number of SPR rearrangements that
could have occurred between the phylogenetic histories for both characters, assuming that
the characters have different histories with which they are each perfectly compatible.
Indeed, Theorem 2 suggests a natural way to interpret genealogical similarity between
two characters, which we have used to develop a powerful test for recombination (Bruen
et al., 2006). Choosing two characters from two different genes (which have possibly different
histories) gives a simple approach to identify the distinctiveness of the histories of the genes.
We can also apply Theorem 2 to obtain a lower bound on an SPR distance between two
trees. Suppose that we have two trees T1 and T2 and we wish to obtain a lower bound on the
SPR distance d(T1, T2) between the two trees. If we choose any character X1 convex on T1
and any character X2 convex on T2 then, by Theorem 2, we have that i(X1, X2) ≤ d(T1, T2).
By carefully choosing X1 and X2 we can obtain tighter bounds. One natural starting point
for X1 and X2 is the four or five character encodings described by (Semple and Steel, 2002;
Huber et al., 2005).
Discussion and extensions
We have presented a reformulation of parsimony that is, in some way, dual to the standard
definitions. Instead of measuring how well a character fits onto a tree we look at how well the
tree fits onto the character. A consequence of this new perspective is that we can combine
trees and character data using one general SPR framework, and we also obtain new results
connecting incongruence measures and recombination. Nevertheless, it is not immediately
clear how the new reformulation can be interpreted in itself.
Trees compatible
with X1
Trees compatible
with X2
Trees compatible
with X3
Trees compatible
with X4
Trees compatible
with X(m-1)Trees compatible
with Xm
d(T,t1)
Figure 2: Cartoon representation of parsimony in terms of tree rearrangements. Each
characterXi gives a ‘cloud’ of trees containing those trees compatible withXi. The maximum
parsimony tree is then the tree closest to these clouds under the SPR distance.
One aid in this direction is to consider the information a single character, or tree, rep-
resents. Given a single character, we can imagine a cloud of trees comprising exactly those
trees compatible with the character (Figure 2). If we are told that this character evolved
without homoplasy, then we know that the true evolutionary tree must be contained some-
where within the cloud. However as there is only one character there is a lot of uncertainty
regarding the tree, so there are a lot of trees in the clouds. Now suppose we have multiple
characters, each with its own cloud. There may not be a single tree contained in the inter-
section of all of these clouds. Instead, we search for a tree that is close as possible to all of
the clouds. The distance from T to the cloud associated to character Xi is exactly ds(T,Xi),
so by Theorem 1 a tree closest to all of the clouds is a maximum parsimony tree.
Each cloud represents the uncertainty around each piece of data (tree or character).
We note that several of the results in this article can be extended, for details. Firstly,
both Theorems 1 and 2 are both valid if we replace the SPR distance with the tree bisection
and reconnection (TBR) distance. In a TBR rearrangement, a subtree is removed from
the tree and then reattached elsewhere in a tree, the difference with SPR being that we can
reattach using any of the nodes in the subtree (Allen and Steel, 2001; Felsenstein, 2004). The
TBR distance between two trees is the minimum number of TBR rearrangements required
to transform one tree into the other.
That Theorems 1 and 2 hold for the TBR distance might seem surprising, since the TBR
distance between two trees is always less than, or equal to, the SPR distance between the
trees. However the extension follows by a tiny change to the proof of Theorem 1, noting
that a TBR move can still only reduce the parsimony score of a character by at most one.
We have also explored extensions of the result to other distances between trees, notably
the Robinson-Foulds or partition distance and the Nearest Neighbor Interchange distance,
though the connections are not so clear. See Bruen (2006) for details.
Acknowledgements
We would like to thank Mike Steel, Sebastien Böcker, Olaf Bininda Emonds, Pablo Golloboff,
Mark Wilkinson and an anonymous referee for their valuable suggestions. This research was
partially supported by the New Zealand Marsden Fund.
References
Allen, B. and M. Steel. 2001. Subtree transfer operations and their induced metrics on
evolutionary trees. Annals of Combinatorics 5:1–13.
Baum, B. 1992. Combining trees as a way of combining datasets for phylogenetic inference,
and the desirability of combining gene trees. Taxon 41:3–10.
Bruen, T. 2006. Discrete and statistical approaches to genetics. Ph.D. thesis McGill Univer-
sity School of Computer Science.
Bruen, T. and D. Bryant. 2006. A subdivision approach to maximum parsimony. Annals of
Combinatorics In Press.
Bruen, T., H. Philippe, and D. Bryant. 2006. A simple and robust statistical test to detect
the presence of recombination. Genetics 172:1–17.
Bryant, D. 1997. Building trees, hunting for trees and comparing trees. Ph.D. thesis Dept.
Mathematics, University of Canterbury.
Bryant, D. 2003. A classification of consensus methods for phylogenetics. Pages 163–184 in
Bioconsensus vol. 61 of DIMACS. American Math Society, Providence, RI.
Bryant, D. 2004. The splits in the neighborhood of a tree. Annals of Combinatorics 8:1–11.
Chen, D., O. Eulenstein, D. Fernandez-Baca, and M. Sanderson. 2006. Minimum-flip su-
pertrees: Complexity and algorithms. IEEE/ACM Trans. Comput. Biol. Bioinformatics
3:165–173.
Cotton, J. and M. Wilkinson. 2007. Majority-rule supertrees. Systematic Biology 56:445–
Farris, J. S., M. Källersjö, A. G. Kluge, and C. Bult. 1995. Constructing a significance test
for incongruence. Systematic Biology 44:570–572.
Felsenstein, J. 2004. Inferring Phylogenies. Sinauer Associates.
Fitch, W. M. 1971. Towards defining the course of evolution: Minimum change for a specific
tree topology. Systematic Zoology 20:406–416.
Goloboff, P. 2007. Calculating SPR distances between trees. Cladistics Online early access.
Gordon, A. D. 1986. Consensus supertrees: the synthesis of rooted trees containing overlap-
ping sets of labeled leaves. Journal of Classification 3:335–348.
Hein, J. 1990. Reconstructing evolution of sequences subject to recombination using parsi-
mony. Mathematical Biosciences 98:185–200.
Hickey, G., F. Dehne, A. Rau-Chaplin, and C. Blouin. 2006. The computational complexity
of the unrooted subtree prune and regraft distance. Tech. Rep. CS-2006-06 Faculty of
Computer Science, Dalhousie University.
Hill, T. 2007. Development of New Methods for Inferring and Evaluating Phylogenetic Trees.
Ph.D. thesis Uppsala Universitet.
Huber, K. T., V. Moulton, and M. A. Steel. 2005. Four characters suffice to convexly define
a phylogenetic tree. SIAM Journal on Discrete Mathematics 18:835–843.
Hudson, R. R. and N. L. Kaplan. 1985. Statistical properties of the number of recombination
events in the history of a sample of dna sequences. Genetics 111:147–64.
Lapointe, F.-J. and G. Cucumel. 1997. The average consensus procedure: combination of
weighted taxa containing identical or overlapping sets of taxa. Systematic Biology 46:306–
Le Quesne, W. J. 1969. A method of selection of characters in numerical taxonomy. System-
atic Zoology 18:201–205.
Penny, D. and M. Hendy. 1986. Estimating the reliability of evolutionary trees. Molecular
Biology and Evolution 3:403–17.
Ragan, M. A. 1992. Phylogenetic inference based on matrix representations of trees. Molec-
ular Phylogenetics and Evolution 1:53–58.
Semple, C. and M. Steel. 2002. Tree reconstruction from multi-state characters. Advances in
Applied Mathematics 28:169–84.
Semple, C. and M. Steel. 2003. Phylogenetics. Oxford University Press.
Sneath, P., M. Sackin, and R. Ambler. 1975. Detecting evolutionary incompatibilities from
protein sequences. Systematic Zoology 24:311–332.
Song, Y. S. 2003. On the combinatorics of rooted binary phylogenetic trees. Ann. Comb.
7:365–379.
Swofford, D., G. Olsen, P. Waddell, and D. Hillis. 1996. Molecular sytematics chap. Phylo-
genetic Inference, Pages 407–514. Sinauer Associates, Inc.
Swofford, D. L. 1998. PAUP*. Phylogenetic Analysis using Parsimony (*and other methods).
Sinauer Associates, Sunderland, Massachusetts.
Thorley, J. L. and M. Wilkinson. 2003. A view of supertree methods. Pages 185–194 in
Bioconsensus (F. Roberts, ed.) vol. 61 of DIMACS series in discrete mathematics and
theoretical computer science The American Mathematical Society, New York.
Zwickl, D. 2006. Genetic algorithm approaches for the phylogenetic analysis of large biological
sequence datasets under the maximum likelihood criterion. Ph.D. thesis University of
Texas at Austin.
Appendix
Refer to (Semple and Steel, 2003) for a detailed description of the notation.
The first observation is that an TBR rearrangement of a tree increases the length of a
character by at most one. As SPR rearrangements are a special case of TBR rearrangements,
the same result holds for SPR.
Lemma 1. Let T be a fully resolved phylogenetic tree and Xi an unordered reversible charac-
ter. Let T ′ be a phylogenetic tree that differs from T by a single TBR rearrangement. Then
`(χ, T ′) ≤ `(χ, T ) + 1.
Proof. The proof of Lemma 5.1 in (Bryant, 2004) for binary characters applies directly to
the multistate case.
Let dSPR(T, T
′) denote the unrooted SPR distance between two phylogenetic trees T and
Theorem 1 LetXi be a character with ri states and let T be a fully resolved phylogenetic
tree. It takes exactly `(Xi, T ) − (ri − 1) SPR rearrangements to transform T into a tree
compatible with Xi. The result still holds if Xi has some missing states.
Proof. Let T ′ be a fully resolved phylogenetic tree compatible with Xi for which dSPR(T, T
is minimized and let m = dSPR(T, T
′). Then there exists a sequence of trees T ′ = T0, ..., Tm =
T such that every adjacent pair of trees in the sequence differ by exactly one SPR rear-
rangement. By Lemma 1 the existence of this sequence implies that `(T,Xi) − `(T ′, Xi) ≤
dSPR(T, T
′) and since Xi is compatible with Xi we have `(T
′, Xi) = ri − 1, giving
`(T,Xi)− (ri − 1) ≤ dSPR(T, T ′).
For the other direction, we show that we can construct a sequence of `(T,Xi) − (ri −
1) SPR rearrangements that transform T into a tree T ′ compatible with Xi. Firstly, if
`(T,Xi) − (ri − 1) = 0, then T is compatible with Xi so the proof is finished. Otherwise,
let X̂i be an assignment of states to internal nodes that minimises the number of state
changes (that is, a minimum extension of Xi). Then since Xi is not convex on T there
exist three vertices u, v and w, where {u, v} ∈ E(T ), v lies on the path from u to w and
X̂i(u) = X̂i(w) 6= X̂i(v). Perform an SPR rearrangement by removing edge {u, v}, supressing
the v vertex and creating a new edge {u, t} where t is a new vertex on an edge adjacent
to w. Furthermore, set X̂i(t) = X̂i(w). Then the number of edges on which a change has
occurred has decreased by 1 thereby decreasing the parsimony length by 1. This procedure
can be repeated until the parsimony length equals ri − 1, constructing the desired sequence
of trees and completing the proof.
Let T be a maximum parsimony phylogenetic tree for X1 and X2 and let
Theorem 2 The total incongruence score i(X1, X2) for two characters equals the mini-
mum SPR distance between a tree T1 and T2 such that X1 is compatible with T1 and X2 is
compatible with T2.
Proof. Let T1 and T2 be any two trees compatible with X1 and X2 respectively. Then
`(X1, T1) = r1−1 and by Theorem 1, `(X2, T1)− (r2−1) ≤ dSPR(T1, T2). We have then that
i(X1, X2) ≤ `(X1, T1) + `(X2, T1)− (r1 − 1)− (r2 − 1)
≤ dSPR(T1, T2)
and so i(X1, X2) is a lower bound for dSPR(T1, T2).
We show that this bound can be achieved. Let T be a maximum parsimony tree for the
pair of characters X1, X2. By Theorem 1 there exist two trees T1 and T2 such that T1 is
compatible with X1, T2 is compatible with X2 and
dSPR(T1, T ) + dSPR(T2, T ) = i(X1, X2),
implying that dSPR(T1, T2) ≤ dSPR(T1, T ) + dSPR(T2, T ) ≤ i(X1, X2) and hence
dSPR(T1, T2) = i(X1, X2).
