Login Register Cart 0
Generic placeholder image

Current Bioinformatics

Editor-in-Chief

ISSN (Print): 1574-8936
ISSN (Online): 2212-392X

Back
Journal Home About Journal Editorial Board Journal Insight Current Issue Volumes/Issues
Subscribe
Research Article

Estimating Bifurcating Consensus Phylogenetic Trees Using Evolutionary Imperialist Competitive Algorithm

Author(s): Vageehe Nikkhah, Seyed M. Babamir* and Seyed S. Arab

Volume 14, Issue 8, 2019

Page: [728 - 739] Pages: 12

DOI: 10.2174/1574893614666190225145620

Price: $65

Abstract

Background: One of the important goals of phylogenetic studies is the estimation of species-level phylogeny. A phylogenetic tree is an evolutionary classification of different species of creatures. There are several methods to generate such trees, where each method may produce a number of different trees for the species. By choosing the same proteins of all species, it is possible that the topology and arrangement of trees would be different.

Objective: There are methods by which biologists summarize different phylogenetic trees to a tree, called consensus tree. A consensus method deals with the combination of gene trees to estimate a species tree. As the phylogenetic trees grow and their number is increased, estimating a consensus tree based on the species-level phylogenetic trees becomes a challenge.

Methods: The current study aims at using the Imperialist Competitive Algorithm (ICA) to estimate bifurcating consensus trees. Evolutionary algorithms like ICA are suitable to resolve problems with the large space of candidate solutions.

Results: The obtained consensus tree has more similarity to the native phylogenetic tree than related studies.

Conclusion: The proposed method enjoys mechanisms and policies that enable us more than other evolutionary algorithms in tuning the proposed algorithm. Thanks to these policies and the mechanisms, the algorithm enjoyed efficiently in obtaining the optimum consensus tree. The algorithm increased the possibility of selecting an optimum solution by imposing some changes in its parameters.

Keywords: Consensus tree, phylogenetic tree, species level, evolutionary algorithm, imperialist competitive algorithm, parameters.

« Previous Next »
Graphical Abstract

