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.
http://dx.doi.org/10.1590/S0103-65132013005000050
Production, vol.24, n3, p.664-674, 2014
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
Facebook
Google+
Twitter
LinkedIn
Mendeley
StumbleUpon
CiteULike
Reddit
Email