A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Piotr Berman , Bhaskar DasGupta

ABSTRACT

We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis parallel rectangles such that, for each axis, the projection of a rectangle on this axis does not enclose that of another, and our goal is to select a subset of independent rectangles from the given set of rectangles of total maximum weight, where two rectangles are independent provided for each axis, the projection of one rectangle does not overlap that of another. We use the two-phase technique of [3] to provide a simple approximation algorithm for this problem that runs in O(n log n) time with a worst-case performance ratio of 3. We also discuss extension and analysis of the algorithm in d dimensions. More... »

PAGES

129-138

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-1-4613-0259-9_7

DOI

http://dx.doi.org/10.1007/978-1-4613-0259-9_7

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "DasGupta", 
        "givenName": "Bhaskar", 
        "id": "sg:person.0763403270.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002", 
    "datePublishedReg": "2002-01-01", 
    "description": "We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis parallel rectangles such that, for each axis, the projection of a rectangle on this axis does not enclose that of another, and our goal is to select a subset of independent rectangles from the given set of rectangles of total maximum weight, where two rectangles are independent provided for each axis, the projection of one rectangle does not overlap that of another. We use the two-phase technique of [3] to provide a simple approximation algorithm for this problem that runs in O(n log n) time with a worst-case performance ratio of 3. We also discuss extension and analysis of the algorithm in d dimensions.", 
    "editor": [
      {
        "familyName": "Pardalos", 
        "givenName": "Panos M.", 
        "type": "Person"
      }, 
      {
        "familyName": "Principe", 
        "givenName": "Jose", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-1-4613-0259-9_7", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-1-4613-7965-2", 
        "978-1-4613-0259-9"
      ], 
      "name": "Biocomputing", 
      "type": "Book"
    }, 
    "keywords": [
      "simple approximation algorithm", 
      "approximation algorithm", 
      "axis-parallel rectangles", 
      "d dimensions", 
      "worst-case performance ratio", 
      "computational molecular biology", 
      "set of rectangles", 
      "local alignment problem", 
      "parallel rectangles", 
      "rectangle", 
      "maximum weight", 
      "algorithm", 
      "problem", 
      "alignment problem", 
      "performance ratio", 
      "set", 
      "two-phase technique", 
      "projections", 
      "extension", 
      "local alignment", 
      "dimensions", 
      "applications", 
      "axis", 
      "technique", 
      "subset", 
      "analysis", 
      "time", 
      "goal", 
      "ratio", 
      "alignment", 
      "biology", 
      "weight", 
      "molecular biology"
    ], 
    "name": "A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)", 
    "pagination": "129-138", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014062514"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-1-4613-0259-9_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-1-4613-0259-9_7", 
      "https://app.dimensions.ai/details/publication/pub.1014062514"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:01", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_91.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-1-4613-0259-9_7"
  }
]
 

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-1-4613-0259-9_7'

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-1-4613-0259-9_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-0259-9_7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4613-0259-9_7'


 

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

