Construction of Phylogenetic Trees from Amino Acid Sequences using a Genetic Algorithm

Hideo Matsuda (matsuda@ics.es.osaka-u.ac.jp)

Department of Information and Computer Sciences, Faculty of Engineering Science, Osaka University
1-3 Machikaneyama, Toyonaka, Osaka 560 Japan


Abstract

We have developed a novel algorithm to search for the maximum likelihood tree constructed from amino acid sequences. This algorithm is a variant of genetic algorithms which uses scores derived from the log-likelihood of trees computed by the maximum likelihood method. This algorithm is valuable since it may construct more likely tree from randomly generated trees by utilizing crossover and mutation operators. In a test of our algorithm on a data set of elongation factor-1 alpha sequences, we found that the performance of our algorithm is comparable to that of other tree-construction methods (UPGMA, the neighbor-joining and the maximum parsimony methods; and the maximum likelihood method with different search algorithms).