Nonoverlapping Local Alignments (weighted Independent Sets of Axis-parallel Rectangles)

We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and either axis, the projection of one rectangle does not enclose that of the other. Define a pair to be independent if their projections in both axes are disjoint. The problem is to find a maximum-weight independent subset of rectangles. We show that the problem is NP-hard even in the uniform case when all the weights are the same. We analyze the performance of a natural local- improvement heuristic for the general problem and prove a performance ration of 3.25. We extend the heuristic to the problem of finding a maximum-weight independent set in (d+1)-claw free graphs, and show a tight performance ration of (d - 1 + (1/d)). A performance ratio of d/2 was known for the heuristic when applied to the uniform case. Our contributions are proving the hardness of the problem and providing a tight analysis of the local-improvement algorithm for the general weighted case.

• Publication year

  1996

• Venue

  Discrete Applied Mathematics

• Publication date

  1996-12-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/S0166-218X(96)00063-7
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sorting permutations by tanspositions

  1995cited by this paper
• Of mice and men: algorithms for evolutionary distances between genomes with translocation

  1995cited by this paper
• Approximating discrete collections via local improvements

  1995cited by this paper
• Approximating maximum independent set in bounded degree graphs

  1994cited by this paper
• Simple heuristics for unit disk graphs

  1994cited by this paper
• Efficient Bounds for Oriented Chromosome Inversion Distance

  1994cited by this paper
• Exact and Approximation Algorithms for the Inversion Distance Between Two Chromosomes

  1993cited by this paper
• Genome rearrangements and sorting by reversals

  1993cited by this paper
• Proof verification and hardness of approximation problems

  1992cited by this paper
• Identification of common molecular subsequences.

  1981cited by this paper
• On concentrators, superconcentrators, generalizers, and nonblocking networks

  1979cited by this paper
• Extremal Graph Theory

  1978cited by this paper
• A general method applicable to the search for similarities in the amino acid sequence of two proteins.

  1970cited by this paper

• Set Packing Optimization by Evolutionary Algorithms with Theoretical Guarantees

  2024cites this paper
• Mending Partial Solutions with Few Changes

  2022cites this paper
• Local improvement algorithms for a path packing problem: A performance analysis based on linear programming

  2021cites this paper
• Scheduling split intervals with non-uniform demands

  2020cites this paper
• Alignment Memories: A Useful Tool to Handle Phrase Alignment Bottleneck

  2020cites this paper
• Towards a Unified Framework for String Similarity Joins

  2019cites this paper
• Subexponential-Time Algorithms for Maximum Independent Set in Pt\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_t$$\

  2018cites this paper
• Scheduling multi-task jobs with extra utility in data centers

  2017cites this paper
• High precision detection of conserved segments from synteny blocks

  2017cites this paper
• Etude de l'évolution de l'ordre des gènes de vertébrés par simulation

  2016cites this paper
• A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs

  2016cites this paper
• Complex single machine scheduling

  2014cites this paper
• Fixed-parameter linear-time algorithms for NP-hard graph and hypergraph problems arising in industrial applications

  2014cites this paper
• A Variant of the Maximum Weight Independent Set Problem

  2014cites this paper
• Two Memory-Based Methods for Phrase Alignment

  2013cites this paper
• Scheduling Jobs with Multiple Non-uniform Tasks

  2013cites this paper
• A local search algorithm for binary maximum 2-path partitioning

  2013cites this paper
• A new model for coalition formation games

  2012cites this paper
• Mémoires partagées d’alignements sous-phrastiques bilingues

  2012influential citation
• Interval scheduling and colorful independent sets

  2012influential citation
• Aligning through divergence

  2012cites this paper
• Optimizing Experimental Design in Genetics

  2012cites this paper
• Two Memory-Based Methods for Phrase Alignement

  2012cites this paper
• k-Gap Interval Graphs

  2011cites this paper
• Screening synteny blocks in pairwise genome comparisons through integer programming

  2011influential citation
