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-08-04T17:16", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_21.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 Nd86d3c1dbd1d4ed69ff236c176454174
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 Nddd516d83e8f464c95888a14104a8b54
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Nb0d56839dbad4b9c93eb221e6209a4f6
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 N66f912323aa247d0abca7ec73384cee1
47 N86a977a609034f56b7741d81537c1078
48 schema:publisher Nb7b02f688eb04fa7911e6fd8797b7c67
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-08-04T17:16
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N73d05f2aed084f9791a0432dbfc6493b
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 N2749fcd34c844a91b56b371662849711 schema:familyName Principe
59 schema:givenName Jose
60 rdf:type schema:Person
61 N3dc328bdce8741d883d13ecc9bd6acd3 rdf:first sg:person.0763403270.10
62 rdf:rest rdf:nil
63 N552505a47b0249ffaf8f5df24416a200 schema:familyName Pardalos
64 schema:givenName Panos M.
65 rdf:type schema:Person
66 N66f912323aa247d0abca7ec73384cee1 schema:name doi
67 schema:value 10.1007/978-1-4613-0259-9_7
68 rdf:type schema:PropertyValue
69 N73d05f2aed084f9791a0432dbfc6493b schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 N86a977a609034f56b7741d81537c1078 schema:name dimensions_id
72 schema:value pub.1014062514
73 rdf:type schema:PropertyValue
74 N8eb9d7b3ab02419daa733531718f05d8 rdf:first N2749fcd34c844a91b56b371662849711
75 rdf:rest rdf:nil
76 Nb0d56839dbad4b9c93eb221e6209a4f6 schema:isbn 978-1-4613-0259-9
77 978-1-4613-7965-2
78 schema:name Biocomputing
79 rdf:type schema:Book
80 Nb7b02f688eb04fa7911e6fd8797b7c67 schema:name Springer Nature
81 rdf:type schema:Organisation
82 Nd86d3c1dbd1d4ed69ff236c176454174 rdf:first sg:person.01274506210.27
83 rdf:rest N3dc328bdce8741d883d13ecc9bd6acd3
84 Nddd516d83e8f464c95888a14104a8b54 rdf:first N552505a47b0249ffaf8f5df24416a200
85 rdf:rest N8eb9d7b3ab02419daa733531718f05d8
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)


...