[1]
Huson DH, Rupp R, Scornavacca C. Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press 2010.
[2]
Wiley EO, Lieberman BS. Phylogenetics: Theory and practice of phylogenetic systematics. 2nd ed. Wiley 2011.
[3]
Adams EN. Consensus techniques and the comparison of taxonomic trees. Syst Zool 1972; 21(4): 390-7.
[4]
Atashpaz-Gargari E, Lucas C. Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress on Evolutionary Computation 2007; 4661-7.
[5]
Lucas C, Nasiri-Gheidari Z, Tootoonchian F. Application of an imperialist competitive algorithm to the design of a linear induction motor. Energy Convers Manage 2010; 51: 1407-11.
[6]
Bahrami H, Faez K, Abdechiri M. Imperialist competitive algorithm using chaos theory for optimization In Proceedings of the 12th International Conference on Computer Modelling and Simulation 2010; 98-103.
[7]
Wang G, Zhang YB, Chen JW. A novel algorithm to solve the vehicle routing problem with time windows: Imperialist competitive algorithm. Adv Inform Sci Service Sci 2011; 3(5): 108-16.
[8]
Hosseini S, Al-Khaled A. A survey on the Imperialist Competitive Algorithm metaheuristic: Implementation in engineering domain and directions for future research. Appl Soft Comput 2014; 24: 1078-94.
[9]
Yousefikhoshbakht M, Sedighpour M. New Imperialist Competitive Algorithm to solve the travelling salesman problem. Int J Comput Math 2013; 90(7): 1495-505.
[10]
van Iersel L, Kelk S, Stamoulis G, Stougie L, Boes O. On unrooted and root-uncertain variants of several well-known phylogenetic network problems. Algorithmica 2018; 80(11): 2993-3022.
[11]
Xiong J. Essential bioinformatics. Cambridge University Press 2006.
[12]
Nei M, Kumar S. Major methods for estimating phylogenetic trees. In: Barry G Hall Ed Molecular Evolution and Phylogenetics, Phylogenetic Trees. Oxford University Press 2000.
[13]
Bryant D. A classification of consensus methods for phylogenetics.DIMACS series in discrete mathematics and theoretical computer science 2003; 61: 163-84.
[14]
Lecointre G, Guyader HL. The tree of life: A phylogenetic classi-fication. Harvard University Press 2006.
[15]
Jansson J, Rajaby R, Shen C, Sung WK. Algorithms for the majority rule (+) consensus tree and the frequency difference consensus tree. IEEE/ACM Trans Comput Biol Bioinformatics 2018; 15(1): 15-26.
[16]
Jansson J, Shen C, Sung WK. Improved algorithms for constructing consensus trees. J Assoc Comput Mach 2016; 63(3): 28.
[17]
Janssona J, Lib Z. KinSungb W. On finding the Adams consensus tree. Information and Computation, Elsevier 2017; 256: 334-47.
[18]
Nelson G. Cladistic analysis and synthesis: principles and definitions, with a historical note on Adanson’s families des Plantes. Syst Biol 1979; 28(1): 1-21.
[19]
Carlos C. On the application of evolutionary algorithms to the consensus tree problem In Proceedings of European Conference on Evolutionary Computation in Combinatorial Optimization 2005; 58-67.
[20]
Cotta C, Moscato P. Inferring phylogenetic trees using evolutionary algorithms In: Proceedings of International Conference on Parallel Problem Solving from Nature In Merelo J, et al, Eds, Parallel problem solving from nature, LNCS Springer VII,. 2002; 2439: pp. 720-9.
[21]
Cotta C, Moscato P. A memetic-aided approach to hierarchical clustering from distance matrices: Application to gene expression clustering and phylogeny. Biosystems 2003; 72(1-2): 75-97.
[22]
Gallardo JE, Cotta C, Fernández AJ. Reconstructing phylogenies with Memetic algorithms and branch-and-bound, science Engineering and Biology Informatics, Analysis of Biological Data: A Soft Computing Approach. World Scientific 2007; pp. 59-84.
[23]
Pirkwieser S, Raidl GR. Finding consensus trees by evolutionary variable neighborhood search and hybrid algorithms Genetic and Evolutionary Computation Conference 2008; 323-0.
[24]
Tahiri N, Willems M, Makarenkov V. A new fast method for inferring multiple consensus trees using k-medoids. BMC Evol Biol 2018; 18(1): 48.
[25]
Wang JTL, Shan H, Shasha D, et al. TreeRank: A similarity measure for nearest neighbor searching in phylogenetic database In Proceedings of the 15th International Conference on Scientific and Statistical Database Management 2003; 1-10.
[26]
Cotta C, Moscato P. Inferring phylogenetic trees using evolutionary algorithms, parallel problem solving from nature In Proceedings of International Conference on Parallel Problem Solving from Nature Springer. 2002; 720-9.
[27]
Protein Data available at: https://www.ncbi.nlm.nih.gov/guide/
[28]
Bioinformatics Toolbox available at: http://www.mathworks.com/ products/bioinfo
[29]
Cardona G, Rosselló F, Valiente G. Extended Newick: it is time for a standard representation of phylogenetic networks. BMC Bioinformatics 2008; 9: 532.
[30]
Abdechiri M, Faez K, Bahrami H. Neural network learning based on chaotic imperialist competitive algorithm In Proceedings of the 2nd International Workshop on Intelligent Systems and Appli-cations IEEE. 2010.
[31]
Tabaszewski P, Górecki P, Eulenstein O. Phylogenetic consensus for exact median trees In Proceedings of the 9th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics 2018; 366-75.
[32]
Chen J, Guo M, Wang X, Liu B. A comprehensive review and comparison of different computational methods for protein remote homology detection. Brief Bioinform 2018; 9: 231-44.
[33]
Khaji E, Karami M, Garkani-Nejad Z. 3D protein structure prediction using Imperialist Competitive Algorithm and half sphere exposure prediction. J Theor Biol 2016; 391: 81-7.

Rights & Permissions Print Cite
Article Metrics
23
1
© 2024 Bentham Science Publishers | Privacy Policy