Title 
Sorting signed permutations by short operations


Published in 
Algorithms for Molecular Biology, March 2015

DOI  10.1186/s130150150040x 
Pubmed ID  
Authors 
Gustavo Rodrigues Galvão, Orlando Lee, Zanoni Dias 
Abstract 
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 wellstudied 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. 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 polynomialtime solutions for problems (i) and (iii), a 5approximation for problem (ii), and a 3approximation for problem (iv). Moreover, we show that the expected approximation ratio of the 5approximation 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 3approximation algorithm is tight. 
Twitter Demographics
Geographical breakdown
Country  Count  As % 

Unknown  1  100% 
Demographic breakdown
Type  Count  As % 

Members of the public  1  100% 
Mendeley readers
Geographical breakdown
Country  Count  As % 

Unknown  6  100% 
Demographic breakdown
Readers by professional status  Count  As % 

Researcher  4  67% 
Student > Ph. D. Student  2  33% 
Readers by discipline  Count  As % 

Biochemistry, Genetics and Molecular Biology  3  50% 
Computer Science  2  33% 
Mathematics  1  17% 