Genomų palyginimo algoritmų tyrimas

To understand evolution, and to discover how different species are related, gene order analysis is a useful tool. Problems in this area can usually be formulated in a combinatorial language. We regard genomes as signed, or unsigned permutations, and thus evolutionary operations like inversions (reversing the order of a segment of genes) are easy to describe combinatorially. A commonly studied problem is to determine the evolutionary distance between two species. This is estimated by several combinatorial distances between gene order permutations, for instance the inversion distance. The main objective of this work was to survey the existing algorithms for genome comparison and to present new approach for solving this problem. The work led to these results: - We have surveyed existing approaches of genome comparison, namely comparison by inversion distance in signed and unsigned cases. It appeared that sorting signed genomes by inversions is done in quadratic time, but sorting unsigned genomes by inversions is NP-hard. - We have proposed the method of how to apply heuristic algorithms for sorting unsigned genomes by inversions. - We have applied tabu search and genetic algorithm to solve the sorting unsigned genomes by inversions problem. - We have experimentally proven, that the worst case solutions to sorting unsigned genomes by inversions found by heuristics (tabu search and genetic algorithm) are better then ones expected from best known approximating algorithm used for... [to full text]