title: Rearrangement models and single-cut operations.
abstract: There have been many widely used genome rearrangement models, such as reversals, Hannenhalli-Pevzner (HP), and double-cut and join. Though each one can be precisely defined, the general notion of a model remains undefined. In this paper, we give a formal set-theoretic definition, which allows us to investigate and prove relationships between distances under various existing and new models. Among our results is that sorting in the HP model is equivalent to sorting in the reversal model when the initial and final genomes are linear uni-chromosomal. We also initiate the formal study of single-cut operations by giving a linear time algorithm for the distance problem under a new single-cut and join model.
authors.affiliation: Départment d'informatique, Université du Québec à Montréal, Montreal, QC, Canada.
authors.forename: Anne
authors.initials: A
authors.lastname: Bergeron
authors.forename: Paul
authors.initials: P
authors.lastname: Medvedev
authors.forename: Jens
authors.initials: J
authors.lastname: Stoye
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods; D015321:Gene Rearrangement; D016678:Genome; D006801:Humans; D008957:Models, Genetic; D010802:Phylogeny