More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Zhi-Zhong Chen , Tao Jiang , Guohui Lin , Romeo Rizzi , Jianjun Wen , Dong Xu , Ying Xu

ABSTRACT

Protein NMR peak assignment refers to the process of assigning a group of “spin systems” obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein backbone NMR peak assignment has been formulated as an interval scheduling problem, where a protein sequence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} of amino acids is viewed as a discrete time interval \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document} (the amino acids on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} one-to-one correspond to the time units of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document}), each subset S of spin systems that are known to originate from consecutive amino acids of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} is viewed as a “job” jS, the preference of assigning S to a subsequence P of consecutive amino acids on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} is viewed as the profit of executing job jS in the subinterval of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document} corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document}. The interval scheduling problem is Max SNP-hard in general. Typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. To solve these most difficult assignments, we present an efficient \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{13}{7}$ \end{document}-approximation algorithm. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e. jobs that need more than two consecutive time units), we obtained a new efficient heuristic for protein NMR peak assignment. Our study using experimental data shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the literature. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{13}{7}$ \end{document}-approximation algorithm is also the first approximation algorithm for a nontrivial case of the classical (weighted) interval scheduling problem that breaks the ratio 2 barrier. More... »

PAGES

580-592

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-39658-1_53

DOI

http://dx.doi.org/10.1007/978-3-540-39658-1_53

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1041718318


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0102", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Applied Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA", 
          "id": "http://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jiang", 
        "givenName": "Tao", 
        "id": "sg:person.015107424575.17", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Comput. Sci., Univ. of Alberta, T6G 2E8, Edmonton, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.17089.37", 
          "name": [
            "Dept. of Comput. Sci., Univ. of Alberta, T6G 2E8, Edmonton, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Guohui", 
        "id": "sg:person.01130357621.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dipartimento di Informatica e Telecomunicazioni, Universit\u00e0 di Trento, Italy", 
          "id": "http://www.grid.ac/institutes/grid.11696.39", 
          "name": [
            "Dipartimento di Informatica e Telecomunicazioni, Universit\u00e0 di Trento, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rizzi", 
        "givenName": "Romeo", 
        "id": "sg:person.012014154343.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012014154343.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA", 
          "id": "http://www.grid.ac/institutes/grid.266097.c", 
          "name": [
            "Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wen", 
        "givenName": "Jianjun", 
        "id": "sg:person.013667114745.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667114745.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN", 
          "id": "http://www.grid.ac/institutes/grid.135519.a", 
          "name": [
            "Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Dong", 
        "id": "sg:person.01316670703.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316670703.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN", 
          "id": "http://www.grid.ac/institutes/grid.135519.a", 
          "name": [
            "Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xu", 
        "givenName": "Ying", 
        "id": "sg:person.01111424013.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111424013.29"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "Protein NMR peak assignment refers to the process of assigning a group of \u201cspin systems\u201d obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein backbone NMR peak assignment has been formulated as an interval scheduling problem, where a protein sequence \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{P}$\n\\end{document} of amino acids is viewed as a discrete time interval \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{I}$\n\\end{document} (the amino acids on \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{P}$\n\\end{document} one-to-one correspond to the time units of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{I}$\n\\end{document}), each subset S of spin systems that are known to originate from consecutive amino acids of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{P}$\n\\end{document} is viewed as a \u201cjob\u201d jS, the preference of assigning S to a subsequence P of consecutive amino acids on \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{P}$\n\\end{document} is viewed as the profit of executing job jS in the subinterval of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{I}$\n\\end{document} corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\mathcal{I}$\n\\end{document}. The interval scheduling problem is Max SNP-hard in general. Typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. To solve these most difficult assignments, we present an efficient \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\frac{13}{7}$\n\\end{document}-approximation algorithm. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e. jobs that need more than two consecutive time units), we obtained a new efficient heuristic for protein NMR peak assignment. Our study using experimental data shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the literature. The \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}\n$\\frac{13}{7}$\n\\end{document}-approximation algorithm is also the first approximation algorithm for a nontrivial case of the classical (weighted) interval scheduling problem that breaks the ratio 2 barrier.", 
    "editor": [
      {
        "familyName": "Di Battista", 
        "givenName": "Giuseppe", 
        "type": "Person"
      }, 
      {
        "familyName": "Zwick", 
        "givenName": "Uri", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-39658-1_53", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-20064-2", 
        "978-3-540-39658-1"
      ], 
      "name": "Algorithms - ESA 2003", 
      "type": "Book"
    }, 
    "keywords": [
      "consecutive amino acids", 
      "amino acids", 
      "protein sequences", 
      "NMR protein structure determination", 
      "protein structure determination", 
      "NMR peak assignments", 
      "structure determination", 
      "sequence", 
      "acid", 
      "SNPs", 
      "peak assignments", 
      "filtering strategy", 
      "data show", 
      "assignment", 
      "process", 
      "-J", 
      "preferences", 
      "strategies", 
      "system", 
      "study", 
      "show", 
      "barriers", 
      "determination", 
      "group", 
      "units", 
      "MAX SNP", 
      "discrete time intervals", 
      "time unit", 
      "goal", 
      "experimental data show", 
      "time interval", 
      "intervals", 
      "cases", 
      "challenging problem", 
      "difficult assignment", 
      "literature", 
      "problem", 
      "automation", 
      "algorithm", 
      "efficient heuristic", 
      "spin systems", 
      "profit", 
      "schedule", 
      "new heuristic", 
      "heuristics", 
      "assignment algorithm", 
      "subintervals", 
      "approximation algorithm", 
      "interval scheduling problem", 
      "scheduling problem", 
      "first approximation algorithm", 
      "jobs", 
      "nontrivial case", 
      "subset S", 
      "new efficient heuristic", 
      "total profit", 
      "longest job", 
      "scheduling", 
      "consecutive time units"
    ], 
    "name": "More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling", 
    "pagination": "580-592", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041718318"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-39658-1_53"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-39658-1_53", 
      "https://app.dimensions.ai/details/publication/pub.1041718318"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_30.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-39658-1_53"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39658-1_53'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39658-1_53'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39658-1_53'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-39658-1_53'


 

This table displays all metadata directly associated to this object as RDF triples.

178 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-39658-1_53 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author N632a8c719456472ba2d7d011cf484f55
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description Protein NMR peak assignment refers to the process of assigning a group of “spin systems” obtained experimentally to a protein sequence of amino acids. The automation of this process is still an unsolved and challenging problem in NMR protein structure determination. Recently, protein backbone NMR peak assignment has been formulated as an interval scheduling problem, where a protein sequence \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} of amino acids is viewed as a discrete time interval \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document} (the amino acids on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} one-to-one correspond to the time units of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document}), each subset S of spin systems that are known to originate from consecutive amino acids of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} is viewed as a “job” jS, the preference of assigning S to a subsequence P of consecutive amino acids on \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{P}$ \end{document} is viewed as the profit of executing job jS in the subinterval of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document} corresponding to P, and the goal is to maximize the total profit of executing the jobs (on a single machine) during \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\mathcal{I}$ \end{document}. The interval scheduling problem is Max SNP-hard in general. Typically the jobs that require one or two consecutive time units are the most difficult to assign/schedule. To solve these most difficult assignments, we present an efficient \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{13}{7}$ \end{document}-approximation algorithm. Combining this algorithm with a greedy filtering strategy for handling long jobs (i.e. jobs that need more than two consecutive time units), we obtained a new efficient heuristic for protein NMR peak assignment. Our study using experimental data shows that the new heuristic produces the best peak assignment in most of the cases, compared with the NMR peak assignment algorithms in the literature. The \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\frac{13}{7}$ \end{document}-approximation algorithm is also the first approximation algorithm for a nontrivial case of the classical (weighted) interval scheduling problem that breaks the ratio 2 barrier.
7 schema:editor N837ecce83d384d6fa4e7295c147baa1f
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Na51b8d49c9204551a49d5398116ec1c8
12 schema:keywords -J
13 MAX SNP
14 NMR peak assignments
15 NMR protein structure determination
16 SNPs
17 acid
18 algorithm
19 amino acids
20 approximation algorithm
21 assignment
22 assignment algorithm
23 automation
24 barriers
25 cases
26 challenging problem
27 consecutive amino acids
28 consecutive time units
29 data show
30 determination
31 difficult assignment
32 discrete time intervals
33 efficient heuristic
34 experimental data show
35 filtering strategy
36 first approximation algorithm
37 goal
38 group
39 heuristics
40 interval scheduling problem
41 intervals
42 jobs
43 literature
44 longest job
45 new efficient heuristic
46 new heuristic
47 nontrivial case
48 peak assignments
49 preferences
50 problem
51 process
52 profit
53 protein sequences
54 protein structure determination
55 schedule
56 scheduling
57 scheduling problem
58 sequence
59 show
60 spin systems
61 strategies
62 structure determination
63 study
64 subintervals
65 subset S
66 system
67 time interval
68 time unit
69 total profit
70 units
71 schema:name More Reliable Protein NMR Peak Assignment via Improved 2-Interval Scheduling
72 schema:pagination 580-592
73 schema:productId N83fcc97912b5436e9a8e97ee777aa09f
74 Nb4d0ec034d5e40a6a51a2dcb6dfdffdd
75 schema:publisher N30a1a6c9d1594165b7893567ea77fee2
76 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041718318
77 https://doi.org/10.1007/978-3-540-39658-1_53
78 schema:sdDatePublished 2022-05-20T07:45
79 schema:sdLicense https://scigraph.springernature.com/explorer/license/
80 schema:sdPublisher N2b8bca1f2e93407ca50fe3089529ed3e
81 schema:url https://doi.org/10.1007/978-3-540-39658-1_53
82 sgo:license sg:explorer/license/
83 sgo:sdDataset chapters
84 rdf:type schema:Chapter
85 N0662cec4268141f5afe95692ddb1b3c4 schema:familyName Di Battista
86 schema:givenName Giuseppe
87 rdf:type schema:Person
88 N2b8bca1f2e93407ca50fe3089529ed3e schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 N30a1a6c9d1594165b7893567ea77fee2 schema:name Springer Nature
91 rdf:type schema:Organisation
92 N3b385bb1c88b4e05b736e5683c697cee schema:familyName Zwick
93 schema:givenName Uri
94 rdf:type schema:Person
95 N4532966b602e4bc99fdc6a59274cefb6 rdf:first sg:person.01111424013.29
96 rdf:rest rdf:nil
97 N632a8c719456472ba2d7d011cf484f55 rdf:first sg:person.015654265661.98
98 rdf:rest Nba6c0ed5850340fa9c288a65a9be4adc
99 N792b1b8ac4b34d17982c8bc859a7bce5 rdf:first sg:person.012014154343.00
100 rdf:rest Ndd6368e8bf8042ee894dd2fabea9e9bf
101 N837ecce83d384d6fa4e7295c147baa1f rdf:first N0662cec4268141f5afe95692ddb1b3c4
102 rdf:rest Na016dd0a228143f4b9f14e51680f306d
103 N83fcc97912b5436e9a8e97ee777aa09f schema:name dimensions_id
104 schema:value pub.1041718318
105 rdf:type schema:PropertyValue
106 Na016dd0a228143f4b9f14e51680f306d rdf:first N3b385bb1c88b4e05b736e5683c697cee
107 rdf:rest rdf:nil
108 Na51b8d49c9204551a49d5398116ec1c8 schema:isbn 978-3-540-20064-2
109 978-3-540-39658-1
110 schema:name Algorithms - ESA 2003
111 rdf:type schema:Book
112 Nb4d0ec034d5e40a6a51a2dcb6dfdffdd schema:name doi
113 schema:value 10.1007/978-3-540-39658-1_53
114 rdf:type schema:PropertyValue
115 Nba6c0ed5850340fa9c288a65a9be4adc rdf:first sg:person.015107424575.17
116 rdf:rest Nf1346c8f5a2748f495c115a178e04766
117 Ndd6368e8bf8042ee894dd2fabea9e9bf rdf:first sg:person.013667114745.67
118 rdf:rest Ne091b54ec6444a3abf185bba5c498f49
119 Ne091b54ec6444a3abf185bba5c498f49 rdf:first sg:person.01316670703.59
120 rdf:rest N4532966b602e4bc99fdc6a59274cefb6
121 Nf1346c8f5a2748f495c115a178e04766 rdf:first sg:person.01130357621.02
122 rdf:rest N792b1b8ac4b34d17982c8bc859a7bce5
123 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
124 schema:name Mathematical Sciences
125 rdf:type schema:DefinedTerm
126 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
127 schema:name Applied Mathematics
128 rdf:type schema:DefinedTerm
129 sg:person.01111424013.29 schema:affiliation grid-institutes:grid.135519.a
130 schema:familyName Xu
131 schema:givenName Ying
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01111424013.29
133 rdf:type schema:Person
134 sg:person.01130357621.02 schema:affiliation grid-institutes:grid.17089.37
135 schema:familyName Lin
136 schema:givenName Guohui
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01130357621.02
138 rdf:type schema:Person
139 sg:person.012014154343.00 schema:affiliation grid-institutes:grid.11696.39
140 schema:familyName Rizzi
141 schema:givenName Romeo
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012014154343.00
143 rdf:type schema:Person
144 sg:person.01316670703.59 schema:affiliation grid-institutes:grid.135519.a
145 schema:familyName Xu
146 schema:givenName Dong
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316670703.59
148 rdf:type schema:Person
149 sg:person.013667114745.67 schema:affiliation grid-institutes:grid.266097.c
150 schema:familyName Wen
151 schema:givenName Jianjun
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013667114745.67
153 rdf:type schema:Person
154 sg:person.015107424575.17 schema:affiliation grid-institutes:grid.266097.c
155 schema:familyName Jiang
156 schema:givenName Tao
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015107424575.17
158 rdf:type schema:Person
159 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
160 schema:familyName Chen
161 schema:givenName Zhi-Zhong
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
163 rdf:type schema:Person
164 grid-institutes:grid.11696.39 schema:alternateName Dipartimento di Informatica e Telecomunicazioni, Università di Trento, Italy
165 schema:name Dipartimento di Informatica e Telecomunicazioni, Università di Trento, Italy
166 rdf:type schema:Organization
167 grid-institutes:grid.135519.a schema:alternateName Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN
168 schema:name Life Sciences Division, Oak Ridge National Lab., 37831, Oak Ridge, TN
169 rdf:type schema:Organization
170 grid-institutes:grid.17089.37 schema:alternateName Dept. of Comput. Sci., Univ. of Alberta, T6G 2E8, Edmonton, Alberta, Canada
171 schema:name Dept. of Comput. Sci., Univ. of Alberta, T6G 2E8, Edmonton, Alberta, Canada
172 rdf:type schema:Organization
173 grid-institutes:grid.266097.c schema:alternateName Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA
174 schema:name Dept. of Comput. Sci., Univ. of California, 92521, Riverside, CA
175 rdf:type schema:Organization
176 grid-institutes:grid.412773.4 schema:alternateName Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
177 schema:name Dept. of Math. Sci., Tokyo Denki Univ., 350-0394, Hatoyama, Saitama, Japan
178 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...