On recovering syntenic blocks from comparative maps

DOI10.1007/s10878-009-9233-xzbMath1180.90261OpenAlexW2798164773MaRDI QIDQ1041433

Zhixiang Chen, Binhai Zhu, Bin Fu, Ming-Hui Jiang

Publication date: 2 December 2009

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-009-9233-x

zbMATH Keywords

NP-completenessbioinformaticsapproximation algorithms

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (17)

Parameterized Complexity in Multiple-Interval Graphs: Domination ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ The complexity of finding common partitions of genomes with predefined block sizes ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Maximal strip recovery problem with gaps: hardness and approximation algorithms ⋮ Exact and approximation algorithms for the complementary maximal strip recovery problem ⋮ An improved approximation algorithm for the complementary maximal strip recovery problem ⋮ Tractability and approximability of maximal strip recovery ⋮ A linear kernel for the complementary maximal strip recovery problem ⋮ A 42k Kernel for the Complementary Maximal Strip Recovery Problem ⋮ An Improved Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ Tractability and Approximability of Maximal Strip Recovery ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ Inapproximability of maximal strip recovery ⋮ A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem ⋮ An improved linear kernel for complementary maximal strip recovery: simpler and smaller ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics

Cites Work

• Approximating the 2-interval pattern problem
• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• Improved algorithms for largest cardinality 2-interval pattern problem
• On the computational complexity of 2-interval pattern matching problems
• Extracting constrained 2-interval subsets in 2-interval sets
• Non-breaking Similarity of Genomes with Gene Repetitions
• Linear FPT reductions and computational lower bounds
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• The complexity of satisfiability problems
• Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots
• Automata, Languages and Programming
• Scheduling Split Intervals

This page was built for publication: On recovering syntenic blocks from comparative maps