research-article

Finding consensus trees by evolutionary, variable neighborhood search, and hybrid algorithms

Authors:

Sandro Pirkwieser,

Günther R. RaidlAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 323 - 330

https://doi.org/10.1145/1389095.1389152

Published: 12 July 2008 Publication History

Abstract

The consensus tree problem arises in the domain of phylogenetics and seeks to find for a given collection of trees a single tree best representing it. Usually, such a tree collection is obtained by biologists for a given taxa set either via different phylogenetic inference methods or multiple applications of a non-deterministic procedure. There exist various consensus methods which often have the drawback of being very strict, limiting the resulting consensus tree in terms of its resolution and/or precision. A reason for this typically is the coarse granularity of the tree metric used. To find fully resolved (binary) consensus trees of high quality, we consider the fine-grained TreeRank similarity measure and extend a previously presented evolutionary algorithm (EA) to a memetic algorithm (MA) by including different variants of local search using neighborhoods based on moves of single taxa as well as subtrees. Furthermore, we propose a variable neighborhood search (VNS) with an embedded variable neighborhood descent (VND) based on the same neighborhood structures. Finally sequential and intertwined combinations of the EA and MA with the VNS/VND are investigated. We give results on real and artificially generated data indicating in particular the benefits of the hybrid methods.

References

[1]

E. N. Adams. Consensus techniques and the comparison of taxonomic trees. Systematic Zoology, 21(4):390--397, 1972.

[2]

A. A. Andreatta and C. C. Ribeiro. Heuristics for the phylogeny problem. Journal of Heuristics, 8:429--447, 2002.

Digital Library

[3]

D. Bryant. A classification of consensus methods for phylogenies. In M. Janowitz et al., editors, Bioconsensus, DIMACS, pages 163--184. AMS, 2003.

[4]

C. Cotta. On the application of evolutionary algorithms to the consensus tree problem. In J. Gottlieb and G. Raidl, editors, Evolutionary Computation in Combinatorial Optimization, volume 3248 of LNCS, pages 58--67. Springer, 2005.

Digital Library

[5]

C. Cotta. Scatter search with path relinking for phylogenetic inference. European Journal of Operational Research, 169(2):520--532, 2006.

[6]

C. Cotta and P. Moscato. Inferring phylogenetic trees using evolutionary algorithms. In J. Merelo et al., editors, Parallel Problem Solving From Nature VII, volume 2439 of LNCS, pages 720--729. Springer, 2002.

Digital Library

[7]

C. Cotta and P. Moscato. A memetic-aided approach to hierarchical clustering from distance matrices: Application to gene expression clustering and phylogeny. BioSystems, 72(1--2):75--97, 2003.

[8]

M. El-Abd and M. Kamel. A taxonomy of cooperative search algorithms. In M. J. Blesa et al., editors, Proceedings of Hybrid Metaheuristics, Second International Workshop, volume 3636 of LNCS, pages 32--41. Springer, 2005.

Digital Library

[9]

J. Felsenstein. PHYLIP (Phylogeny Inference Package) version 3.6, 2005. Distributed by the author. Department of Genome Sciences, University of Washington, Seattle.

[10]

G. Fogel. Evolutionary computation for the inference of natural evolutionary histories. IEEE Connections, 3(1):11--14, 2005.

[11]

A. Goeffon, J.-M. Richer, and J.-K. Hao. Progressive tree neighborhood applied to the maximum parsimony problem. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(1):136--145, 2008.

Digital Library

[12]

P. Hansen and N. Mladenovic. Variable neighborhood search. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 145--184. Kluwer Academic Publishers, 2003.

[13]

S. Holmes. Phylogenies: An overview. In M. Halloran and S. Geisser, editors, Statistics and Genetics, pages 81--119. Springer, 1999.

[14]

A. K. Jain, M. N. Murty, and P. J. Flynn. Data Clustering: A Review. ACM Computing Surveys, 31(3):264--323, 1999.

Digital Library

[15]

J. Kim and T. Warnow. Tutorial on phylogenetic tree estimation. In T. Lengauer et al., editors, Proceedings of the 7th International Conference on Intelligent Systems for Molecular Biology, pages 196--205. AAAI Press, 1999.

