A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem

Haitao Jiang, Jiong Guo, Daming Zhu, Binhai ZhuCPM 2019 · OpenReview

TL;DR

This paper introduces a new 2-approximation algorithm for the Complementary Maximal Strip Recovery (CMSR) problem, a crucial task in computational genomics for identifying conserved gene order between species. While the improvement in the approximation factor over the previous best (7/3) is modest, the algorithm's analysis is significantly simplified by a novel "non-oblivious local search" technique.

What Problem Does This Paper Address?

Computational genomics often involves comparing the genetic makeup of different species to understand evolutionary relationships and identify conserved gene regions. These comparisons can be represented as "signed permutations," where genes are ordered and can appear in either forward or reverse orientation. The Maximal Strip Recovery (MSR) problem aims to find the largest possible set of conserved gene regions (called "strips" of length at least two) that appear in both species' genetic maps.

This paper focuses on the complementary problem: Complementary Maximal Strip Recovery (CMSR). The goal here is to delete the minimum number of "noisy" or ambiguous gene markers from the two genetic maps so that all remaining markers form valid common strips. Both MSR and CMSR are known to be NP-hard, meaning finding the absolute optimal solution is computationally infeasible for large datasets. Therefore, researchers develop approximation algorithms that guarantee a solution within a certain factor of the optimal. The existing best approximation for CMSR was 7/3, meaning the algorithm might delete up to 7/3 times the minimum number of markers.

Methods

The core of this paper is a new approximation algorithm for CMSR that achieves a factor of 2. This is accomplished using a technique called non-oblivious local search.

Here's a breakdown of the approach:

  • Preprocessing: The algorithm first identifies existing common strips and "candidate adjacencies" (pairs of genes that could form a strip if intervening genes were removed). It then iteratively expands these initial strips by "attaching" or "joining" genes based on these candidate adjacencies.
  • Non-Oblivious Local Search: This is the key innovation. Unlike standard local search where each step must improve the objective function (minimizing deleted genes), this technique allows steps that might not immediately improve the objective. Instead, these steps improve a related, but different, auxiliary function. This "non-oblivious" nature allows the algorithm to explore a wider solution space and potentially escape local optima that might trap a standard local search. The algorithm iteratively refines a set of common strips (CS) by applying three types of "substitutions" (0-substitution, 1-substitution, 2-substitution) that aim to improve the auxiliary function.
  • Analysis: The paper provides a rigorous proof that this algorithm achieves a 2-approximation factor. This involves a detailed analysis of how the algorithm's output relates to the optimal solution, using concepts like "occupying sets," "breaking sets," and a carefully designed "weight assignment" scheme to bound the error.

Datasets

Not discussed in the paper. The paper focuses on the theoretical development of an algorithm and its approximation guarantee, rather than empirical evaluation on specific biological datasets.

Key Insights and Ideas

  • The Power of Non-Oblivious Local Search: The most significant insight is the successful application and analysis of non-oblivious local search for CMSR. This technique, by decoupling immediate objective improvement from the search step, offers a powerful way to navigate complex optimization landscapes where strict local improvement might lead to suboptimal solutions.
  • Simplified Analysis: While the approximation factor improvement is modest (from 7/3 to 2), the paper highlights that the analysis of the algorithm is greatly simplified by this technique. This suggests that non-oblivious local search might be a more general and tractable approach for analyzing approximation algorithms in computational biology.
  • Connecting Adjacencies and Strips: The algorithm's strategy of building longer strips from shorter "candidate adjacencies" and existing strips is a fundamental approach in this problem domain. The paper refines this by carefully managing the conditions under which these operations are performed.

Key Results

  • 2-Approximation Algorithm: The paper presents a new algorithm for CMSR that guarantees a 2-approximation factor. This means the number of deleted genes is at most twice the minimum possible.
  • Improved Analysis: The analysis of the algorithm is presented as being significantly simpler than previous methods, largely due to the non-oblivious local search approach.
  • O(n²) Time Complexity: The algorithm is shown to run in polynomial time, specifically O(n²), making it efficient for practical use.

Limitations and Future Work

  • Modest Approximation Factor Improvement: While a factor of 2 is theoretically better than 7/3, the improvement is not dramatic. The paper acknowledges this, stating "Although the improvement on the factor is not huge..."
  • Theoretical Focus: The paper is primarily theoretical, focusing on the algorithm's design and approximation guarantee. It does not include experimental results on real biological data, which would be a natural next step to demonstrate its practical utility.
  • Generalizability of Non-Oblivious Local Search: The authors express hope that this technique will find more applications in computational biology, suggesting future work could explore its use for other related problems. The complexity of the weight assignment and analysis in the paper also hints at the challenges in applying this technique broadly.

Summary updated

Abstract

The Maximal Strip Recovery problem (MSR) and its complementary (CMSR) are well-studied NP-hard problems in computational genomics. The input of these dual problems are two signed permutations. The goal is to delete some gene markers from both permutations, such that, in the remaining permutations, each gene marker has at least one common neighbor. Equivalently, the resulting permutations could be partitioned into common strips of length at least two. Then MSR is to maximize the number of remaining genes, while the objective of CMSR is to delete the minimum number of gene markers. In this paper, we present a new approximation algorithm for the Complementary Maximal Strip Recovery (CMSR) problem. Our approximation factor is 2, improving the currently best 7/3-approximation algorithm. Although the improvement on the factor is not huge, the analysis is greatly simplified by a compensating method, commonly referred to as the non-oblivious local search technique. In such a method a substitution may not always increase the value of the current solution (it sometimes may even decrease the solution value), though it always improves the value of another function seemingly unrelated to the objective function.
BibTeX
@inproceedings{jiang2019approximation,
  author = {Haitao Jiang and Jiong Guo and Daming Zhu and Binhai Zhu},
  title = {{A 2-Approximation Algorithm for the Complementary Maximal Strip Recovery Problem}},
  booktitle = {CPM},
  year = {2019},
  url = {https://openreview.net/forum?id=dz7pcWod8M},
}
Figure