article

Progressive Tree Neighborhood Applied to the Maximum Parsimony Problem

Authors:

Adrien Goeffon,

Jean-Michel Richer,

Jin-Kao HaoAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 5, Issue 1

Pages 136 - 145

https://doi.org/10.1109/TCBB.2007.1065

Published: 01 January 2008 Publication History

Abstract

The Maximum Parsimony problem aims at reconstructing a phylogenetic tree from DNA sequences while minimizing the number of genetic transformations. To solve this NP-complete problem, heuristic methods have been developed, often based on local search. In this article, we focus on the influence of the neighborhood relations. After analyzing the advantages and drawbacks of the well-known NNI, SPR and TBR neighborhoods, we introduce the concept of Progressive Neighborhood which consists in constraining progressively the size of the neighborhood as the search advances. We empirically show that applied to the Maximum Parsimony problem, this progressive neighborhood turns out to be more efficient and robust than the classic neighborhoods using a descent algorithm. Indeed, it allows to find better solutions with a smaller number of iterations or trees evaluated.

References

[1]

A.A. Andreatta and C.C. Ribeiro, "Heuristics for the Phylogeny Problem," J. Heuristics, vol. 8, pp. 429-447, 2002.

Digital Library

[2]

B.L. Allen and M. Steel, "Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees," Annals of Combinatorics, vol. 5, no. 1, pp. 1-15, 2000.

[3]

O.R.P. Bininda-Emonds, "Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life," Computational Biology, vol. 4, Kluwer Academic Publishers, 2004.

[4]

L.L. Cavalli-Sforza and A.W.F. Edwards, "Phylogenetic Analysis: Models and Estimation Procedures," Evolution, vol. 32, pp. 550- 570, 1967.

[5]

I. Charon and O. Hudry, "The Noising Methods: A Generalization of Some Metaheuristics," European J. Operational Research, vol. 135, pp. 86-101, 2001.

[6]

M.W. Chase et al., "Phylogenetics of Seed Plants: An Analysis of Nucleotide-Sequences from the Plastid Gene rbcL," Annals of the Missouri Botanical Garden, vol. 80, pp. 528-580, 1993.

[7]

A.W.F. Edwards and L.L. Cavalli-Sforza, "The Reconstruction of Evolution," Annals of Human Genetics, vol. 27, pp. 105-106, 1963.

[8]

J. Felsenstein, "Evolutionary Trees from DNA Sequences: A Maximum Likelihood Approach," J. Molecular Evolution, vol. 17, pp. 368-376, 1981.

[9]

J. Felsenstein, Inferring Phylogenies. Sinauer Assoc., 2003.

[10]

T.A. Feo and M.G.C. Resende, "Greedy Randomized Adaptative Search Procedures," J. Global Optimization, vol. 6, pp. 109-133, 1995.

[11]

W. Fitch, "Towards Defining Course of Evolution: Minimum Change for a Specified Tree Topology," Systematic Zoology, vol. 20, pp. 406-416, 1971.

[12]

W.M. Fitch and E. Margoliash, "Construction of Phylogenetic Trees," Science, vol. 155, pp. 279-284, 1967.

[13]

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.

Digital Library

[14]

