↓ Skip to main content

Sorting signed permutations by short operations

Overview of attention for article published in Algorithms for Molecular Biology, March 2015
Altmetric Badge

Mentioned by

twitter
1 X user

Citations

dimensions_citation
13 Dimensions

Readers on

mendeley
6 Mendeley
You are seeing a free-to-access but limited selection of the activity Altmetric has collected about this research output. Click here to find out more.
Title
Sorting signed permutations by short operations
Published in
Algorithms for Molecular Biology, March 2015
DOI 10.1186/s13015-015-0040-x
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 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. 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.

X Demographics

X Demographics

The data shown below were collected from the profile of 1 X user who shared this research output. Click here to find out more about how the information was compiled.
Mendeley readers

Mendeley readers

The data shown below were compiled from readership statistics for 6 Mendeley readers of this research output. Click here to see the associated Mendeley record.

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 %
Computer Science 3 50%
Biochemistry, Genetics and Molecular Biology 2 33%
Mathematics 1 17%
Attention Score in Context

Attention Score in Context

This research output has an Altmetric Attention Score of 1. This is our high-level measure of the quality and quantity of online attention that it has received. This Attention Score, as well as the ranking and number of research outputs shown below, was calculated when the research output was last mentioned on 04 April 2015.
All research outputs
#20,273,512
of 22,805,349 outputs
Outputs from Algorithms for Molecular Biology
#233
of 264 outputs
Outputs of similar age
#222,930
of 263,364 outputs
Outputs of similar age from Algorithms for Molecular Biology
#6
of 8 outputs
Altmetric has tracked 22,805,349 research outputs across all sources so far. This one is in the 1st percentile – i.e., 1% of other outputs scored the same or lower than it.
So far Altmetric has tracked 264 research outputs from this source. They receive a mean Attention Score of 3.2. This one is in the 1st percentile – i.e., 1% of its peers scored the same or lower than it.
Older research outputs will score higher simply because they've had more time to accumulate mentions. To account for age we can compare this Altmetric Attention Score to the 263,364 tracked outputs that were published within six weeks on either side of this one in any source. This one is in the 1st percentile – i.e., 1% of its contemporaries scored the same or lower than it.
We're also able to compare this research output to 8 others from the same source and published within six weeks on either side of this one. This one has scored higher than 2 of them.