Problems of sorting permutations by FragmentationWeighted operations
Full text  
Author(s): 
Total Authors: 3

Affiliation:  ^{[1]} Univ Estadual Campinas, Inst Comp, BR13083852 Campinas, SP  Brazil
Total Affiliations: 1

Document type:  Journal article 
Source:  Algorithms for Molecular Biology; v. 10, MAR 25 2015. 
Web of Science Citations:  8 
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 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. 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 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. (AU)  
FAPESP's process:  14/047186  Algorithms for rearrangement sorting problem 
Grantee:  Gustavo Rodrigues Galvão 
Support type:  Scholarships in Brazil  Doctorate 
FAPESP's process:  13/082937  CCES  Center for Computational Engineering and Sciences 
Grantee:  Munir Salomao Skaf 
Support type:  Research Grants  Research, Innovation and Dissemination Centers  RIDC 