arXiv:math/0504378v2 [math.PR] 28 Sep 2005

A Short Proof that Phylogenetic Tree Reconstruction
by Maximum Likelihood is Hard
Sébastien Roch
Department of Statistics
University of California, Berkeley
February 1, 2008

Abstract
Maximum likelihood is one of the most widely used techniques to infer evolutionary histories.
Although it is thought to be intractable, a proof of its hardness has been lacking. Here, we give
a short proof that computing the maximum likelihood tree is NP-hard by exploiting a connection
between likelihood and parsimony observed by Tuffley and Steel.

1

Introduction

In a series of seminal works, Edwards and Cavalli-Sforza [9], Neyman [15], and Felsenstein [11] applied the maximum likelihood methodology to the problem of inferring phylogenies from molecular
sequences. Since, the many variants of this approach have gained increasing popularity in the systematics literature. This is due in part to the flexibility of the technique in accomodating a variety of
models of evolution as well as to good practical performance. Nevertheless, the approach is not without
a flaw: it has been observed to be highly demanding computationally. Remarkably, the computational
complexity status of the problem has remained elusive. Partial progress was made recently in [1] where
a variant of the problem, known as Ancestral Maximum Likelihood, was shown to be NP-hard. Here,
we resolve the issue by proving that computing the maximum likelihood tree is NP-hard. Moreover,
we show that the log-likelihood is NP-hard to approximate within a constant ratio. Our proof—which
is mostly elementary—combines a connection between likelihood and parsimony observed by Tuffley
and Steel [17] with a result on the hardness of approximating parsimony obtained by Wareham [18].
General references on inferring phylogenies are [12, 16]. For background on NP-completeness and
hardness of approximation, refer to [14, 3]. Many other popular phylogenetic techniques have been
shown to be NP-hard, including parsimony [13, 7], compatibility [8], and distance-based methods [2].
Remark. While writing this paper, Mike Steel brought to our attention that Benny Chor and
Tamir Tuller have recently given an independent proof of this result which now appears in the proceedings of RECOMB 2005 [5]. Similarly to the proof presented here, the Chor-Tuller paper uses
results from [17] and the hardness of approximating vertex cover (from which follows the hardness of
approximating parsimony), but their argument proceeds from a sequence of rather involved constructions. Our reduction has the advantage of being short and elementary. It also sheds some more light
on the interesting connection between likelihood and parsimony.

2

Definitions and Results

The use of maximum likelihood requires the choice of a statistical model of evolution. Here, we consider
the simple binary symmetric model generally known as the Cavender-Farris model [4, 10]. We are given
1

a tree T on n leaves and probabilities of transition on edges p = {pe }e∈E(T ) ∈ [0, 1/2]ET , where E(T )
is the set of edges of T and ET ≡ |E(T )| is the cardinality of E(T ). (All trees considered here have
no internal vertex of degree 2.) A realization of the model is obtained as follows: choose any vertex
as a root; pick a state for the root uniformly at random in {0, 1}; moving away from the root, each
edge e flips the state of its ancestor with probability pe . Let [n] denote the set of leaves. A character
χ assigns to each leaf a state in {0, 1}. An extension of χ is an assignment of states in {0, 1} to all
vertices of T which is equal to χ on the leaves. The set of all extensions of χ is denoted H(χ).
In the Cavender-Farris model, the (modified) log-likelihood of χ on (T, p) is


