A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study
By David A. Bader, B. Moret, Mi Yan. Workshop on Algorithms and Data Structures, 2001
398 citations recorded by the source corpus.
Hannenhalli and Pevzner gave the first polynomial-time 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α(n)) algorithm, based on a Union-Find structure, to find its connected components, where α is the inverse Ackerman function. Since for all practical purposes α(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 linear-time 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 speed-up 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.
Subfields: Artificial Intelligence, Genetics, Molecular Biology
View Paper: https://www.semanticscholar.org/paper/42447221f01080432ad9a1edca02dc4f759d5fef
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Genetics
In Molecular Biology
- David Haussler
- Glenn Tesler
- W. James Kent
- Brian J. Raney
- Aaron E. Darling
- Webb Miller
- Bob Mau
- Nicole T. Perna
Citations in the corpus
- GRIMM: genome rearrangements web server (2002, methodology): “This code makes extensive use of code that was adapted from GRAPPA for computing unichromosomal distance in linear time (Bader et al., 2001); how the multichromosomal algorithm was integrated with this, as well as corrections to errors in Hannenhalli and Pevzner (1995), will be described in Tesler…”
- Reconstructing contiguous regions of an ancestral genome. (2006, methodology): “Inspired by this landmark algorithm, more efficient algorithms have been proposed since then (Berman and Hannenhalli, 1996; Kaplan et al., 1997; Bader et al., 2001).”
- Some problems on Cayley graphs (2008, background): “[53] that the reversal distance could be calculated in linear time for signed permutations.”
- Mauve: multiple alignment of conserved genomic sequence with rearrangements. (2004, background): “Much research has been devoted to inference of rearrangement history that could lead to observed permutations in gene order (Bader et al. 2001; Bourque and Pevzner 2002; Larget et al. 2002; Eichler and Sankoff 2003).”