Production
https://prod.org.br/doi/10.1590/S0103-65132013005000050
Production
Article

Hybrid GRASP heuristics for the phylogeny problem combining path-relinking and genetic algorithm as an intensification strategy

Vianna, Dalessandro Soares; Vianna, Marcilene de Fátima D.

Downloads: 0
Views: 119

Abstract

A phylogeny is a tree that relates taxonomic units based on their similarity over a set of characteristics. The phylogeny problem under the parsimony criterion consists in finding a phylogeny with a minimum number of evolutionary steps. We propose hybrid heuristic methods - based on GRASP, path-relinking and genetic algorithm methodologies - to build a phylogeny while minimizing parsimony. Computational experiments using benchmark conditions are reported, and the results obtained by the proposed hybrid heuristics are compared with the solutions obtained by a traditional GRASP (without hybridization) heuristic and with previously reported solutions in the literature. The experimental results illustrate that the proposed heuristics are efficient in terms of solution quality and time-to-target-value.

Keywords

Phylogeny problem. Evolutionary trees. GRASP. Path-relinking. Genetic algorithm. Heuristics.

References



AIEX, R. M.; RESENDE, M. G. C.; RIBEIRO, C. C. Probability distribution of solution time in GRASP: An experimental investigation. Journal of Heuristics, v. 8, p. 343-373, 2002. http://dx.doi.org/10.1023/A:1015061802659

ANDREATTA, A. A. Uma arquitetura abstrata de domínio para o desenvolvimento de heurísticas de busca local com uma aplicação ao problema da filogenia. 1998. Tese (Doutorado em Informática)-Pontifícia Universidade Católica, Rio de Janeiro, 1998.

ANDREATTA, A. A; RIBEIRO, C. C. Heuristics for the phylogeny problem. Journal of Heuristics, v. 8, p. 429-447, 2002. http://dx.doi.org/10.1023/A:1015439913121

AYALA, F. J. The myth of Eve: Molecular biology and human origins. Science, v. 270, p. 1930-1939, 1995. PMid:8533083. http://dx.doi.org/10.1126/science.270.5244.1930

BODLAENDER, H.; FELLOWS, M.; WARNOW, T. Two strikes against the perfect phylogeny problem. In: INTERNATIONAL CONFERENCE ON ALGORITHMS, LANGUAGES AND PROGRAMMING, 1992, Wien. Proceedings... Springer-Verlag, 1992. p. 273-283.

COTTA, C. Scatter search with path relinking for phylogenetic inference. European Journal of Operational Research, v. 169, p. 520-532, 2006. http://dx.doi.org/10.1016/j.ejor.2004.08.013

DAY, W. H. E.; JOHNSON, D. S.; SANKOFF, D. The computational complexity of inferring rooted phylogenies by parsimony. Mathematical Biosciences, v. 81, p. 33-42, 1986. http://dx.doi.org/10.1016/0025-5564(86)90161-6

EDWARDS, A.; CAVALLI-SFORZA, L. Reconstruction of evolutionary trees. Phenetic and Phylogenetic Classification, v. 6, p. 67-76, 1964.

FEO, T. A.; RESENDE, M. G. C. Greedy randomized adaptive search procedures. Journal of Global Optimization, v. 6, p. 109-133, 1995. http://dx.doi.org/10.1007/BF01096763

FESTA, P.; RESENDE, M. G. C. An annotated bibliography of GRASP - part I: Algorithms. International Transactions in Operational Research, v. 16, p. 1-24, 2009a. http://dx.doi.org/10.1111/j.1475-3995.2009.00663.x

FESTA, P.; RESENDE, M. G. C. An annotated bibliography of GRASP - part II: Applications. International Transactions in Operational Research, v. 16, p. 131-172, 2009b. http://dx.doi.org/10.1111/j.1475-3995.2009.00664.x

FOULDS, L. R.; GRAHAM, R. L. The Steiner problem in phylogeny is NP-Complete. Advances in Applied Mathematics, v. 3, p. 43-49, 1982a. http://dx.doi.org/10.1016/S0196-8858(82)80004-3

FOULDS, L. R.; GRAHAM, R. L. Unlikelihood that minimal phylogenie for a realistic biological study can be constructed in reasonable computational time. Mathematical Biosciences, v. 60, p. 133-142, 1982b. http://dx.doi.org/10.1016/0025-5564(82)90125-0

GLOVER, F. Tabu search and adaptive memory programing - Advances, applications and challenges. In: BARR, R. S.; HELGASON, R. V.; KENNINGTON, J. L. (Eds.). Interfaces in Computer Science and Operations Research. Kluwer, 1996. p. 1-75. PMid:8842811.

GLOVER, F. Multi-start and strategic oscillation methods - Principles to exploit adaptive memory. In: LAGUNA, M.; GONZÁLES-VELARDE, J. L. (Eds.). Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research. Kluwer, 2000. p. 1-24. PMid:10757191. http://dx.doi.org/10.1007/978-1-4615-4567-5_1

