| Abstrakt: | Genome rearrangements are large scale mutations, which change the order and orientation of genes in genomes. Reconstruction of ancestral gene orders on a phylogeny is known as the small phylogeny problem. On input, we have a phylogenetic tree, which is a binary tree describing the evolutionary history, as well as gene orders in present day species. The task is to reconstruct the gene orders of ancestors, while minimizing the overall number of rearrangement operations that had to occur during the evolution. The small phylogeny problem is NP-hard for most genome rearrangement models. A universal heuristic method (PIVO) was developed by Kováč et al. for solving the small phylogeny problem using an iterative local optimization procedure. We created a new algorithm, called PIVO2, which improves the original PIVO algorithm in various areas. These include improved initialization, candidate generation, and candidate selection. The PIVO2 algorithm contains several added optional extensions. In PIVO2, we also improved the speed of the original PIVO algorithm by creating a new and more efficient method for genome distance calculation. In this thesis, we also present practical experiments and comparisons of the original PIVO and the PIVO2 algorithms. The experiments show that the PIVO2 algorithm is indeed better than the original PIVO algorithm in finding evolutionary histories with lower score. Moreover, to find a history with a good score, the PIVO2 algorithm requires a significantly lower number of runs. The experiments also confirm that the new method of genome distance calculation really increases the computational speed.
|
|---|