Computational Biology
@ Comenius University in Bratislava

Albert Herencsár. An improved algorithm for ancestral gene order reconstruction. Master thesis, Comenius University in Bratislava, 2014. Supervised by Broňa Brejová.

Download preprint: 14herencsarth.pdf, 984Kb

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX

Abstract:

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.