ERA

Download the full-sized PDF of An improved approximation algorithm for the complementary maximal strip recovery problemDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3RV0D224

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

An improved approximation algorithm for the complementary maximal strip recovery problem Open Access

Descriptions

Author or creator
Li, Zhong
Goebel, Randy
Wang, Lusheng
Lin, Guohui
Additional contributors
Subject/Keyword
Bioinformatics
Maximal strip recovery
Sequential amortized analysis
Algorithmics
Approximation algorithm
Type of item
Computing Science Technical Report
Computing science technical report ID
TR11-02
Language
English
Place
Time
Description
Technical report TR11-02. Given two genomic maps G1 and G2 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 G1 and G2 such that the resultant subsequences, denoted as G1* and G2*, can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7/3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a sequential amortization.
Date created
2011
DOI
doi:10.7939/R3RV0D224
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-24T23:35:41.672+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 374707
Last modified: 2015:10:12 16:45:46-06:00
Filename: TR11-02.pdf
Original checksum: a581295db0bef387eb694322840c5ea5
Well formed: true
Valid: true
File title: Introduction
Page count: 22
Activity of users you follow
User Activity Date