Warning: imagejpeg(C:\Inetpub\vhosts\kidney.de\httpdocs\phplern\25302568
.jpg): Failed to open stream: No such file or directory in C:\Inetpub\vhosts\kidney.de\httpdocs\pget.php on line 117 J+Comput+Biol
2014 ; 21
(11
): 799-808
Nephropedia Template TP
gab.com Text
Twit Text FOAVip
Twit Text #
English Wikipedia
The worst case complexity of maximum parsimony
#MMPMID25302568
Carmel A
; Musa-Lempel N
; Tsur D
; Ziv-Ukelson M
J Comput Biol
2014[Nov]; 21
(11
): 799-808
PMID25302568
show ga
One of the core classical problems in computational biology is that of
constructing the most parsimonious phylogenetic tree interpreting an input set of
sequences from the genomes of evolutionarily related organisms. We reexamine the
classical maximum parsimony (MP) optimization problem for the general
(asymmetric) scoring matrix case, where rooted phylogenies are implied, and
analyze the worst case bounds of three approaches to MP: The approach of
Cavalli-Sforza and Edwards, the approach of Hendy and Penny, and a new
agglomerative, "bottom-up" approach we present in this article. We show that the
second and third approaches are faster than the first one by a factor of ?(?n)
and ?(n), respectively, where n is the number of species.
free
free
free
