A 1.375-approximation algorithm for unsigned translocation sorting

DOI10.1016/J.JCSS.2020.05.004MaRDI QIDQ2186826zbMATH OpenOpenAlexFDO

Authors Lianrong Pu, Daming Zhu, Haitao Jiang

Publication date 9 June 2020

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2020.05.004

zbMATH Keywords

complexityapproximation algorithmgenome rearrangementtranslocation

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Protein sequences, DNA sequences (92D20) Searching and sorting (68P10) Approximation algorithms (68W25)

Recommendations

• A new approximation algorithm for unsigned translocation sorting
• Algorithms and Computation
• A 1.75-approximation algorithm for unsigned translocation distance
• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations

Cites work

• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• scientific article; zbMATH DE number 910919 (Why is no real title available?)
• A 1.75-approximation algorithm for unsigned translocation distance
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
• An \(O(n^{3/2}\sqrt {\log (n)})\) algorithm for sorting by reciprocal translocations
• Can a Breakpoint Graph be Decomposed into None Other Than 2-Cycles?
• Can a breakpoint graph be decomposed into none other than 2-cycles?
• Combinatorial Pattern Matching
• On the complexity of unsigned translocation distance
• Polynomial-time algorithm for computing translocation distance between genomes
• Transforming cabbage into turnip

Cited in

(9)

• A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
• On the complexity of unsigned translocation distance
• Algorithms and Computation
• A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
• A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
• A new approximation algorithm for unsigned translocation sorting
• Exact and approximation algorithms for the contiguous translocation distance problem
• A 1.75-approximation algorithm for unsigned translocation distance

This page was built for publication: A 1.375-approximation algorithm for unsigned translocation sorting

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