David A. Bader
IEEE Fellow
AAAS Fellow
Professor
College of Computing
Georgia Tech
Atlanta, GA
30332






Hannenhalli
and Pevzner gave the first polynomialtime algorithm
for computing the inversion distance between two signed
permutations, as part of the larger task of determining
the shortest sequence of inversions needed to transform
one permutation into the other. Their algorithm (restricted
to distance calculation) proceeds in two stages: in the
first stage, the overlap graph induced by the permutation
is decomposed into connected components, then in the
second stage certain graph structures (hurdles and others)
are identified. Berman and Hannenhalli avoided the explicit
computation of the overlap graph and gave an $O(n\alpha
(n))$ algorithm, based on a UnionFind structure, to
find its connected components, where $\alpha$ is the
inverse Ackerman function. Since for all practical purposes
$\alpha(n)$ is a constant no larger than four, this algorithm
has been the fastest practical algorithm to date. In
this paper, we present a new lineartime algorithm for
computing the connected components, which is more efficient
than that of Berman and Hannenhalli in both theory and
practice. Our algorithm uses only a stack and is very
easy to implement. We give the results of computational
experiments over a large range of permutation pairs produced
through simulated evolution; our experiments show a speedup
by a factor of 2 to 5 in the computation of the connected
components and by a factor of 1.3 to 2 in the overall
distance computation.
Versions
of this paper appeared as:
 D.A.
Bader, B.M.E. Moret, and M. Yan, ``A
LinearTime Algorithm for Computing Inversion Distance
Between Signed Permutations with an Experimental Study,'' Journal
of Computational Biology, 8(5):483491, 2001.
 D.A.
Bader, B.M.E. Moret, M. Yan, ``A
LinearTime Algorithm for Computing Inversion Distance
Between Signed Permutations with an Experimental Study,''
presented at the Seventh
International Workshop on Algorithms and Data Structures
(WADS2001), F. Dehne, J.R. Sack, and R. Tamassia
(eds.), SpringerVerlag LNCS 2125, 365376, Brown University,
Providence, RI, August 2001.
The code accompanying this paper can be found here: GRAPPA1.01.tar.gz 








Last updated:
July 25, 2004



Computational Biology
Parallel Computing
Combinatorics
