Tractability and approximability of maximal strip recovery

An essential task in comparative genomics is to decompose two or more genomes into synteny blocks that are segments of chromosomes with similar contents. Given a set of d genomic maps each containing the same n markers without duplicates, the problem Maximal Strip Recovery (MSR) aims at finding a decomposition of the genomic maps into synteny blocks (strips) of the maximum total length ℓ, by deleting the minimum number k=n−ℓ of markers which are probably noise and ambiguities. In this paper, we present a collection of new or improved FPT and approximation algorithms for MSR and its variants. Our main results include a time FPT algorithm for δ-gap-MSR-d, a time FPT algorithm for both CMSR-d and δ-gap-CMSR-d, and a (d+1.5)-approximation algorithm for both CMSR-d and δ-gap-CMSR-d.