skip to main content
article

Approximate Maximum Parsimony and Ancestral Maximum Likelihood

Published: 01 January 2010 Publication History

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.

References

[1]
L. Addario-Berry, B. Chor, M. Hallett, J. Lagergren, A. Panconesi, and T. Wareham, "Ancestral Maximum Likelihood of Evolutionary Trees Is Hard," J. Bioinformatics and Computational Biology, vol. 2, no. 2, pp. 257- 271, 2004.
[2]
D. Barry and J.A. Hartigan, "Statistical Analysis of Hominoid Molecular Evolution," Statistical Science, vol. 2, pp. 191-210, 1987.
[3]
P. Berman and V. Ramaiyer, "Improved Approximations for the Steiner Tree Problem," J. Algorithms, vol. 17, pp. 381-408, 1994.
[4]
T. Cover and J. Thomas, Elements of Information Theory. John Wiley & Sons, 1991.
[5]
J. Felsenstein, "Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach," J. Molecular Evolution, vol. 17, pp. 368-376, 1981.
[6]
W.M. Fitch, "Toward Defining the Course of Evolution: Minimum Change for Specified Tree Topology," Systematic Zoology, vol. 20, pp. 406-416, 1971.
[7]
L.R. Foulds and R.L. Graham, "The Steiner Problem in Phylogeny Is NP-Complete," Advances in Applied Math., vol. 3, pp. 43-49, 1982.
[8]
N. Goldman, "Maximum Likelihood Inference of Phylogenetic Trees, with Special Reference to a Poisson Process Model of DNA Substitution and to Parsimony Analyses," Systematic Zoology, vol. 39, pp. 345-361, 1990.
[9]
S. Hougardy and H.J. Prömel, "A 1.598 Approximation Algorithm for the Steiner Problem in Graphs," Proc. 10th ACM-SIAM Symp. Discrete Algorithms (SODA '99), pp. 448-453, 1999.
[10]
T.H. Jukes and C.R. Cantor, "Evolution of Protein Molecules," Mammalian Protein Metabolism, H.N. Munro, ed., pp. 21-132, Academic Press, 1969.
[11]
R. Karp, "Reducibility among Combinatorial Problems," Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, eds., pp. 85-103, Plenum Press, 1972.
[12]
M. Kimura, "Estimation of Evolutionary Sequences between Homologous Nucleotide Sequences," Proc. Nat'l Academy of Sciences USA, vol. 78, pp. 454- 458, 1981.
[13]
J. Neyman, "Molecular Studies of Evolution: A Source of Novel Statistical Problems," Statistical Decision Theory and Related Topics, S. Gupta and Y. Jackel, eds., pp. 1-27, Academic Press, 1971.
[14]
T. Pupko, I. Péer, R. Shamir, and D. Graur, "A Fast Algorithm for Joint Reconstruction of Ancestral Amino-Acid Sequences," Molecular Biology and Evolution, vol. 17, no. 6, pp. 890-896, 2000.
[15]
G. Robins and A. Zelikovsky, "Tighter Bounds for Graph Steiner Tree Approximation," SIAM J. Discrete Math., vol. 19, no. 1, pp. 122-134, 2005.
[16]
M. Steel and D. Penny, "Parsimony, Likelihood, and the Role of Models in Molecular Phylogenetics," Molecular Biology and Evolution, vol. 17, no. 6, pp. 839-850, 2000.
[17]
H. Takahashi and A. Matsuyama, "An Approximate Solution for the Steiner Problem in Graphs," Math. Japonica 4, pp. 573-577, 1980.
[18]
A.Z. Zelikovsky, "An 11/6-Approximation Algorithm for the Steiner Problem on Graphs," Proc. Fourth Czechoslovakian Symp. Combinatorics, Graphs and Complexity, J. Nesetril and M. Fiedler, eds., Annals of Discrete Math., vol. 51, pp. 351-354, 1992.

Cited By

View all
  • (2014)Molecular phylogeny analysis using correlation distance and spectral distanceInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2014.06489010:4(391-406)Online publication date: 1-Sep-2014
  • (2009)Shrinkage Effect in Ancestral Maximum LikelihoodIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2008.1076:1(126-133)Online publication date: 1-Jan-2009
  1. Approximate Maximum Parsimony and Ancestral Maximum Likelihood

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics
      IEEE/ACM Transactions on Computational Biology and Bioinformatics  Volume 7, Issue 1
      January 2010
      190 pages

      Publisher

      IEEE Computer Society Press

      Washington, DC, United States

      Publication History

      Published: 01 January 2010
      Published in TCBB Volume 7, Issue 1

      Author Tags

      1. Phylogenetic reconstruction
      2. Steiner trees
      3. ancestral maximum likelihood
      4. approximation algorithms.
      5. maximum parsimony

      Qualifiers

      • Article

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)3
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 05 Mar 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2014)Molecular phylogeny analysis using correlation distance and spectral distanceInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2014.06489010:4(391-406)Online publication date: 1-Sep-2014
      • (2009)Shrinkage Effect in Ancestral Maximum LikelihoodIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2008.1076:1(126-133)Online publication date: 1-Jan-2009

      View Options

      Login options

      Full Access

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media