Exact and approximation algorithms for the complementary maximal strip recovery problem

Haitao Jiang (), Zhong Li (), Guohui Lin (), Lusheng Wang () and Binhai Zhu ()
Additional contact information
Haitao Jiang: Shandong University
Zhong Li: University of Alberta
Guohui Lin: University of Alberta
Lusheng Wang: City University of Hong Kong
Binhai Zhu: Montana State University

Journal of Combinatorial Optimization, 2012, vol. 23, issue 4, No 8, 493-506

Abstract: 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}^{*}$ and $G_{2}^{*}$ , 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.

Keywords: Fixed-parameter tractable; Approximation algorithm; Amortized analysis (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9366-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:4:d:10.1007_s10878-010-9366-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9366-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().