• Improved Algorithms for Weighted 3-Set Packing: Improved Algorithms for Weighted 3-Set Packing

  2010cites this paper
• Matroid matching: the power of local search

  2010cites this paper
• Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots

  2010influential citation
• On the parameterized complexity of some optimization problems related to multiple-interval graphs

  2010cites this paper
• Recognizing d-Interval Graphs and d-Track Interval Graphs

  2010cites this paper
• String Mining in Bioinformatics

  2010cites this paper
• Algorithms for genome comparison applied to bacterial genomes. (Algorithmes de comparaison de génomes appliqués aux génomes bactériens)

  2010cites this paper
• Sorting with Objectives: Graph-Theoretic Concepts in Industrial Optimization

  2010cites this paper
• Matroid Matching : the Power of Local Search [ Extended Abstract ]

  2010cites this paper
• Optimization problems in multiple-interval graphs

  2010cites this paper
• Discovery of Unconventional Patterns for Sequence Analysis: Theory and Algorithms

  2009cites this paper
• On Linear Programming Relaxations of Hypergraph Matching CHAN, Yuk Hei A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of Master of Philosophy

  2009cites this paper
• UvA-DARE ( Digital Academic Repository ) Optimization and approximation on systems of geometric objects

  2009cites this paper
• Improved Parameterized Algorithms for Weighted 3-Set Packing

  2008cites this paper
• Plagiarism Detection Using the Levenshtein Distance and Smith-Waterman Algorithm

  2008cites this paper
• Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots

  2007cites this paper
• On Restrictions of Balanced 2-Interval Graphs

  2007cites this paper
• On restrictions of 2-interval graphs

  2007cites this paper
• On the Fixed-Parameter Intractability and Tractability of Multiple-Interval Graph Problems

  2007cites this paper
• 2 Efficient combinatorial algorithms for DNA sequence processing

  2007influential citation
• Optimization problems in multiple-interval graphs

  2007cites this paper
• Algorithms and a software system for comparative genome analysis

  2006cites this paper
• A Survey of Approximation Results for Local Search Algorithms

  2006cites this paper
• A modified greedy algorithm for dispersively weighted 3-set cover

  2006cites this paper
• Clique-detection models in computational biochemistry and genomics

  2006cites this paper
• An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions

  2006cites this paper
• Spectrum Sharing Games

  2005cites this paper
• Using fractional primal-dual to schedule split intervals with demands

  2005cites this paper
• Scheduling Split Intervals Reuven Bar-Yehuda yz Magn us M. Halld orsson x Joseph (Se) Naor y

  2005cites this paper
• Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes

  2005influential citation
• Local ratio: A unified framework for approximation algorithms. In Memoriam: Shimon Even 1935-2004

  2004cites this paper
• An approximation algorithm for maximum triangle packing

  2004cites this paper
• Hardness of approximation for non-overlapping local alignments

  2004cites this paper
• On spectrum sharing games

  2004cites this paper
• Chaining Algorithms and Applications in Comparative Genomics

  2004cites this paper
• Local Ratio: A Unified Framework for Approximation Algorithms

  2004cites this paper
• Optimizing misdirection

  2003cites this paper
• A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)

  2002influential citation
• Scheduling split intervals

  2002influential citation
• Simple approximation algorithm for nonoverlapping local alignments

  2002cites this paper
• A Modified Greedy Algorithm for the Set Cover Problem with Weights 1 and 2

  2001cites this paper
• Improved approximation algorithms for rectangle tiling and packing

  2001cites this paper
• Greedy local improvement and weighted set packing approximation

  2001cites this paper
• Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles

  2001cites this paper
• A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs

  2000cites this paper
• An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling

  1999cites this paper
• On approximating rectangle tiling and packing

  1998cites this paper
• Approximations of Independent Sets in Graphs

  1998cites this paper
• An Approximation Algorithm for Maximum Packing of 3-Edge Paths

  1997cites this paper
• On Local Search for Weighted k-Set Packing

  1997cites this paper