Approximation algorithms for the interval constrained coloring problem

Althaus, Ernst; Canzar, Stefan; Elbassioni, Khaled; Karrenbauer, Andreas; Mestre, Julián

Approximation algorithms for the interval constrained coloring problem

Dateien

Karrenbauer etal.pdfGröße: 6.37 MBDownloads: 1041

Datum

2010

Autor:innen

Althaus, Ernst

Canzar, Stefan

Elbassioni, Khaled

Karrenbauer, Andreas

Mestre, Julián

Open Access-Veröffentlichung

Open Access Green

Sammlungen

Zukunftskolleg
Informatik und Informationswissenschaft

Publikationstyp

Zeitschriftenartikel

Publikationsstatus

Published

Erschienen in

Algorithmica. 2010, 61(2), pp. 342-361. ISSN 0178-4617. Available under: doi: 10.1007/s00453-010-9406-0

Zusammenfassung

We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogendeuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constrained coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein segment) and requirements on the number of elements that belong to each color class (exchange rates observed in the experiments).

Fachgebiet (DDC)

004 Informatik

Zitieren

ISO 690

ALTHAUS, Ernst, Stefan CANZAR, Khaled ELBASSIONI, Andreas KARRENBAUER, Julián MESTRE, 2010. Approximation algorithms for the interval constrained coloring problem. In: Algorithmica. 2010, 61(2), pp. 342-361. ISSN 0178-4617. Available under: doi: 10.1007/s00453-010-9406-0

BibTex

@article{Althaus2010Appro-17265,
  year={2010},
  doi={10.1007/s00453-010-9406-0},
  title={Approximation algorithms for the interval constrained coloring problem},
  number={2},
  volume={61},
  issn={0178-4617},
  journal={Algorithmica},
  pages={342--361},
  author={Althaus, Ernst and Canzar, Stefan and Elbassioni, Khaled and Karrenbauer, Andreas and Mestre, Julián}
}

RDF

<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/17265">
    <dc:creator>Karrenbauer, Andreas</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:abstract xml:lang="eng">We consider the interval constrained coloring problem, which appears in the interpretation of experimental data in biochemistry. Monitoring hydrogendeuterium exchange rates via mass spectroscopy experiments is a method used to obtain information about protein tertiary structure. The output of these experiments provides data about the exchange rate of residues in overlapping segments of the protein backbone. These segments must be re-assembled in order to obtain a global picture of the protein structure. The interval constrained coloring problem is the mathematical abstraction of this re-assembly process. The objective of the interval constrained coloring problem is to assign a color (exchange rate) to a set of integers (protein residues) such that a set of constraints is satisfied. Each constraint is made up of a closed interval (protein segment) and requirements on the number of elements that belong to each color class (exchange rates observed in the experiments).</dcterms:abstract>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-12-01T12:41:29Z</dcterms:available>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:title>Approximation algorithms for the interval constrained coloring problem</dcterms:title>
    <dc:contributor>Elbassioni, Khaled</dc:contributor>
    <dc:creator>Canzar, Stefan</dc:creator>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/17265/1/Karrenbauer%20etal.pdf"/>
    <dc:contributor>Karrenbauer, Andreas</dc:contributor>
    <dc:rights>terms-of-use</dc:rights>
    <dc:creator>Elbassioni, Khaled</dc:creator>
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-12-01T12:41:29Z</dc:date>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/17265"/>
    <dc:creator>Mestre, Julián</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/17265/1/Karrenbauer%20etal.pdf"/>
    <dcterms:bibliographicCitation>First publ. in: Algorithmica ; 61 (2011), 2. - S. 342-361</dcterms:bibliographicCitation>
    <dc:creator>Althaus, Ernst</dc:creator>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/52"/>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Canzar, Stefan</dc:contributor>
    <dc:contributor>Mestre, Julián</dc:contributor>
    <dc:contributor>Althaus, Ernst</dc:contributor>
    <dcterms:issued>2010</dcterms:issued>
    <dc:language>eng</dc:language>
  </rdf:Description>
</rdf:RDF>

Universitätsbibliographie

Ja