CHAPTER 33

ADVANCES IN GENOME REARRANGEMENT ALGORITHMS

Masud Hasan and M. Sohel Rahman

33.1 INTRODUCTION

One of the goals of the scientists is to explain better the evolutionary history of a set of species. Interestingly although the organizations of the molecules of different species differ dramatically, the content of the DNA molecules from one species to another are believed to be often similar. Genome rearrangements refer to the mutations that affect this organization. Now, the role of computer scientists (or bioinformaticians), in this regard, lies basically in the efficient formulation of the evolutionary events to a combinatorial problem and then to provide an efficient solution for it. More specifically, a computer scientist would use mathematical model and combinatorial tools to reconstruct rearrangement scenarios to explain better the evolutionary history of a set of species.

Now, every study of genome rearrangement involves solving a combinatorial problem of finding a series of rearrangements that transform a genome into another. In the late 1980s, Palmer and Herbon [70] found that the number of such operations needed to transform the gene order of one genome into the other could be used as a measure of the evolutionary distance between two species. The classic examples of cabbage transforming into a turnip (Figure 33.1) and/or a mouse transforming into a human (Figure 33.2) are cited in almost all textbooks related to bioinformatics. Notably, in the latter example, ...

Get Algorithms in Computational Molecular Biology: Techniques, Approaches and Applications now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.