NDLI: A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem

Please wait, while we are loading the content...

A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem

Content Provider	ACM Digital Library
Author	Canzar, Stefan Elbassioni, Khaled Mestre, Julin
Copyright Year	2013
Abstract	We study the interval constrained coloring problem, a combinatorial problem arising in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. The problem captures the challenging task of increasing the spatial resolution of experimental data in order to get a better picture of the protein structure. Since solutions proposed by any algorithmic framework have to ultimately be verified by biochemists, it is important to provide not just a single solution, but a valuable set of candidate solutions. Our contribution is a polynomial-delay, polynomial-space algorithm for enumerating all exact solutions plus further approximate solutions, which are guaranteed to be within an absolute error of two of the optimum within fragments of the protein, that is, within sets of consecutive residues. Our experiments indicate that the quality of the approximate solutions is comparable to the optimal ones in terms of deviation from the underlying true solution. In addition, the experiments also confirm the effectiveness of the method in reducing the delay between two consecutive solutions considerably, compared to what it takes an integer programming solver to produce the next exact solution.
Starting Page	2.1
Ending Page	2.19
Page Count	19
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/2444016.2493372
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	18
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	LP rounding Hydrogen-deuterium exchange Protein structure
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Polynomial Delay Algorithm for Enumerating Approximate Solutions to the Interval Constrained Coloring Problem

A polynomial delay algorithm for enumerating approximate solutions to the interval constrained coloring problem.

A polynomial delay algorithm for enumerating approximate solutions to the interval constraint coloring problem

Approximation algorithms for the interval constrained coloring problem (2010).

Approximation algorithms for the interval constrained coloring problem∗.

Approximation Algorithms for the Interval Constrained Coloring Problem

Approximating the interval constrained coloring problem (2008)

Application of deuterium–hydrogen exchange to study the secondary structure of oligonucleotide ions in a gas phase

On finding feasible solutions for the delay constrained group multicast routing problem

A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem

Similar Documents

A Polynomial Delay Algorithm for Enumerating Approximate Solutions to the Interval Constrained Coloring Problem

A polynomial delay algorithm for enumerating approximate solutions to the interval constrained coloring problem.

A polynomial delay algorithm for enumerating approximate solutions to the interval constraint coloring problem

Approximation algorithms for the interval constrained coloring problem (2010).

Approximation algorithms for the interval constrained coloring problem∗.

Approximation Algorithms for the Interval Constrained Coloring Problem

Approximating the interval constrained coloring problem (2008)

Application of deuterium–hydrogen exchange to study the secondary structure of oligonucleotide ions in a gas phase

On finding feasible solutions for the delay constrained group multicast routing problem

A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem