title: Sorting by Cuts, Joins, and Whole Chromosome Duplications.
abstract: Genome rearrangement problems have been extensively studied due to their importance in biology. Most studied models assumed a single copy per gene. However, in reality, duplicated genes are common, most notably in cancer. In this study, we make a step toward handling duplicated genes by considering a model that allows the atomic operations of cut, join, and whole chromosome duplication. Given two linear genomes, [Formula: see text] with one copy per gene and [Formula: see text] with two copies per gene, we give a linear time algorithm for computing a shortest sequence of operations transforming [Formula: see text] into [Formula: see text] such that all intermediate genomes are linear. We also show that computing an optimal sequence with fewest duplications is NP-hard.
authors.affiliation: Blavatnik School of Computer Science, Tel Aviv University , Tel-Aviv, Israel .
authors.forename: Ron
authors.initials: R
authors.lastname: Zeira
authors.affiliation: Blavatnik School of Computer Science, Tel Aviv University , Tel-Aviv, Israel .
authors.forename: Ron
authors.initials: R
authors.lastname: Shamir
mesh_terms: D000465:Algorithms; D058674:Chromosome Duplication; D015321:Gene Rearrangement; D020131:Genes, Duplicate; D016678:Genome; D006801:Humans; D008957:Models, Genetic; D009369:Neoplasms / Q000235:genetics; D010944:Plants / Q000235:genetics
keywords: SCJ; computational genomics; genome rearrangements