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

DOI10.1016/J.IPL.2010.03.003MaRDI QIDQ991802zbMATH OpenOpenAlexFDO

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

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

algorithmdata structurepermutation groupgenome rearrangementgeneralized transpositionpermutation treeblock-interchange

Mathematics Subject Classification ID

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

Recommendations

• An improved block-interchange algorithm
• Sorting permutations by block-interchanges
• Theory and Applications of Models of Computation
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Approximation algorithms for sorting permutations by extreme block-interchanges

Cites work

• scientific article; zbMATH DE number 1306890 (Why is no real title available?)
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Advances on sorting by reversals
• An $O(n^{3/2}\sqrt{\log (n)})$ Algorithm for Sorting by Reciprocal Translocations
• An alternative algebraic formalism for genome rearrangements
• Faster algorithms for sorting by transpositions and sorting by block interchanges
• Polynomial-time algorithm for computing translocation distance between genomes
• Sorting by Transpositions
• Sorting permutations by block-interchanges
• The average number of block interchanges needed to sort a permutation and a recent result of Stanley
• Transforming cabbage into turnip

Cited in

(9)

• Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics
• An efficient algorithm for one-sided block ordering problem with block-interchange distance
• An improved block-interchange algorithm
• An efficient algorithm for one-sided block ordering problem under block-interchange distance
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations
• Theory and Applications of Models of Computation
• Rearrangement events on circular genomes
• Faster algorithms for sorting by transpositions and sorting by block interchanges

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991802)