Research On Genome Rearrangement Solution Space Sorting By Reversals And Deletions

Comparative Genomics is an important research branch in Bioinformatics. In this field, computing the evolve distance between two species, namely the genome rearrangement problem, is essential. The applications include reconstructing the evolutionary distance tree, exploring gene functions, and analyzing the principle of pathogenic disease. A genome is a set of chromosomes, while a chromosome which can be seen as a sequence of genes is genetic material. In signed genome, each gene is represented by an integer with the sign "+" or "-". The sign is used to indicate the direction of genes.Sorting genomes reveals the phenomenon of sequence order changing of genomes, which isabstracted to be some fundamental operations such as Reversal, Translocation, Transposition, tranreversal, Inserting, Deletion, Fission and Fussion in the genomes rearrangement problem.It was named sorting genomes by multiple-operation rearrangements when the rearrangement involves more than one operations. It seems more valueable because this problem is more general than sorting genomes by single-operation rearrangements. Reversal has been widely recognized as the most common operation in genome rearrangement. In many studies, scientistshave found that there are gene segment insertion and deletion in genome rearrangement. Besides, much practice of molecular biologyneeds insertion and deletion operation in genome rearrangement.In this thesis, we first study all solution space sorting by reversal and introduce Braga’s algorithm framework. Then, we extend the classic genome model by adding deletionblock. Deletion block is used to contain temporal genes which will be removed by deletion operation. Deletion block may be present at different place in the permutation. We can keep a copy of the temporal gene at every place that the deletion block presents. For each copy, there exist reversal sequences recording how the copy of temporal gene presents in the place. Being objected of minimum operations, this thesis proposed an algorithm that computes the all solution space sorting by reversal and deletion under that condition that reversal distance is the minimum. Finally, we implement the algorithm in Java, conduct some experiments and anylize the results.