Combinatorial Algorithms Of Genome Rearrangements In Bioinformatics

Computational biology is the focus of research in the world today, results from which are influencing the study progress in many other fields like biological race evolution, cladistics, and the bio-pharmaceutical etc. More and more scientists, especially those experts in the field of biology, mathematics, computer science and chemistry, are interested in the progress of computational biology.In the late 1980's. Jeffrey Palmer and his colleagues discovered a remarkable pattern of evolutionary change in plant organelles. They mapped the mitochondrial genomes of cabbage and turnip, which are very closely related. To their surprise, these molecules, which are almost identical in gene content, differ dramatically in gene order. This discovery and many other studies in the last decade proved that genome rearrangement is a common mode of molecular evolution.A chromosome is a sequence of genes and does not have an orientation. A genome is a set of chromosomes. Clearly, a chromosome can be seen as an uni-chromosomal genome. The genes of a chromosome can be put on a line or a ring. The former is called linear and the latter is called circular. If the direction of genes in a chromosome are known, a sign of "+" or "-" will be added before each gene to indicate the direction. A chromosome (or genome) is called signed if the genes it contains are signed, and otherwise is called unsigned.Although genome rearrangement is a complicated process, there are several basic operations. In the process of mutation, there are three possible global rearrangement events: reversal, translocation and transposition. The evolutionary relationship between different species can be approximated by the genome rearrangements between different species. Given two genomes Π and Γ, and the set of available rearrangement...