ICTACT Journal on Soft Computing

Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Enhanced Bio-Inspired Algorithm for Constructing Phylogenetic Tree


Affiliations
1 Department of Computer Applications, National Institute of Technology, Tiruchirappalli, India
     

   Subscribe/Renew Journal


This paper illustrates an enhanced algorithm based on one of the swarm intelligence techniques for constructing the Phylogenetic tree (PT), which is used to study the relationship between species. The main scheme is to formulate a PT, an NP- complete problem through an evolutionary algorithm called Artificial Bee Colony (ABC). The tradeoff between the accuracy and the computational time taken for constructing the tree makes way for new variants of algorithms. A new variant of ABC algorithm is proposed to promote the convergence rate of general ABC algorithm through recommending a new formula for searching solution. In addition, a searching step has been included so that it constructs the tree faster with a nearly optimal solution. Experimental results are compared with the ABC algorithm, Genetic Algorithm and the state-of-the-art techniques like unweighted pair group method using arithmetic mean, Neighbour-joining and Relaxed Neighbor Joining. For results discussion, we used one of the standard dataset Treesilla. The results show that the Enhanced ABC (EABC) algorithm converges faster than others. The claim is supported by a distance metric called the Robinson-Foulds distance that finds the dissimilarity of the PT, constructed by different algorithms.

Keywords

Phylogenetic Trees, Artificial Bee Colony Algorithm, Edit Distance, Converges Faster, Genetic Algorithm.
Subscription Login to verify subscription
User
Notifications
Font Size

  • Daniel H. Huson, Vincent Moulton and Mike Steel, “Special Section: Phylogenetics”, IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 6, No. 1, pp. 4-6, 2009

  • Savarimuthu Ignacimuthu, “Basic Bioinformatics”, Alpha Science International Ltd., 2005.

  • J. Kennedy and R. Eberhart, “Particle swarm optimization,” Proceedings of IEEE International Conference on Neural Networks, Vol. 4, pp. 1942-1948, 1995.

  • Daniel H. Huson, Regula Rupp and Celine Scornavacca, “Phylogenetic Networks: Concepts, Algorithms and Applications”, Cambridge University Press, 2010.

  • Dervis Karaboga, “An Idea based on Honey Bee Swarm for Numerical Optimization”, Technical report-TR06, Computer Engineering Department, Erciyes University, 2005.

  • Anabel Martínez-Vargas and Ángel G. Andrade, “Comparing particle swarm optimization variants for a cognitive radio network”, Applied Soft Computing, Vol. 13, No. 2, pp. 1222-1234, 2013.

  • Walter M. Fitch and Emanuel Margoliash, “Construction of phylogenetic trees”, Science, Vol. 155, No. 3760, pp: 279-284, 1967.

  • Peter H.A. Sneath and Robert R. Sokal, “Numerical Taxonomy. The Principles and Practice of Numerical Classification”, W. H. Freeman & Co Ltd, 1973.

  • Naruya Saitou and Masatoshi Nei, “The neighbor-joining method: a new method for reconstructing phylogenetic tree”, Molecular Biology and Evolution, Vol. 4, No. 4, pp. 406-425, 1987.

  • Ando, Shin and Hitoshi Iba, “Ant algorithm for construction of evolutionary tree”, Proceedings of the World on Congress on Computational Intelligence, Vol. 2, pp. 1552-1557, 2002.

  • M. Kumnorkaew, K. Ku and P. Ruenglertpanyakul, “Application of ant colony optimization to evolutionary tree construction”, Proceedings of 15th Annual Meeting of the Thai Society for Biotechnology, 2004.

  • Hui-Ying Lv, Wen-Gang Zhou and Chun-Guang Zhou, “A discrete particle swarm optimization algorithm for phylogenetic tree reconstruction”, Proceedings of International Conference on Machine Learning and Cybernetics, Vol. 4, pp. 2650-2654, 2004.

  • Mauricio Perretto and Heitor Silvério Lopes, “Reconstruction of phylogenetic trees using the ant colony optimization paradigm”, Genetics and Molecular Research, Vol. 4, No. 3, pp. 581-589, 2005.

  • S June Oh, Je-Gun Joung, Jeong-Ho Chang and Byoung-Tak Zhang, “Construction of phylogenetic trees by kernel-based comparative analysis of metabolic networks”, BMC Bioinformatics, Vol. 7, No. 1, 2006.

  • Jason Evans, Luke Sheneman, and James Foster, “Relaxed neighbor joining: a fast distance-based phylogenetic tree construction method”, Journal of Molecular Evolution, Vol. 62, No. 6, pp. 785-792, 2006.

  • Ling Qin, Yixin Chen, Yi Pan and Ling Chen, “A novel approach to phylogenetic tree construction using stochastic optimization and clustering”, BMC Bioinformatics, Vol. 7, 2006.

  • Priyank Raj Katariya and Sathish S. Vadhiyar, “Phylogenetic predictions on grids”, Proceedings of IEEE 8th International Conference on E-Science, pp. 58-65, 2009.

  • Pankaj Bhambri and O.P. Gupta, “Development of phylogenetic tree based on Kimura's Method”, Proceedings of IEEE International Conference on Parallel Distributed and Grid Computing, pp. 721-723. 2012.

  • Phylogenetic Tree: Example, Available at: http://science.kennesaw.edu/~jdirnber/Bio2108/Lecture/LecPhylogeny/LecPhylogeny.html

  • Xin-She Yang, “Engineering optimizations via nature-inspired virtual bee algorithms”, Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach, pp. 317-323, Vol. 3562, 2005.

  • Dervis Karaboga and Bahriye Akay, “A comparative study of artificial bee colony algorithm”, Applied Mathematics and Computation, Vol. 214, No. 1, pp. 108-132, 2009.

  • R. Srinivasa Rao, S. V. L. Narasimham and M. Ramalingaraju, “Optimization of distribution network configuration for loss reduction using artificial bee colony algorithm”, International Journal of Electrical Power and Energy Systems Engineering, Vol. 1, No. 2, pp. 116-122, 2008.

  • Dervis Karaboga and Bahriye Basturk, “An artificial bee colony (ABC) algorithm for numeric function optimization”, IEEE Swarm Intelligence Symposium, pp. 12-14. 2006.

  • Karaboga, Dervis, and Bahriye Basturk, “A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm”, Journal of global optimization, Vol. 39, No. 3, pp: 459-471, 2007.

  • John H. Holland, “Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence”, U Michigan Press, 1975.

  • P. Larranaga, C.M.H. Kuijpers, R.H. Murga, I. Inza and S. Dizdarevic, “Genetic algorithms for the travelling salesman problem: A review of representations and operators”, Artificial Intelligence Review, Vol. 13, No. 2, pp. 129-170, 1999.

  • Gusfield, Dan, “Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology”, Cambridge university press, 1997.

  • p53Dataset: Available at: http://www.bioinformatics.org/p53/nucleotide.html

  • Dataset: Treezilla, Available at: http://bioinformatics.hungry.com/clearcut/treezilla.fasta

  • Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara and Gabriel Valiente, “Faster computation of the robinson-foulds distance between phylogenetic networks”, Information Sciences, Vol. 197, pp. 77-90, 2012.