107 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-1-4613-0259-9_7 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N49e017e601e149de8a7e220faabb116d
4 schema:datePublished 2002
5 schema:datePublishedReg 2002-01-01
6 schema:description We consider the following problem motivated by applications to nonoverlapping local alignment problems in computational molecular biology: we are a given a set of n positively weighted axis parallel rectangles such that, for each axis, the projection of a rectangle on this axis does not enclose that of another, and our goal is to select a subset of independent rectangles from the given set of rectangles of total maximum weight, where two rectangles are independent provided for each axis, the projection of one rectangle does not overlap that of another. We use the two-phase technique of [3] to provide a simple approximation algorithm for this problem that runs in O(n log n) time with a worst-case performance ratio of 3. We also discuss extension and analysis of the algorithm in d dimensions.
7 schema:editor N8c338d0b7a04489597037ec97bc5d43f
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N54e75e666e074512a0d5733ec9f24c71
11 schema:keywords algorithm
12 alignment
13 alignment problem
14 analysis
15 applications
16 approximation algorithm
17 axis
18 axis-parallel rectangles
19 biology
20 computational molecular biology
21 d dimensions
22 dimensions
23 extension
24 goal
25 local alignment
26 local alignment problem
27 maximum weight
28 molecular biology
29 parallel rectangles
30 performance ratio
31 problem
32 projections
33 ratio
34 rectangle
35 set
36 set of rectangles
37 simple approximation algorithm
38 subset
39 technique
40 time
41 two-phase technique
42 weight
43 worst-case performance ratio
44 schema:name A Simple Approximation Algorithm for Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles)
45 schema:pagination 129-138
46 schema:productId N5d694b9ca49f48fb89097738394dd261
47 Nf3efe94d0878482686eb2044d14ec4ca
48 schema:publisher N2ff87c76badf4f119b1f639c9e5ec2f4
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014062514
50 https://doi.org/10.1007/978-1-4613-0259-9_7
51 schema:sdDatePublished 2022-10-01T07:01
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N881fa48557e1443aa67ef1c836365229
54 schema:url https://doi.org/10.1007/978-1-4613-0259-9_7
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N2ff87c76badf4f119b1f639c9e5ec2f4 schema:name Springer Nature
59 rdf:type schema:Organisation
60 N46078e6fb71e45ab9e7b5e420d6c5bd1 rdf:first sg:person.0763403270.10
61 rdf:rest rdf:nil
62 N49e017e601e149de8a7e220faabb116d rdf:first sg:person.01274506210.27
63 rdf:rest N46078e6fb71e45ab9e7b5e420d6c5bd1
64 N4c27b1b23b8a4479a6136da702018370 schema:familyName Principe
65 schema:givenName Jose
66 rdf:type schema:Person
67 N54e75e666e074512a0d5733ec9f24c71 schema:isbn 978-1-4613-0259-9
68 978-1-4613-7965-2
69 schema:name Biocomputing
70 rdf:type schema:Book
71 N5d694b9ca49f48fb89097738394dd261 schema:name dimensions_id
72 schema:value pub.1014062514
73 rdf:type schema:PropertyValue
74 N881fa48557e1443aa67ef1c836365229 schema:name Springer Nature - SN SciGraph project
75 rdf:type schema:Organization
76 N8c338d0b7a04489597037ec97bc5d43f rdf:first N95a32ea02e5a4b8c8a993d8db9c1e8ef
77 rdf:rest Nba89fe4dfa02401aad5163d9e726ce96
78 N95a32ea02e5a4b8c8a993d8db9c1e8ef schema:familyName Pardalos
79 schema:givenName Panos M.
80 rdf:type schema:Person
81 Nba89fe4dfa02401aad5163d9e726ce96 rdf:first N4c27b1b23b8a4479a6136da702018370
82 rdf:rest rdf:nil
83 Nf3efe94d0878482686eb2044d14ec4ca schema:name doi
84 schema:value 10.1007/978-1-4613-0259-9_7
85 rdf:type schema:PropertyValue
86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
87 schema:name Mathematical Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
90 schema:name Numerical and Computational Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
93 schema:familyName Berman
94 schema:givenName Piotr
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
96 rdf:type schema:Person
97 sg:person.0763403270.10 schema:affiliation grid-institutes:grid.430387.b
98 schema:familyName DasGupta
99 schema:givenName Bhaskar
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0763403270.10
101 rdf:type schema:Person
102 grid-institutes:grid.29857.31 schema:alternateName Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA
103 schema:name Department of Computer Science & Engineering, Pennsylvania State University, 16802, University Park, PA, USA
104 rdf:type schema:Organization
105 grid-institutes:grid.430387.b schema:alternateName Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
106 schema:name Department of Computer Science, Rutgers University, 08102, Camden, NJ, USA
107 rdf:type schema:Organization
 




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


...