title: Sorting signed permutations by short operations.
abstract: BACKGROUND
  During evolution, global mutations may alter the order and the orientation of the genes in a genome. Such mutations are referred to as rearrangement events, or simply operations. In unichromosomal genomes, the most common operations are reversals, which are responsible for reversing the order and orientation of a sequence of genes, and transpositions, which are responsible for switching the location of two contiguous portions of a genome. The problem of computing the minimum sequence of operations that transforms one genome into another - which is equivalent to the problem of sorting a permutation into the identity permutation - is a well-studied problem that finds application in comparative genomics. There are a number of works concerning this problem in the literature, but they generally do not take into account the length of the operations (i.e. the number of genes affected by the operations). Since it has been observed that short operations are prevalent in the evolution of some species, algorithms that efficiently solve this problem in the special case of short operations are of interest.
  
  
  RESULTS
  In this paper, we investigate the problem of sorting a signed permutation by short operations. More precisely, we study four flavors of this problem: (i) the problem of sorting a signed permutation by reversals of length at most 2; (ii) the problem of sorting a signed permutation by reversals of length at most 3; (iii) the problem of sorting a signed permutation by reversals and transpositions of length at most 2; and (iv) the problem of sorting a signed permutation by reversals and transpositions of length at most 3. We present polynomial-time solutions for problems (i) and (iii), a 5-approximation for problem (ii), and a 3-approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5-approximation algorithm is not greater than 3 for random signed permutations with more than 12 elements. Finally, we present experimental results that show that the approximation ratios of the approximation algorithms cannot be smaller than 3. In particular, this means that the approximation ratio of the 3-approximation algorithm is tight.
authors.affiliation: Institute of Computing, University of Campinas, Av. Albert Einstein, 1251, Campinas, 13083-852 Brazil.
authors.forename: Gustavo Rodrigues
authors.initials: GR
authors.lastname: Galvão
authors.affiliation: Institute of Computing, University of Campinas, Av. Albert Einstein, 1251, Campinas, 13083-852 Brazil.
authors.forename: Orlando
authors.initials: O
authors.lastname: Lee
authors.affiliation: Institute of Computing, University of Campinas, Av. Albert Einstein, 1251, Campinas, 13083-852 Brazil.
authors.forename: Zanoni
authors.initials: Z
authors.lastname: Dias
keywords: Genome rearrangement; Short reversals; Short transpositions
references.citation: Mol Biol Evol. 1987 Jul;4(4):406-25
references.pmid: 3447015
references.citation: J Math Biol. 2014 Jul;69(1):243-65
references.pmid: 23793228
references.citation: J Mol Evol. 2002 Jul;55(1):24-36
references.pmid: 12165840
references.citation: J Comput Biol. 2001;8(5):483-91
references.pmid: 11694179
references.citation: Nature. 2011 Oct 12;478(7370):506-10
references.pmid: 21993626
references.citation: IEEE/ACM Trans Comput Biol Bioinform. 2006 Oct-Dec;3(4):369-79
references.pmid: 17085846
references.citation: Bioinformatics. 2003;19 Suppl 1:i190-6
references.pmid: 12855457
references.citation: Genome Inform. 2002;13:103-11
references.pmid: 14571379
references.citation: J Comput Biol. 2003;10(5):775-89
references.pmid: 14633399
references.citation: Proc Natl Acad Sci U S A. 2000 Dec 19;97(26):14433-7
references.pmid: 11087826