Research Of Genome Rearrangements Based On Common Intervals

The genetic material of organisms changes as they evolve. More and more researchers were concerned with large transformations at the genome level, as opposed to point mutations at the sequence level. The problem of sorting a signed permutation by reversals is inspired by genome rearrangements in computational molecular biology. Given two genomes represented as two signed permutations of the same elements, the problem consists in finding a most parsimonious scenario of sorting by reversals that transforms one genome into the other.Nowadays the reconstruction of evolution scenarios based on genome rearrangements has proven to be a powerful tool in understanding the evolution of close species, especially mammals. For example, in the last two years, several very interesting evolution scenarios have been proposed between the mouse and the human, and between the mouse and the newly sequenced Norway rat, using the MGR and GRIMM software. We are interested in scenarios that do not break combinatorial structures (that is the genome synteny blocks).Indeed, if two genomes share a common feature, it is likely that their common ancestor did too, which makes evolution scenarios that conserve this feature more interesting.In this dissertation, the combinatorial structures that we consider are common intervals of two permutations that represent two genomes. At first, we define the overlap graph and give the new construction of it, which are different from those of the HP theory. We obtain the same conclusion as S. Berard and A. bergeron proposed, when use the new description of the overlap graph. Based on the commuting scenario we give the definition of the non-commuting scenario, and give relative research about the transformation from the non-commuting scenario to the commuting scenario.However since commuting scenario is a class of special perfect scenario and a perfect scenario is not necessarily commuting, we also want to know if there exists perfect scenario or optimal perfect scenario in the evolution process. Based on the faster and simpler algorithm which was proposed by H. Kaplan, R. Shamir and R. E. Tarjan for sorting a signed permutation by reversals, we modify this algorithm to solve theproblem for conserving the common intervals. By contrasting common intervals with the reversals, we can decide if the reversals conserve the common intervals. Moreover, we also obtain a polynomial time algorithm to decide if a permutation can be sorted by an optimal perfect scenario. So the optimal perfect scenario problem of a permutation can be solved more efficiently to some extent by the algorithm we propose.