Mathematical problems in comparative genomics

Abstract

In this thesis I look at several fundamental mathematical problems in the area of comparative genomics. To understand the probabilistic behaviors of genomic distances and to devise statistical tests to see whether there is significant evolutionary signal remaining in the gene orders, I derive the probability distributions for DCJ distance, reversal distance and breakpoint distance. To utilize these validated evolutionary signals in recovering the phylogeny of species, I develop a graph decomposition theory to effectively reduce the size of the median problem, which lies at the heart of the rearrangement based phylogeny problem and has been proven NP-hard. My decomposition theory enables recursive reductions of the size of the problem by discovering adequate subgraphs in the multiple breakpoint graphs which are the graphic representation of the median problems. The results on simulated data with varying parameters show the power of the theory and the effectiveness of the corresponding algorithm--- ASMedian. With various possible improvements, this theory should lead to practical methods applicable to most biology instances.