An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations

DOI10.1016/J.JDA.2011.04.003zbMath1228.92054OpenAlexW2107632273MaRDI QIDQ655439

Ron Shamir, Michal Ozery-Flato

Publication date: 4 January 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2011.04.003

zbMATH Keywords

reversalsgenome rearrangements

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Biochemistry, molecular biology (92C40) Genetics and epigenetics (92D10) Algorithms in computer science (68W99) Algorithms on strings (68W32)

Related Items (3)

A 1.375-approximation algorithm for unsigned translocation sorting ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Unnamed Item
• Unnamed Item
• Advances on sorting by reversals
• A very elementary presentation of the Hannenhalli-Pevzner theory
• Sorting signed permutations by reversals, revisited
• Transforming cabbage into turnip
• 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
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Polynomial-time algorithm for computing translocation distance between genomes

This page was built for publication: An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations