A 1.75-approximation algorithm for unsigned translocation distance

DOI10.1016/j.jcss.2007.03.009zbMath1123.68144OpenAlexW3026825597MaRDI QIDQ2643729

Daming Zhu, Yun Cui, Lusheng Wang

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

zbMATH Keywords

approximation algorithmunsigned translocation distance

Mathematics Subject Classification ID

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

Related Items (3)

Can a breakpoint graph be decomposed into none other than 2-cycles? ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of unsigned translocation distance
• Matching theory
• 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
• Genome Rearrangements and Sorting by Reversals
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Research in Computational Molecular Biology
• Polynomial-time algorithm for computing translocation distance between genomes

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