Abstract

Comparative Genomics: Multiple Genome Rearrangement and Efficient Algorithm Development

Multiple genome rearrangement by signed reversal is discussed: For a collection of genomes represented by signed permutations, reconstruct their evolutionary history by using signed reversals, i.e., find a tree with the given genomes as leaf nodes and assign signed permutations (i.e., ancestral genomes) to internal nodes such that the total reversal distance over all edges of the tree is minimized.

In this thesis, several efficient algorithms are developed to search the optimal ancestral genomes for the problem, including nearest path search algorithm, neighbor-perturbing algorithm, branch-and-bound algorithm, etc. Through theoretical approaches, computer simulations, and biological applications, they are showed to be more efficient than previous algorithms (e.g., grid search, MGR greedy split).