EUVIMEDEUVIMED entdecken
Crossref

A Constant-Factor Approximation for Weighted Complementary Maximal Strip Recovery

Fei Yu, Liu Wenbing

Bulletin of Computer and Data Sciences · 2023

DOI: 10.71448/bcds2343-2 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bulletin of Computer and Data Sciences, 2023. Verfasst von Fei Yu und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Maximal Strip Recovery (MSR) and its complementary version (CMSR) are classical optimization problems arising in comparative genomics: given two genomic maps on the same set of markers, the goal is to delete as few markers as possible (CMSR) so that the remaining markers can be partitioned into a set of common strips. Existing work has established NP-hardness and APX-hardness, and for the unweighted CMSR problem a 7/3-approximation is known via a prioritized sequence of local operations plus a local amortized analysis. In practical genomic settings, however, markers differ in reliability, biological importance, or confidence level, so the cost of deleting a marker is rarely uniform. In this paper we introduce the Weighted Complementary Maximal Strip Recovery (W-CMSR) problem, in which each marker has a positive weight and the objective is to minimize the total weight of deleted markers. We show that the local-operation framework can be extended to this weighted setting. We define weight-aware priorities, prove that every operation improves a suitable potential function, and give a charging scheme that bounds the algorithm’s total deletion weight by a constant factor of the optimal deletion weight. Concretely, we obtain a constant-factor approximation (with factor ≤ 3 in the basic version); we also discuss how tighter weight-normalized charges can reduce the factor toward the unweighted 7/3 bound. Our results broaden the applicability of CMSR-style algorithms to more realistic comparative-genomics instances where certain markers must be preserved whenever possible.

Zitieren

APA

Yu, F., & Wenbing, L. (2023). A Constant-Factor Approximation for Weighted Complementary Maximal Strip Recovery. Bulletin of Computer and Data Sciences. https://doi.org/10.71448/bcds2343-2

Vancouver

Yu F, Wenbing L. A Constant-Factor Approximation for Weighted Complementary Maximal Strip Recovery. Bulletin of Computer and Data Sciences. 2023. doi:10.71448/bcds2343-2

BibTeX
@article{Yu2023,
  author = {Yu, Fei and Wenbing, Liu},
  title = {A Constant-Factor Approximation for Weighted Complementary Maximal Strip Recovery},
  journal = {Bulletin of Computer and Data Sciences},
  year = {2023},
  doi = {10.71448/bcds2343-2}
}
Kostenlos starten →