G. Ganapathy, V. Ramachandran, and T. Warnow, "On Contract-and-Refine Transformations between Phylogenetic Trees," Proc. ACM-SIAM Symp. Discrete Algorithms (SODA '04), pp. 900-909, 2004.

Digital Library

[15]

O. Gascuel, "On the Optimization Principle in Phylogenetic Analysis and the Minimum Evolution Criterion," Biology and Evolution, vol. 17, pp. 401-405, 2000.

[16]

A. Goëffon, J.-M. Richer, and J.-K. Hao, "Local Search for the Maximum Parsimony Problem," Lecture Notes in Computer Science, vol. 3612, pp. 678-683, Springer, 2005.

Digital Library

[17]

A. Goëffon, J.-M. Richer, and J.-K. Hao, "A Distance-Based Information Preservation Tree Crossover for the Maximum Parsimony Problem," Lecture Notes in Computer Science, vol. 4193, pp. 761-770, Springer, 2006.

Digital Library

[18]

P.A. Goloboff, "Character Optimisation and Calculation of Tree Lengths," Cladistics, vol. 9, pp. 433-436, 1993.

[19]

P.A. Goloboff, "Analyzing Large Data Sets in Reasonable Times: Solutions for Composite Optima," Cladistics, vol. 15, pp. 415-428, 1999.

[20]

P.A. Goloboff, J.S. Farris, and K. Nixon, "TNT: Tree Analysis Using New Technology," http://www.cladistics.com/ aboutTNT.html, 2003.

[21]

P. Hansen and N. Mladenovic, "An Introduction to Variable Neighborhood Search," Metaheuristics, Advances and Trends in Local Search Paradigms for Optimization, S. Voss et al., eds., pp. 433-458, Kluwer Academic Publishers, 1999.

[22]

D. Hillis, C. Moritz, and B. Mable, Molecular Systematics. Sinauer, 1996.

[23]

H.H. Hoos and T. Stützle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann, 2005.

Digital Library

[24]

M. Kimura, "A Simple Model for Estimating Evolutionary Rates of Base of Base Substitutions through Comparative Studies of Nucleotide Sequence," J. Molecular Evolution, vol. 16, pp. 111- 120, 1980.

[25]

M.K. Kuhner and J. Felsenstein, "A Simulation Comparison of Phylogeny Algorithms under Equal and Unequal Evolutionary Rates," Molecular Biology and Evolution, vol. 11, pp. 459-468, 1994, (Erratum 12:525).

[26]

M. Luckow and R.A. Pimentel, "An Empirical Comparison of Numerical Wagner Computer Programs," Cladistics, vol. 1, pp. 47- 66, 1985.

[27]

D.R. Maddison, "The Discovery and Importance of Multiple Islands of Most-Parsimonious Trees," Systematic Zoology, vol. 43, no. 3, pp. 315-328, 1991.

[28]

K.C. Nixon, "The Parsimony Ratchet, A New Method for Rapid Parsimony Analysis," Cladistics, vol. 15, pp. 407-414, 1999.

[29]

C.C. Ribeiro and D.S. Vianna, "A GRASP/VND Heuristic for the Phylogeny Problem Using a New Neighborhood Structure," Int'l Trans. Operational Research, vol. 12, pp. 1-14, 2005.

[30]

D.F. Robinson, "Comparison of Labeled Trees with Valency Three," J. Combinatorial Theory, vol. 11, pp. 105-119, 1971.

[31]

N. Saitou and M. Nei, "The Neighbor-Joining Method: A New Method for Reconstructing Phylogenetic Trees," Molecular Biology and Evolution, vol. 4, pp. 406-425, 1987.

[32]

E. Schröder, "Vier Kombinatorische Probleme," Zeitschrift fur Mathematik und Physik, vol. 15, pp. 361-376, 1870.

[33]

R.R. Sokal and C.D. Michener, A Statistical Method for Evaluating Systemaic Relationships, vol. 38, Univ. of Kansas Science Bull., pp. 1409-1438, 1958.

[34]

R.R. Sokal and P.H.A. Sneath, Principles of Numerical Taxonomy. W.H. Freeman, 1963.

[35]

D.L. Swofford and G.J. Olsen, "Phylogeny Reconstruction," Molecular Systematics, D.M. Hillis and C. Moritz, eds., chapter 11, pp. 411-501, 1990.

[36]

D.L. Swofford, "PAUP^*: Phylogenetic Analysis Using Parsimony 4.0 Beta, 2002," Molecular Systematics, chapter 11, pp. 411-501, 1990.

[37]

M.S. Waterman and T.F. Smith, "On the Similarity of Dendograms," J. Theoretical Biology, vol. 73, pp. 789-800, 1978.

Cited By

Corts RAlachiotis N(2023)A Survey of Processing Systems for Phylogenetics and Population GeneticsACM Transactions on Reconfigurable Technology and Systems10.1145/358803316:3(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3588033
Santander-Jiménez SVega-Rodríguez M(2019)Comparative Analysis of Intra-Algorithm Parallel Multiobjective Evolutionary Algorithms: Taxonomy Implications on Bioinformatics ScenariosIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.285478830:1(63-78)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2854788
Santander-Jiménez SVega-Rodríguez MSousa L(2018)Multiobjective Frog-Leaping Optimization for the Study of Ancestral Relationships in Protein DataIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.277459922:6(879-893)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1109/TEVC.2017.2774599
Show More Cited By

Index Terms

Progressive Tree Neighborhood Applied to the Maximum Parsimony Problem

Recommendations

Recombination and phylogeny: effects and detection

The role of phylogeny in guiding comparative studies is rapidly growing in the post genomic era. Most phylogeny reconstruction methods though, assume a single tree underlying a given alignment of sequences. However, when events such as recombination ...
Approximate Maximum Parsimony and Ancestral Maximum Likelihood

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 ...
Reconstructing Phylogenetic Networks Using Maximum Parsimony
CSB '05: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference

Phylogenies the evolutionary histories of groups of organisms are one of the most widely used tools throughout the life sciences, as well as objects of research within systematics, evolutionary biology, epidemiology, etc. Almost every tool devised to ...

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 5, Issue 1

January 2008

159 pages

ISSN:1545-5963

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2008

Published in TCBB Volume 5, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
225
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Corts RAlachiotis N(2023)A Survey of Processing Systems for Phylogenetics and Population GeneticsACM Transactions on Reconfigurable Technology and Systems10.1145/358803316:3(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3588033
Santander-Jiménez SVega-Rodríguez M(2019)Comparative Analysis of Intra-Algorithm Parallel Multiobjective Evolutionary Algorithms: Taxonomy Implications on Bioinformatics ScenariosIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2018.285478830:1(63-78)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TPDS.2018.2854788
Santander-Jiménez SVega-Rodríguez MSousa L(2018)Multiobjective Frog-Leaping Optimization for the Study of Ancestral Relationships in Protein DataIEEE Transactions on Evolutionary Computation10.1109/TEVC.2017.277459922:6(879-893)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.1109/TEVC.2017.2774599
Villalobos-Cid MDorn MInostroza-Ponta M(2018)Performance Comparison of Multi-Objective Local Search Strategies to Infer Phylogenetic Trees2018 IEEE Congress on Evolutionary Computation (CEC)10.1109/CEC.2018.8477666(1-8)Online publication date: 8-Jul-2018
https://dl.acm.org/doi/10.1109/CEC.2018.8477666
Santander-Jiménez SVega-Rodríguez M(2017)Using mixed mode programming to parallelize an indicator-based evolutionary algorithm for inferring multiobjective phylogenetic historiesSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-016-2219-621:19(5601-5620)Online publication date: 1-Oct-2017
https://dl.acm.org/doi/10.1007/s00500-016-2219-6
Santander-Jiménez SVega-Rodríguez M(2015)A hybrid approach to parallelize a fast non-dominated sorting genetic algorithm for phylogenetic inferenceConcurrency and Computation: Practice & Experience10.1002/cpe.326927:3(702-734)Online publication date: 10-Mar-2015
https://dl.acm.org/doi/10.1002/cpe.3269
Santander-Jiménez SVega-Rodríguez MAlba E(2013)A comparative study on distance methods applied to a multiobjective firefly algorithm for phylogenetic inferenceProceedings of the 15th annual conference companion on Genetic and evolutionary computation10.1145/2464576.2482739(1587-1594)Online publication date: 6-Jul-2013
https://dl.acm.org/doi/10.1145/2464576.2482739
Santander-Jiménez SVega-Rodríguez M(2013)A multiobjective proposal based on the firefly algorithm for inferring phylogeniesProceedings of the 11th European conference on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics10.1007/978-3-642-37189-9_13(141-152)Online publication date: 3-Apr-2013
https://dl.acm.org/doi/10.1007/978-3-642-37189-9_13
Derbel HDerbel BMoore J(2012)On neighborhood tree searchProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330338(1261-1268)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330338
Santander-Jiménez SVega-Rodríguez MGómez-Pulido JSánchez-Pérez J(2012)Comparing different operators and models to improve a multiobjective artificial bee colony algorithm for inferring phylogeniesProceedings of the First international conference on Theory and Practice of Natural Computing10.1007/978-3-642-33860-1_16(187-200)Online publication date: 2-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33860-1_16
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents