2009/12/31 by Minghui Jiang · 8 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Constant (computer programming) #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Longest common subsequence problem #Longest increasing subsequence #Orientation (vector space) #Subsequence #Synteny #cs.CC
paper · pdf · doi:10.1007/978-3-642-14553-7_8
published in Lecture notes in computer science, 53-64 (Springer Science+Business Media) · A preliminary version of this paper appeared in two parts in the Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009) and the Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW 2010)
openalex publication_date 2010/01/01 · arxiv created 2010/06/04 · arxiv updated 2015/05/14 · openalex created_date 2016/10/07 · openalex updated_date 2026/08/05
In comparative genomic, the first step of sequence analysis is usually to decompose two or more genomes into syntenic blocks that are segments of homologous chromosomes. For the reliable recovery of syntenic blocks, noise and ambiguities in the genomic maps need to be removed first. Maximal Strip Recovery (MSR) is an optimization problem proposed by Zheng, Zhu, and Sankoff for reliably recovering syntenic blocks from genomic maps in the midst of noise and ambiguities. Given d genomic maps as sequences of gene markers, the objective of \msrd is to find d subsequences, one subsequence of each genomic map, such that the total length of syntenic blocks in these subsequences is maximized. For any constant d ≥ 2, a polynomial-time 2d-approximation for \msrd was previously known. In this paper, we show that for any d ≥ 2, \msrd is APX-hard, even for the most basic version of the problem in which all gene markers are distinct and appear in positive orientation in each genomic map. Moreover, we provide the first explicit lower bounds on approximating \msrd for all d ≥ 2. In particular, we show that \msrd is NP-hard to approximate within Ω(d/log d). From the other direction, we show that the previous 2d-approximation for \msrd can be optimized into a polynomial-time algorithm even if d is not a constant but is part of the input. We then extend our inapproximability results to several related problems including \cmsrd, \gapmsrδd, and \gapcmsrδd.