SORTING BY TRANSPOSITIONS

Sequence comparison in computational molecular biology is a powerful t ool for deriving evolutionary and functional relationships between gen es. However, classical alignment algorithms handle only local mutation s (i.e., insertions, deletions, and substitutions of nucleotides) and ignore global rearrangements (i.e., inversions and transpositions of l ong fragments). As a result, the applications of sequence alignment to analyze highly rearranged genomes (i.e., herpes viruses or plant mito chondrial DNA) are rather limited. The paper addresses the problem of genome comparison versus classical gene comparison and presents algori thms to analyze rearrangements in genomes evolving by transpositions. In the simplest form the problem corresponds to sorting by transpositi ons, i.e., sorting of an array using transpositions of arbitrary fragm ents. We derive lower bounds on transposition distance between permuta tions and present approximation algorithms for sorting by transpositio ns. The algorithms also imply a nontrivial upper bound on the transpos ition diameter of the symmetric group. Finally, we formulate two biolo gical problems in genome rearrangements and describe the first algorit hmic steps toward their solution.