Genome rearrangement algorithms
FacultiesFakultät für Ingenieurwissenschaften und Informatik
LicenseStandard (Fassung vom 01.10.2008)
With the increasing amount of sequenced genomes, a comparison of species based on these data becomes more and more interesting. In contrast to the classical approach, where only point mutations were considered, genome rearrangement problems ignore small mutations and only consider large-scale mutations that change the gene order on the chromosomes. This makes these problems a powerful tool when studying organisms that have diverged millions of years ago, or very fast evolving genomes, like those of cancerous cells. The major results contained in this thesis are as follows: - We provide a linear time transformation from an arbitrary permutation into its equivalent simple permutation, and an O(n log n) time back-transformation. Transformations like these were used in several sorting-by-reversals algorithms, and can give new insight into other genome rearrangement problems. - We prove the NP-completeness of the transposition median problem. As a direct consequence, also the reversal and transposition median problem is NP-complete if both operations are weighted equally. - We provide an exact branch and bound algorithm for the transposition median problem and the weighted reversal and transposition median problem which is fast enough to be used in practice. As a byproduct, we improve Christie´s exact algorithm for sorting by transpositions, and extend it to sorting by weighted reversals and transpositions. - We introduce a new pairwise distance measure which also considers operations that change the genome content, namely tandem duplications and deletions. We develop a lower bound for this distance and a greedy algorithm based on this lower bound. We provide two versions of this algorithm, one for unichromosomal circular genomes and one for multichromosomal linear genomes.
Subject HeadingsGenomik [GND]