Evolutionary Algorithms For Phylogenetic Tree Construction

At present, the difficult problem—phylogenetic tree construction becomes more and more important in bioinformatics. Most optimal tree construction problems are NP-Complete. The number of possible tree topologies increases exponentially with the number of the taxa under consideration. Due to its NP-hardness, researchers have made great efforts to find efficient algorithms to construct near optimal solutions in a reasonable time.Genetic algorithm and ant colony algorithm are two evolutionary algorithms for complicated problems in combinatorial optimization. A great deal of experimental results indicates that these two algorithms have excellent performance and can obtain satisfactory solution for combinatorial optimization problems in reasonable time. Therefore, we apply these two algorithms in phylogenetic tree construction.In this thesis, we propose four approaches based on these two evolutionary algorithms to resolve the phylogenetic tree construction problem.1. We present a genetic algorithm named GA-PTC for phylogenetic tree construction based on genetic algorithm. GA-PTC first encodes the possible tree topologies into the solution space of the problem, and then searches for the optimal tree in the searching space. To coding the solutions, we propose a suffix representation as the encoding strategy of genetic algorithm. To evaluate quality of the individual, we adopt a distance based fitness function to score solution, and select parts of individuals according to a selection strategy called roulette wheel where the select probability is proportional to the fitness value.2. We present three phylogenetic tree construction algorithms using ACO: (1) Phylogenetic tree construction method based on TSP (TSP-PTC). Given a set of species and their distance matrix, TSP-PTC first builds a weighed graph where each Hamilton Circuit represents a phylogenetic tree. Among the phylogenetic trees corresponding to all circle paths, the optimal tree with minimum fitness value is the one which is corresponding to the solution of TSP. Therefore, artificial ants can be used to search an optimal path in the weighed graph. Then, the optimal tree can be constructed by the optimal path and the distance matrix. (2) Phylogenetic tree construction method based on ant clustering (AC-PTC). In this method, the process of phylogenetic tree construction can be treated as clustering of the species according their distances. In the algorithm, species are represented by a complete graph. Distances between species are measured by pheromone left by ants traveling on the graph. The pheromone of the digraph is updated according to the number of ants passing through this edge. The algorithm constructs the phylogenetic tree recursively by omitting the edges with less pheromone intensities. Then the graph can be divided into two connected components. By modifying these two subgraphs, each of them can be further divided into two smaller subgraphs. The algorithm is a recursive procedure of bisecting the graph. Tracing the procedure of bisecting the graph, a phylogenetic tree can be constructed. (3) Phylogenetic tree construction method based on suffix representation (SR-PTC). In this phylogenetic tree construction algorithm, ants search in the collection containing species and the internal nodes, and construct a suffix representation sequence which corresponding to a phylogenetic tree. In this method, ants select different nodes with different probability and form a phylogenetic tree represented by suffix representation. Futhermore, the pheromone on each edge is updated according to the fitness value of the phylogenetic tree.Experimental results show that our ant colony algorithm based methods can obtain higher accuracy results, higher convergence speed than other similar methods.