ﻻ يوجد ملخص باللغة العربية
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.
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 ver
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 p
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 permutat
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)
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 compl