Exact and approximation algorithms for the complementary maximal strip recovery problem

Exact and approximation algorithms for the complementary maximal strip recovery problem

0.00 Avg rating0 Votes
Article ID: iaor20123735
Volume: 23
Issue: 4
Start Page Number: 493
End Page Number: 506
Publication Date: May 2012
Journal: Journal of Combinatorial Optimization
Authors: , , , ,
Keywords: combinatorial optimization
Abstract:

Given two genomic maps G 1 and G 2 each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G 1 and G 2 such that the resultant subsequences, denoted as G 1 * equ1 and G 2 * equ2 , can be partitioned into the same set of maximal substrings of length greater than or equal to two. Such substrings can occur in the reversal and negated form. The complementary maximal strip recovery (CMSR) problem is to delete the minimum number of markers from both G 1 and G 2 for the same purpose, with its optimization goal exactly complementary to maximizing the total number of gene markers retained in the final maximal substrings. Both MSR and CMSR have been shown NP‐hard and APX‐hard. A 4‐approximation algorithm is known for the MSR problem, but no constant ratio approximation algorithm for CMSR. In this paper, we present an O(3 k n 2)‐time fixed‐parameter tractable (FPT) algorithm, where k is the size of the optimal solution, and a 3‐approximation algorithm for the CMSR problem.

Reviews

Required fields are marked *. Your email address will not be published.