Approximate maximum parsimony and ancestral maximum likelihood

Noga Alon; Benny Chor; Fabio Pardi; Anat Rapoport

doi:10.1109/TCBB.2008.13

Approximate maximum parsimony and ancestral maximum likelihood

Noga Alon, Benny Chor, Fabio Pardi, Anat Rapoport

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

Original language	English (US)
Article number	4429176
Pages (from-to)	183-187
Number of pages	5
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	7
Issue number	1
DOIs	https://doi.org/10.1109/TCBB.2008.13
State	Published - Jan 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Applied Mathematics
Genetics
Biotechnology

Keywords

Ancestral maximum likelihood
Approximation algorithms.
Biology and genetics
Combinatorial algorithms
Computations on discrete structures
Constrained optimization
Maximum parsimony
Phylogenetic reconstruction
Steiner trees
Trees

Access to Document

10.1109/TCBB.2008.13

Cite this

@article{91b08da52eff4a1f9ac0283a168d7f29,

title = "Approximate maximum parsimony and ancestral maximum likelihood",

abstract = "We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.",

keywords = "Ancestral maximum likelihood, Approximation algorithms., Biology and genetics, Combinatorial algorithms, Computations on discrete structures, Constrained optimization, Maximum parsimony, Phylogenetic reconstruction, Steiner trees, Trees",

author = "Noga Alon and Benny Chor and Fabio Pardi and Anat Rapoport",

note = "Funding Information: Many thanks to Alexander Zelikovsky for his help in clarifying some subtle points in existing Steiner approximation algorithms. The work of Noga Alon was supported in part by the Israel Science Foundation, by a USA-Israel BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Part of this work was done while Benny Chor was visiting the European Bioinformatics Institute, Hinxton, Cambridge, UK.",

year = "2010",

month = jan,

doi = "10.1109/TCBB.2008.13",

language = "English (US)",

volume = "7",

pages = "183--187",

journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",

issn = "1545-5963",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - Approximate maximum parsimony and ancestral maximum likelihood

AU - Alon, Noga

AU - Chor, Benny

AU - Pardi, Fabio

AU - Rapoport, Anat

N1 - Funding Information: Many thanks to Alexander Zelikovsky for his help in clarifying some subtle points in existing Steiner approximation algorithms. The work of Noga Alon was supported in part by the Israel Science Foundation, by a USA-Israel BSF grant, and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Part of this work was done while Benny Chor was visiting the European Bioinformatics Institute, Hinxton, Cambridge, UK.

PY - 2010/1

Y1 - 2010/1

N2 - We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

AB - We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP-hard, so we seek approximate solutions. We formulate the two problems as Steiner tree problems under appropriate distances. The gist of our approach is the succinct characterization of Steiner trees for a small number of leaves for the two distances. This enables the use of known Steiner tree approximation algorithms. The approach leads to a 16/9 approximation ratio for AML and asymptotically to a 1.55 approximation ratio for MP.

KW - Ancestral maximum likelihood

KW - Approximation algorithms.

KW - Biology and genetics

KW - Combinatorial algorithms

KW - Computations on discrete structures

KW - Constrained optimization

KW - Maximum parsimony

KW - Phylogenetic reconstruction

KW - Steiner trees

KW - Trees

UR - http://www.scopus.com/inward/record.url?scp=76849097970&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=76849097970&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2008.13

DO - 10.1109/TCBB.2008.13

M3 - Article

C2 - 20150680

AN - SCOPUS:76849097970

SN - 1545-5963

VL - 7

SP - 183

EP - 187

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

IS - 1

M1 - 4429176

ER -

Approximate maximum parsimony and ancestral maximum likelihood

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this