GLOVER, F.; LAGUNA, M. Tabu Search. Kluwer, 1997. http://dx.doi.org/10.1007/978-1-4615-6089-0

GLOVER, F.; LAGUNA, M.; MARTÍ, R. Fundamentals of scatter search and path relinking. Control and Cybernetics, v. 39, p. 653-684, 2000.

HENNIG, W. Phylogenetic systematics. Urbana: University of Illinois Press, 1966.

KITCHING, I. J. et al. Cladistics: The theory and practice of parsimony analysis. London: Oxford University Press, 1998.

LAGUNA, M.; MARTÍ, R. GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS Journal on Computing, v. 11, p. 44-52, 1999. http://dx.doi.org/10.1287/ijoc.11.1.44

LOURENÇO,H. R.; MARTIN, O.; STUETZLE, T. Iterated local search. In: GLOVER, F.; KOCHENBERGER, G. (Eds.). Handbook of Metaheuristics. Norwell: Kluwer Academic Publishers, 2002. chapt. 7, p. 321-353.

LUCKOW, M.; PIMENTEL, R. A. An empirical comparison of numerical Wagner computer programs. Cladistics, v. 1, p. 47-66, 1985. http://dx.doi.org/10.1111/j.1096-0031.1985.tb00410.x

MAURI, G. R.; LORENA, L. A. N. Uma nova abordagem para o problema dial-a-ride. Produção, v. 19, n. 1, p. 41-54, 2009. http://dx.doi.org/10.1590/S0103-65132009000100004

NERI, F.; COTTA, C.; MOSCATO, P. Handbook of Memetic Algorithms. Springer, 2012. v. 379. (Series: Studies in Computational Intelligence).

PENNY, D.; FOULDS, L. R.; HENDY, M. D. Testing the theory of evolution by comparing phylogenetic trees constructed from five different protein sequences. Nature, v. 247, p. 197-200, 1982. http://dx.doi.org/10.1038/297197a0

PLATNICK, N. I. An empirical comparison of microcomputer parsimony programs. Cladistics, v. 3, p. 121-144, 1987. http://dx.doi.org/10.1111/j.1096-0031.1987.tb00502.x

PLATNICK, N. I. An empirical comparison of microcomputer parsimony programs II. Cladistics, v. 5, p. 145-161, 1989. http://dx.doi.org/10.1111/j.1096-0031.1989.tb00561.x

RESENDE, M. G. C.; RIBEIRO, C. C. Greedy randomized adaptive search procedures. In: GLOVER, F.; KOCHENBERGER, G. (Eds.). Handbook of Metaheuristics. Kluwer, 2003.

RESENDE, M. G. C.; RIBEIRO, C. C. GRASP with path-relinking: Recent advances and applications. In: IBARAKI, T.; NONOBE, K.; YAGIURA, M. (Eds.). Metaheuristics: Progress as Real Problem Solvers. Springer, 2005. p. 29-63. http://dx.doi.org/10.1007/0-387-25383-1_2

RIBEIRO, C. C.; RESENDE, M. G. C. Path-relinking intensification methods for stochastic local search algorithms. Journal of Heuristics, v. 18, p. 193-214, 2012. http://dx.doi.org/10.1007/s10732-011-9167-1

RIBEIRO, C. C.; VIANNA, D. S. A hybrid genetic algorithm for the phylogeny problem using path-relinking as a progressive crossover strategy. International Transactions in Operational Research, v. 16, p. 641-657, 2009. http://dx.doi.org/10.1111/j.1475-3995.2009.00699.x

RIBEIRO, C. C.; VIANNA, D. S. A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure. International Transactions in Operational Research, v. 12, p. 325-338, 2005. http://dx.doi.org/10.1111/j.1475-3995.2005.498_1.x

SCHRAGE, L. A more portable FORTRAN random number generator. ACM Transactions on Mathematical Software, v. 5, p. 132-138, 1979. http://dx.doi.org/10.1145/355826.355828

SOBER, E. Parsimony, likelihood and the principle of the common cause. Philosophy of Science, v. 54, p. 465-469, 1987. http://dx.doi.org/10.1086/289394

SWOFFORD, D. L. Wagner procedure program. Champaign: Illinois Natural History Survey, 1982. PMid:20372399.

SWOFFORD, D. L.; OLSEN, G. Phylogeny reconstruction. In: HILLIS, D. M.; MORITZ, C. (Eds.). Molecular Systematics. Sinauer, 1990. p. 411-501.

SWOFFORD, D. L. et al. Phylogeny inference. In: HILLIS, D. M.; MORITZ, C.; MABLE, B. K. (Eds.). Molecular Systematics. 2nd ed. Sinauer, 1996. p. 407-514.

VIANNA, D. S. et al. Parallel strategies for a multi-criteria GRASP algorithm. Produção, v. 17, p. 1-12, 2007. http://dx.doi.org/10.1590/S0103-65132007000100006
5883a4467f8c9da00c8b486c production Articles
Links & Downloads

Production

Share this page
Page Sections