Sorting by reciprocal translocations via reversals theory.
The understanding of genome rearrangements is an important endeavor in comparative genomics. A major computational problem in this field is finding a shortest sequence of genome rearrangements that transforms, or sorts, one genome into another. In this paper we focus on sorting a multi-chromosomal genome by translocations. We reveal new relationships between this problem and the well studied problem of sorting by reversals. Based on these relationships, we develop two new algorithms for sorting by reciprocal translocations, which mimic known algorithms for sorting by reversals: a score-based method building on Bergeron's algorithm, and a recursive procedure similar to the Berman-Hannenhalli method. Though their proofs are more involved, our procedures for reciprocal translocations match the complexities of the original ones for reversals.
Ozery-Flato
Michal
M
School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel. ozery@post.tau.ac.il
Shamir
Ron
R
D000465:Algorithms; D002875:Chromosomes / Q000235:genetics*; D019295:Computational Biology; D016678:Genome; D017422:Sequence Analysis, DNA; D014178:Translocation, Genetic / Q000235:genetics*