An Ant Colony system for large-scale phylogenetic tree reconstruction

Issue title: Evolutionary computation in bioinformatics

Article type: Research Article

Authors: Lopes, Heitor S. | Perretto, Mauricio

Affiliations: Laboratório de Bioinformática/CPGEI, Universidade Tecnológica Federal do Paraná, UTFPR, Av. 7 de setembro, 3165, 80230-901 Curitiba (PR), Brazil

Note: [] Corresponding author. Tel.: +55 41 3310 4694; E-mail: hslopes@pesquisador.cnpq.br

Abstract: An important problem in Bioinformatics is the reconstruction of phylogenetic trees. A phylogenetic tree aims at unveiling the evolutionary relationship between several species. In this way, it is possible to know which species are more closely related to one another and which are more distantly related. Established methods for phylogeny work fine for small or moderate number of species, but they become unfeasible for large-scale phylogeny. This work proposes a methodology using the Ant Colony Optimization (ACO) paradigm for the problem. A phylogenetic tree is viewed as a fully-connected graph using a matrix of distances between species. We search for the shortest path in this graph, turning the problem to an instance of the well-known traveling salesman problem. After, we describe how to build a tree using the directed graph and the pheromone matrix obtained by the ACO. Two data sets were used to test the system. The first one was used to investigate the sensitivity of the control parameters and to define their default values. The second data set was used to analyze the scalability of the system for a large number of sequences. Results show that the proposed method is as good as or even better than the other conventional methods and very efficient for large-scale phylogeny.

Keywords: Bioinformatics, phylogenetic tree, Ant Colony Optimization

Journal: Journal of Intelligent & Fuzzy Systems, vol. 18, no. 6, pp. 575-583, 2007