Genome rearrangement algorithms [Elektronische Ressource] / vorgelegt von Martin Bader

Universit at UlmInstitut fur Theoretische InformatikLeiter: Prof. Dr. Uwe Sch oningGENOMEREARRANGEMENTALGORITHMSDISSERTATIONzur Erlangung des Doktorgrades Dr.rer.nat.der Fakult at fur Ingenieurwissenschaften und Informatik derUniversit at Ulmvorgelegt vonMartin Baderaus Friedrichshafen2011Amtierender Dekan: Prof. Dr. Klaus DietmayerGutachter: Prof. Dr. Enno OhlebuschProf. Dr. Jacobo Tor anProf. Dr. Jens StoyeTag der Promotion: 6.5.2011SummaryWith the increasing amount of sequenced genomes, a comparison of species based onthese data becomes more and more interesting. In contrast to the classical approach,where only point mutations were considered, genome rearrangement problems ignoresmall mutations and only consider large-scale mutations that change the gene order onthe chromosomes. This makes these problems a powerful tool when studying organismsthat have diverged millions of years ago, or very fast evolving genomes, like those ofcancerous cells.A large variety of problems arises from genome rearrangements, like the calculation ofevolutionary distances, the reconstruction of evolutionary events and the gene order ofhypothetical ancestors, or even the reconstruction of whole phylogenetic trees. Dueto the high complexity of most of these problems, the algorithms are based on highlysimpli ed models of the reality. For example, most consider only a singletype or a small set of evolutionary events.