Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn a lower bound for sorting signed permutations by reversals
126
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Computing the reversal distances of signed permutations is an important topic in Bioinformatics. Recently, a new lower bound for the reversal distance was obtained via the plane permutation framework. This lower bound appears different from the existing lower bound obtained by Bafna and Pevzner through breakpoint graphs. In this paper, we prove that the two lower bounds are equal. Moreover, we confirm a related conjecture on skew-symmetric plane permutations, which can be restated as follows: let $p=(0,-1,-2,ldots -n,n,n-1,ldots 1)$ and let $$ tilde{s}=(0,a_1,a_2,ldots a_n,-a_n,-a_{n-1},ldots -a_1) $$ be any long cycle on the set ${-n,-n+1,ldots 0,1,ldots n}$. Then, $n$ and $a_n$ are always in the same cycle of the product $ptilde{s}$. Furthermore, we show the new lower bound via plane permutations can be interpreted as the topological genera of orientable surfaces associated to signed permutations.
rate research
Read More
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.
In this paper we present a topological framework for studying signed permutations and their reversal distance. As a result we can give an alternative approach and interpretation of the Hannenhalli-Pevzner formula for the reversal distance of signed permutations. Our approach utlizes the Poincare dual, upon which reversals act in a particular way and obsoletes the notion of padding of the signed permutations. To this end we construct a bijection between signed permutations and an equivalence class of particular fatgraphs, called $pi$-maps, and analyze the action of reversals on the latter. We show that reversals act via either slicing, gluing or half-flipping of external vertices, which implies that any reversal changes the topological genus by at most one. Finally we revisit the Hannenhalli-Pevzner formula employing orientable and non-orientable, irreducible, $pi$-maps.
We study the combinatorial properties of vexillary signed permutations, which are signed analogues of the vexillary permutations first considered by Lascoux and Schutzenberger. We give several equivalent characterizations of vexillary signed permutations, including descriptions in terms of essential sets and pattern avoidance, and we relate them to the vexillary elements introduced by Billey and Lam.
We show that the number of members of S_n avoiding any one of five specific triples of 4-letter patterns is given by sequence A111279 in OEIS, which is known to count weak sorting permutations. By numerical evidence, there are no other (non-trivial) triples of 4-letter patterns giving rise to this sequence. We make use of a variety of methods in proving our result, including recurrences, the kernel method, direct counting, and bijections.
The problem of distinguishing between a random function and a random permutation on a domain of size $N$ is important in theoretical cryptography, where the security of many primitives depend on the problems hardness. We study the quantum query complexity of this problem, and show that any quantum algorithm that solves this problem with bounded error must make $Omega(N^{1/5}/log N)$ queries to the input function. Our lower bound proof uses a combination of the Collision Problem lower bound and Ambainiss adversary theorem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
