A 1.75-approximation algorithm for unsigned translocation distance

DOI10.1016/J.JCSS.2007.03.009zbMATH Open1123.68144OpenAlexW3026825597MaRDI QIDQ2643729FDOQ2643729

Authors: Yun Cui, Lusheng Wang, Daming Zhu 

Publication date: 27 August 2007

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.2007.03.009

Recommendations

• Algorithms and Computation
• A 1.375-approximation algorithm for unsigned translocation sorting
• A new approximation algorithm for unsigned translocation sorting
• On the complexity of unsigned translocation distance
• A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations

zbMATH Keywords

approximation algorithmunsigned translocation distance

Mathematics Subject Classification ID

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

Cites Work

• Matching theory
• Research in Computational Molecular Biology
• Title not available (Why is that?)
• Polynomial-time algorithm for computing translocation distance between genomes
• Title not available (Why is that?)
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Genome Rearrangements and Sorting by Reversals
• On the complexity of unsigned translocation distance
• Comparative genomics. Empirical and analytical approaches to gene order dynamics, map alignment and the evolution of gene families. Papers at the DCAF workshop, Québec, Canada, September 22--25, 2000

Cited In (9)

• Algorithms and Computation
• On the complexity of 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
• A new approximation algorithm for unsigned translocation sorting
• Structural, Syntactic, and Statistical Pattern Recognition
• Exact and approximation algorithms for the contiguous translocation distance problem
• A 1.375-approximation algorithm for unsigned translocation sorting
• Can a breakpoint graph be decomposed into none other than 2-cycles?

This page was built for publication: A 1.75-approximation algorithm for unsigned translocation distance

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