[16]

A. Moilanen. Searching for most parsimonious trees with simulated evolutionary optimization. Cladistics, 15(1):39--50, 1999.

[17]

P. Moscato and C. Cotta. A gentle introduction to memetic algorithms. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, pages 105--144. Kluwer Academic Publishers, 2003.

[18]

G. R. Raidl. A unified view on hybrid metaheuristics. In F. Almeida et al., editors, Proceedings of Hybrid Metaheuristics, Third International Workshop, volume 4030 of LNCS, pages 1--12. Springer, 2006.

Digital Library

[19]

C. C. Ribeiro and D. S. Vianna. A GRASP/VND heuristic for the phylogeny problem using a new neighborhood structure. International Transactions in Operational Research, 12:325--338, 2005.

[20]

L. Sheneman and J. A. Foster. Estimating the destructiveness of crossover on binary tree representations. In Proceedings of the 8th Conference on Genetic and Evolutionary Computation, pages 1427--1428. ACM Press, 2006.

Digital Library

[21]

R. R. Sokal and C. D. Michener. A statistical method for evaluating systematic relationships. University of Kansas Science Bulletin, 38:1409--1438, 1958.

[22]

Y. S. Song. On the combinatorics of rooted binary phylogenetic trees. Annals of Combinatorics, 7:365--379, 2003.

[23]

J. T. L. Wang, H. Shan, D. Shasha, and W. H. Piel. TreeRank: a similarity measure for nearest neighbor searching in phylogenetic databases. In Proceedings of the 15th International Conference on Scientific and Statistical Database Management, pages 171--180. IEEE Press, 2003.

Digital Library

Cited By

Villalobos-Cid MDorn MLigabue-Braun RInostroza-Ponta M(2019)A Memetic Algorithm Based on an NSGA-II Scheme for Phylogenetic Tree InferenceIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.288388823:5(776-787)Online publication date: Oct-2019
https://doi.org/10.1109/TEVC.2018.2883888
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6
Show More Cited By

Index Terms

Finding consensus trees by evolutionary, variable neighborhood search, and hybrid algorithms

Recommendations

Variable neighborhood search for the degree-constrained minimum spanning tree problem
Special issue: Third ALIO-EURO meeting on applied combinatorial optimization

Given an undirected graph with weights associated with its edges, the degree-constrained minimum spanning tree problem consists in finding a minimum spanning tree of the given graph, subject to constraints on node degrees. We propose a variable ...
Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the cost constrained minimum label spanning tree (CCMLST) problem is to find a spanning tree that uses the ...
Improved algorithms for constructing consensus trees
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

A consensus tree is a single phylogenetic tree that summarizes the branching structure in a given set of conflicting phylogenetic trees. Many different types of consensus trees have been proposed in the literature; three of the most well-known and ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
200
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Villalobos-Cid MDorn MLigabue-Braun RInostroza-Ponta M(2019)A Memetic Algorithm Based on an NSGA-II Scheme for Phylogenetic Tree InferenceIEEE Transactions on Evolutionary Computation10.1109/TEVC.2018.288388823:5(776-787)Online publication date: Oct-2019
https://doi.org/10.1109/TEVC.2018.2883888
Moscato PBerretta RCotta CCochran JCox LKeskinocak PKharoufeh JSmith J(2011)Memetic AlgorithmsWiley Encyclopedia of Operations Research and Management Science10.1002/9780470400531.eorms0515Online publication date: 14-Jan-2011
https://doi.org/10.1002/9780470400531.eorms0515
Moscato PCotta C(2010)A Modern Introduction to Memetic AlgorithmsHandbook of Metaheuristics10.1007/978-1-4419-1665-5_6(141-183)Online publication date: 12-Aug-2010
https://doi.org/10.1007/978-1-4419-1665-5_6
Goëffon ARicher JHao J(2010)Heuristic Methods for Phylogenetic Reconstruction with Maximum ParsimonyAlgorithms in Computational Molecular Biology10.1002/9780470892107.ch26(579-597)Online publication date: 23-Dec-2010
https://doi.org/10.1002/9780470892107.ch26

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten