On the approximability of the exemplar adjacency number problem for genomes with gene repetitions

DOI10.1016/j.tcs.2014.07.011zbMath1417.68050OpenAlexW2111945870MaRDI QIDQ401311

Jinhui Xu, Randy Goebel, Bin Fu, Weitian Tong, Zhiyu Zhao, Boting Yang, Binhai Zhu, Zhixiang Chen, Guo-Hui Lin

Publication date: 26 August 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.011

zbMATH Keywords

breakpointapproximation algorithmNP-hardnessadjacencygenome comparison

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items (3)

Genomic Scaffold Filling: A Progress Report ⋮ Fixed-parameter algorithms for scaffold filling ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets with domination constraints
• On the inapproximability of the exemplar conserved interval distance problem of genomes
• Transforming cabbage into turnip
• Linear FPT reductions and computational lower bounds
• Lower Bounds on the Approximation of the Exemplar Conserved Interval Distance Problem of Genomes
• On the Approximability of Comparing Genomes with Duplicates
• A Retrospective on Genomic Preprocessing for Comparative Genomics
• The Approximability of the Exemplar Breakpoint Distance Problem
• Computing and Combinatorics

This page was built for publication: On the approximability of the exemplar adjacency number problem for genomes with gene repetitions