X
Y
e T, p) ≡ − ln 2P[χ | T, p] = − ln 
(1)
p1e {χ̂(u)6=χ̂(v)} (1 − pe )1{χ̂(u)=χ̂(v)}  ,
L(χ;
χ̂∈H(χ) e=(u,v)∈E(T )

where 1{A} is 1 if A occurs, and 0 otherwise. The data consists of a set of characters X = {χi }ki=1 .
Assuming the characters are independent and identically distributed,
Pktheelog-likelihood of the data
e
is the sum of the log-likelihood of all characters, viz. L(X; T, p) = i=1 L(χi ; T, p). The maximum
e
likelihood (ML) problem consists in computing (T ∗ , p∗ ) minimizing L(X;
T, p) over all trees and transition probability vectors. Note that this is equivalent to minimizing the standard likelihood, without
the factor of 2.
Contrary to ML, maximum parsimony (MP) is not based on a statistical model. Denote by ch(χ̂)
the number of flips in χ̂, i.e. ch(χ̂) = |{(u, v) ∈ E(T ) : χ̂(u) 6= χ̂(v)}|. Let l(χ, T ) be the smallest
number of flips in any extension of χ on T , i.e. l(χ, T ) = minχ̂∈H(χ) ch(χ̂). The parsimony score of T
P
is then l(X, T ) = ki=1 l(χi , T ). The problem MP consists in finding the tree T ∗∗ minimizing l(X, T )
over all trees.
A useful connection between ML and MP was noted by Tuffley and Steel in [17]: if one adds
sufficiently many constant sites (i.e. χ(i) = α, ∀i ∈ [n] for some α ∈ {0, 1}) to the data and applies
the maximum likelihood technique, then one necessarily chooses the most parsimonious tree. This
could serve as the basis for a reduction, except that the Tuffley-Steel bounds require an exponential
number of constant sites. Our contribution is to show that a polynomial number of sites imposes
a weaker relationship between likelihood and parsimony, but that this is sufficient for the following
reason. Parsimony is in fact hard to approximate, that is, even the seemingly easier task of obtaining
a solution close to optimal is hard. This result is due to Wareham [18].
We prove the following theorem. We first define the notion of approximation algorithm.
Definition 1 Let Π be an optimization problem (minimization). Let I denote an instance of Π and
OPT(I), the optimal value of a solution to I. For c > 0, a (1 + c)-approximation algorithm for Π is
a polynomial-time algorithm that is guaranteed to return, for any instance I, a solution with objective
value m satisfying m ≤ (1 + c)OPT(I).
Theorem 1 There exists a c > 0 sufficiently small so that there is no (1 + c)-approximation algorithm
for ML unless P = NP. In particular, ML is NP-hard. (The approximation claim relates to the
e
modified log-likelihood L.)

3

Proof

In this section, we prove our main result. The proof follows easily from the following propositions. The
first proposition borrows heavily from [17] although we need somewhat tighter estimates. The second
proposition follows directly from the work of [18, 6].
Proposition 1 Let c′ > c > 0 be constants. If there is a (1 + c)-approximation algorithm for ML then
there is a (1 + c′ )-approximation algorithm for MP.
2

Proposition 2 ([18, 6]) There exists a c′ > 0 sufficiently small so that there is no (1+c′ )-approximation
algorithm for MP unless P = NP.
As in [17], the reduction from MP to ML consists in adjoining a large number of constant sites
to the data. Let ε > 0 be a small constant and M = max{2n, k}. Fix Nc = M 1/ε . Denote by
c
X0 = {χi }k+N
the set X augmented with Nc all-0 characters. For all χ, let Nχ be the number of
i=1
characters equal to χ in X. To avoid the factors of 2 from the probability of the root state, we define
e 0 | p, T ] = 2k+Nc P[X0 | p, T ] for p ∈ [0, 1/2]ET . Also, let f˜χ = 2P[χ | p, T ]. Let 0 be the all-0
P[X
character and 1, the all-1 character. We make three claims, from which Proposition 1 follows.
Claim 1 Let ε > 0 and Nc = M 1/ε for M = max{2n, k}. Let pe = q =
Then

e
P[X0 | p,T ]
− lnln(k+N
c)

l(X,T )
ET (k+Nc ) ,

for all e ∈ E(T ).

≤ (1 + 2ε)l(X, T ), for M large enough.

Proof. Note that, by a calculation identical to [17, Lemma 5],




X

q ch(χ̂) (1 − q)ET −ch(χ̂)  ≥ ln q l(χ,T ) (1 − q)ET ≥ l(χ, T ) ln q − ET q + 2q 2 ,
ln f˜χ = ln 
χ̂∈H(χ)

where we have used a standard Taylor expansion (note that we have q ≤ 1/2 by definition). This
bound applies in particular to the case χ = 0. Then, as in [17, Lemma 5] again,


Y Nχ
e 0 | p, T ]
ln P[X
1
−
f˜χ 
= −
ln f˜0N0 +Nc
ln(k + Nc )
ln(k + Nc )
χ6=0


1
(k + Nc )ET (q + 2q 2 ) − l(X, T ) ln q
ln(k + Nc )



1
ln ET − ln l(X, T )
l(X, T )
+
= l(X, T ) 1 +
1+2
ln(k + Nc )
ln(k + Nc )
ET (k + Nc )



1
M
ln M
+
1 + 2 1/ε
≤ l(X, T ) 1 +
1/ε
1/ε
ln M
ln M
M
≤ (1 + 2ε)l(X, T ),
≤

e 0 | p, T ] ≤ 1 because P[χ | p, T ] ≤ 1/2 by symmetry.) 
for M large enough. (Note that P[X
e

P[X0 | p,T ]
Claim 2 For all p ∈ [0, 1/2]ET such that − lnln(k+N
≤ l(X, T ), one has pe ≤ p̄, ∀e ∈ E(T ), with
c)

p̄ ≡

l(X,T ) ln(k+Nc )
.
Nc

Proof. Assume edge e is such that pe > p̄. Take any two leaves u, v joined by a path going through
e. As observed in [17, Formula (11)], the probability that χ(u) 6= χ(v) is at least pe . In particular, the
probability that a character is constant is less than 1 − pe and − ln f˜0 ≥ − ln(1 − pe ) ≥ pe (by the 0 − 1
symmetry). Therefore,




Y
e
ln P[X0 | p, T ]
1
1
Nχ 
N0 +Nc
Nc
˜
˜
˜

−
ln f0
fχ
> l(X, T ),
=−
ln f0
≥−
ln(k + Nc )
ln(k + Nc )
ln(k + Nc )
χ6=0

by pe > p̄ and f˜χ ≤ 1 (by the 0 − 1 symmetry). This contradicts the assumption. 

e

P[X0 | p,T ]
≥
Claim 3 Let ε > 0 and Nc = M 1/ε for M = max{2n, k}. For all p ∈ [0, 1/2]ET , we have − lnln(k+N
c)
(1 − 5ε)l(X, T ) for M large enough.

3

Proof. For this proof, we need a better estimate than [17, Lemma 6]. From Claim 2, the result holds
whenever maxe pe > p̄. Therefore, we can assume that for all e ∈ E(T ), pe ≤ p̄. Then,

ET −l(χ,T ) 
ET −l(χ,T )
X
X
X
ET
ch(χ̂)
α+l(χ,T )
˜
fχ ≤
p̄
≤
p̄
≤
(ET p̄)α+l(χ,T ) ≤ ET (ET p̄)l(χ,T ) ,
α
+
l(χ,
T
)
α=0
α=0
χ̂∈H(χ)

when M is large enough so that p̄ < 1/ET . For constant sites, we use the bound f˜0 , f˜1 ≤ 1 (by the
0 − 1 symmetry). Therefore,


Y
e 0 | p, T ]
1
ln P[X
N
f˜χ χ 
= −
ln f˜0N0 +Nc
−
ln(k + Nc )
ln(k + Nc )
χ6=0


X
1

≥ −
Nχ ln(ET (ET p̄)l(χ,T ) )
ln(k + Nc )
χ6=0,1




X
1
ET l(X, T ) ln(k + Nc ) 
l(X, T ) 

Nχ ln ET  − ln
−
≥
ln(k + Nc )
l(X, T )
Nc
χ6=0,1


l(X, T )
− ln ET + ln Nc − ln(ET2 k ln(k + Nc ))
1 + ln Nc

l(X, T ) 
1/ε
1/ε
≥
ln
M
−
4
ln
M
−
ln(1
+
ln
M
)
1 + ln M 1/ε
≥ l(X, T )(1 − 5ε),
≥

for M large enough. 
Proof. (Proposition 1) Let T ∗ be a maximum likelihood tree with corresponding edge probabilities
p∗ , and T ∗∗ , be a maximum parsimony tree. Assume we have a polynomial-time algorithm which is
guaranteed to return a tree T ′ and edge probabilities p′ such that


e 0 | T ′ , p′ ] ≤ (1 + c) − ln P[X
e 0 | T ∗ , p∗ ] .
− ln P[X

Then the claims above and the optimality of T ∗ imply that, if p∗∗ is chosen as in Claim 1 (for T = T ∗∗ ),
!
e 0 | T ′ , p′ ]
− ln P[X
1
′
l(X, T ) ≤
1 − 5ε
ln(k + Nc )
!
e 0 | T ∗ , p∗ ]
1 + c − ln P[X
≤
1 − 5ε
ln(k + Nc )
!
e 0 | T ∗∗ , p∗∗ ]
1 + c − ln P[X
≤
1 − 5ε
ln(k + Nc )
(1 + c)(1 + 2ε)
l(X, T ∗∗ )
1 − 5ε
≤ (1 + c′ )l(X, T ∗∗ ),

≤

for ε small enough. 
Proof. (Proposition 2) Wareham [18, Theorem 45 Part 3] gives a reduction from vertex cover with
bounded degree B (B-VC) to maximum parsimony. (Wareham actually defines MP as a Steiner tree
problem on the Hamming cube {0, 1}k but the correspondence with our definition is straightforward.)
The reduction is such that the existence of a (1 + c′ )-approximation algorithm for maximum parsimony
implies the existence of a (1 + 2Bc′ )-approximation algorithm for B-VC. By [6], for a sufficiently large
B, there is no 1.16-approximation algorithm for B-VC unless P = NP. 
4

Acknowledgment
I thank Elchanan Mossel, Mike Steel and Tandy Warnow for discussions and encouragements. I
gratefully acknowledge the partial support of CIPRES (NSF ITR grant # NSF EF 03-31494), NSERC,
NATEQ, and a Loève Fellowship. This project was initiated at a CIPRES retreat. I also thank Martin
Nowak and the Program for Evolutionary Dynamics at Harvard University where part of this work
was done.

References
[1] L. Addario-Berry, B. Chor, M. T. Hallett, J. Lagergren, A. Panconesi, and T. Wareham, “Ancestral
Maximum Likelihood of Evolutionary Trees is Hard,” Journal of Bioinformatics and Computational
Biology, vol. 2, no. 2, pp. 257-271, 2004.
[2] R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, and M. Thorup, “On the approximability of numerical taxonomy (fitting distances by tree metrics),” SIAM Journal on Computing,
vol. 28, pp. 1073-1085, 1999.
[3] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, Complexity and Approximation, Springer, Berlin, 1999.
[4] J. Cavender, “Taxonomy with confidence,” Mathematical Biosciences, vol. 40, pp. 271-280, 1978.
[5] B. Chor and T. Tuller, “Maximum Likelihood of Evolutionary Trees is Hard,” In: Proceedings
of the 9th International Conference on Computational Molecular Biology (RECOMB 2005), ACM
Press, Cambridge, 2005.
[6] A. Clementi, and L. Trevisan, “Improved Non-Approximability Results for Minimum Vertex Cover
with Density Constraints,” Theor. Comput. Sci., vol. 225, no. 1-2, pp. 113-128, 1999.
[7] W. Day, D. Jonhson, and D. Sankoff, “The computational complexity of inferring rooted phylogenies
by parsimony,” Mathematical Biosciences, vol. 81, pp. 33-42, 1986.
[8] W. Day and D. Sankoff, “The computational complexity of inferring phylogenies by compatibility,”
Systematic Zoology, vol. 35, pp. 224-229, 1986.
[9] A. W. F. Edwards and L. L. Cavalli-Sforza, “Reconstruction of evolutionary trees,” In: Phenetic
and Phylogenetic Classification, eds. V. H. Heywood and J. McNeill, Systematics Association,
London, vol. 6, pp. 67-76, 1964.
[10] J. S. Farris, “A probability model for inferring evolutionary trees,” Systematic Zoology, vol. 22,
pp. 250-256, 1973.
[11] J. Felsenstein, “Evolutionary trees from DNA sequences: a maximum likelihood approach,” J.
Molecular Evolution, vol. 17, pp. 368-376, 1981.
[12] J. Felsenstein, Inferring Phylogenies, Sinauer Associates, Sunderland, 2004.
[13] L. Foulds and R. Graham, “The Steiner problem in phylogeny is NP-complete,” Advances in
Applied Mathematics, vol. 3, pp. 43-49, 1982.
[14] M. R. Garey and D. S. Johnson, Computers and Intractability. A Guide to the Theory of NPcompleteness, W. H. Freeman, San Francisco, 1976.

5

[15] J. Neyman, “Molecular studies of evolution: a source of novel statistical problems,” In: Statistical
decision theory and related topics, eds. S.S Gupta and J. Yackel, Academic Press, New York, pp.
1-27, 1971.
[16] C. Semple and M. Steel, Phylogenetics, Oxford University Press, 2003.
[17] C. Tuffley and M. Steel, “Links between maximum likelihood and maximum parsimony under a
simple model of site substitution,” Bull Math Biol., vol. 59, no. 3, pp. 581-607, 1997.
[18] H. T. Wareham, On the Computational Complexity of Inferring Evolutionary Trees, M.Sc. thesis,
Technical Report no. 9301, Department of Computer Science, Memorial University of Newfoundland, 1993.

6

