Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed.
%0 Journal Article
%1 Bruen08a
%A Bruen, Trevor C.
%A Bryant, David
%D 2008
%J Ann. Comb.
%K from:davidjamesbryant
%N 1
%P 45-51
%T A subdivision approach to maximum parsimony
%U http://www.springerlink.com/content/66271H7714451874/
%V 12
%X Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed.
@article{Bruen08a,
abstract = {Determining an optimal phylogenetic tree using maximum parsimony, also referred to as the Steiner tree problem in phylogenetics, is NP hard. Here we provide a new formulation for this problem which leads to an analytical and linear time solution when the dimensionality (sequence length, or number of characters) is at most two. This new formulation of the problem provides a direct link between the maximum parsimony problem and the maximum compatibility problem via the intersection graph. The solution for the “two character case” has numerous practical applications in phylogenetics, some of which are discussed.},
added-at = {2009-05-14T23:20:19.000+0200},
author = {Bruen, Trevor C. and Bryant, David},
biburl = {https://www.bibsonomy.org/bibtex/23e8b1263558edf97199e653096eb069c/compevol},
date-modified = {2009-01-28 13:04:38 +1300},
fjournal = {Annals of Combinatorics},
interhash = {a5985044941ce9b1b2fa964c74b026da},
intrahash = {3e8b1263558edf97199e653096eb069c},
issn = {0218-0006},
journal = {Ann. Comb.},
keywords = {from:davidjamesbryant},
month = Apr,
mrclass = {92D15 (05C05 68Q25 68R10)},
mrnumber = {MR2401135},
number = 1,
pages = {45-51},
timestamp = {2009-05-14T23:20:19.000+0200},
title = {A subdivision approach to maximum parsimony},
url = {http://www.springerlink.com/content/66271H7714451874/},
volume = 12,
year = 2008
}