An improved algorithm for sorting by block-interchanges based on permutation groups

DOI10.1016/j.ipl.2010.03.003zbMath1213.68418OpenAlexW1984048611MaRDI QIDQ991802

Cheng-Chen Huang, Chin Lung Lu, Yen-Lin Huang, Chuan Yi Tang

Publication date: 7 September 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.03.003

zbMATH Keywords

algorithmpermutation groupgenome rearrangementdata structurepermutation treegeneralized transpositionblock-interchange

Mathematics Subject Classification ID

Searching and sorting (68P10) Combinatorics in computer science (68R05) Data structures (68P05)

Related Items (4)

Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics ⋮ Rearrangement events on circular genomes ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting permutations by block-interchanges
• Advances on sorting by reversals
• The average number of block interchanges needed to sort a permutation and a recent result of Stanley
• Transforming cabbage into turnip
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Sorting by Transpositions
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• An $O(n^{3/2}\sqrt{\log (n)})$ Algorithm for Sorting by Reciprocal Translocations
• Polynomial-time algorithm for computing translocation distance between genomes

This page was built for publication: An improved algorithm for sorting by block-interchanges based on permutation groups