GENOME REARRANGEMENTS AND SORTING BY REVERSALS

Sequence comparison in molecular biology is in the beginning of a majo r paradigm shift-a shift from gene comparison based on local mutations (i.e., insertions, deletions, and substitutions of nucleotides) to ch romosome comparison based on global rearrangements (i.e., inversions a nd transpositions of fragments). The classical methods of sequence com parison do not work for global rearrangements, and little is known in computer science about the edit distance between sequences if global r earrangements are allowed. In the simplest form, the problem of gene r earrangements corresponds to sorting by reversals, i.e., sorting of an array using reversals of arbitrary fragments. Recently, Kececioglu an d Sankoff gave the first approximation algorithm for sorting by revers als with guaranteed error bound 2 and identified open problems related to chromosome rearrangements. One of these problems is Gollan's conje cture on the reversal diameter of the symmetric group. This paper prov es the conjecture. Further, the problem of expected reversal distance between two random permutations is investigated. The reversal distance between two random permutations is shown to be very close to the reve rsal diameter, thereby indicating that reversal distance provides a go od separation between related and nonrelated sequences in molecular ev olution studies. The gene rearrangement problem forces us to consider reversals of signed permutations, as the genes in DNA could be positiv ely or negatively oriented. An approximation algorithm for signed perm utation is presented, which provides a performance guarantee of 3/2 Fi nally, using the signed permutations approach, an approximation algori thm for sorting by reversals is described which achieves a performance guarantee of 7/4.