Abstract Views: 228

PDF Views: 2




  • Enhanced Bio-Inspired Algorithm for Constructing Phylogenetic Tree

Abstract Views: 228  |  PDF Views: 2

Authors

J. Jayapriya
Department of Computer Applications, National Institute of Technology, Tiruchirappalli, India
Michael Arock
Department of Computer Applications, National Institute of Technology, Tiruchirappalli, India

Abstract


This paper illustrates an enhanced algorithm based on one of the swarm intelligence techniques for constructing the Phylogenetic tree (PT), which is used to study the relationship between species. The main scheme is to formulate a PT, an NP- complete problem through an evolutionary algorithm called Artificial Bee Colony (ABC). The tradeoff between the accuracy and the computational time taken for constructing the tree makes way for new variants of algorithms. A new variant of ABC algorithm is proposed to promote the convergence rate of general ABC algorithm through recommending a new formula for searching solution. In addition, a searching step has been included so that it constructs the tree faster with a nearly optimal solution. Experimental results are compared with the ABC algorithm, Genetic Algorithm and the state-of-the-art techniques like unweighted pair group method using arithmetic mean, Neighbour-joining and Relaxed Neighbor Joining. For results discussion, we used one of the standard dataset Treesilla. The results show that the Enhanced ABC (EABC) algorithm converges faster than others. The claim is supported by a distance metric called the Robinson-Foulds distance that finds the dissimilarity of the PT, constructed by different algorithms.

Keywords


Phylogenetic Trees, Artificial Bee Colony Algorithm, Edit Distance, Converges Faster, Genetic Algorithm.

References