On Recovering Syntenic Blocks from Comparative Maps

DOI10.1007/978-3-540-85097-7_30MaRDI QIDQ5505670zbMATH OpenOpenAlexFDO

Authors Zhi-Xiang Chen, Bin Fu, Binhai Zhu, Minghui Jiang

Publication date 27 January 2009

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-85097-7_30

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Genetics and epigenetics (92D10)

Recommendations

• On recovering syntenic blocks from comparative maps
• On the Tractability of Maximal Strip Recovery
• Inapproximability of maximal strip recovery
• Efficient exact and approximate algorithms for the complement of Maximal Strip Recovery

Cites work

• A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem
• A PTAS for the Weighted 2-Interval Pattern Problem over the Preceding-and-Crossing Model
• Algorithms – ESA 2005
• Automata, Languages and Programming
• Extracting constrained 2-interval subsets in 2-interval sets
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• Improved algorithms for largest cardinality 2-interval pattern problem
• Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots
• Linear FPT reductions and computational lower bounds
• Non-breaking Similarity of Genomes with Gene Repetitions
• On the computational complexity of 2-interval pattern matching problems
• Scheduling Split Intervals
• The complexity of satisfiability problems

Cited in

(7)

• On recovering syntenic blocks from comparative maps
• The complexity of finding common partitions of genomes with predefined block sizes
• Maximal strip recovery problem with gaps: hardness and approximation algorithms
• Multilocus consensus genetic maps (MCGM): Formulation, algorithms, and results
• The complexity of gene placement
• On the Tractability of Maximal Strip Recovery
• Decoding the genomic architecture of mammalian and plant genomes: synteny blocks and large-scale duplications

This page was built for publication: On Recovering Syntenic Blocks from Comparative Maps

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