An Optimal Algorithm for the Maximum-Density Segment Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2003

AUTHORS

Kai-min Chung , Hsueh-I Lu

ABSTRACT

We address a fundamental string problem arising from analysis of biomolecular sequences. The input consists of two integers L and U and a sequence S of n number pairs (ai,wi) with wi > 0. Let segmentS(i,j) of S be the consecutive subsequence of S starting index i to index j. The density of S(i,j) is d(i,j) = (ai + ai + 1 + ... + aj)/(wi + wi + 1 + ... + wj). The maximum-density segment problem is to find a maximum-density segment over all segments of S with L ≤ wi + wi + 1 + ... + wj ≤ U. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in O(n log(U − L + 1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for an input sequence S representable in O(k) space, we also show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(k) time. More... »

PAGES

136-147

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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. Computer Science & Information Engineering, National Taiwan University, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.19188.39", 
          "name": [
            "Dept. Computer Science & Information Engineering, National Taiwan University, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chung", 
        "givenName": "Kai-min", 
        "id": "sg:person.015157715672.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, 128 Academia Road, Sec. 2, 115, Taipei, Taiwan, Republic of China", 
          "id": "http://www.grid.ac/institutes/grid.28665.3f", 
          "name": [
            "Institute of Information Science, Academia Sinica, 128 Academia Road, Sec. 2, 115, Taipei, Taiwan, Republic of China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lu", 
        "givenName": "Hsueh-I", 
        "id": "sg:person.013345515575.46", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003", 
    "datePublishedReg": "2003-01-01", 
    "description": "We address a fundamental string problem arising from analysis of biomolecular sequences. The input consists of two integers L and U and a sequence S of n number pairs (ai,wi) with wi\u2009>\u20090. Let segmentS(i,j) of S be the consecutive subsequence of S starting index i to index j. The density of S(i,j) is d(i,j)\u2009=\u2009(ai\u2009+\u2009ai\u2009+\u20091\u2009+\u2009...\u2009+\u2009aj)/(wi\u2009+\u2009wi\u2009+\u20091\u2009+\u2009...\u2009+\u2009wj). The maximum-density segment problem is to find a maximum-density segment over all segments of S with L\u2009\u2264\u2009wi\u2009+\u2009wi\u2009+\u20091\u2009+\u2009...\u2009+\u2009wj\u2009\u2264\u2009U. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in O(n log(U\u2009\u2212\u2009L\u2009+\u20091)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for an input sequence S representable in O(k) space, we also show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(k) time.", 
    "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_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-20064-2", 
        "978-3-540-39658-1"
      ], 
      "name": "Algorithms - ESA 2003", 
      "type": "Book"
    }, 
    "keywords": [
      "maximum-density segment problem", 
      "sequence S", 
      "biomolecular sequences", 
      "optimal algorithm", 
      "string problem", 
      "integer L", 
      "consecutive subsequence", 
      "segment problems", 
      "number pairs", 
      "input sequence", 
      "problem", 
      "algorithm", 
      "online manner", 
      "present paper", 
      "genome-scale sequences", 
      "chaos", 
      "important features", 
      "sparsity", 
      "index I", 
      "space", 
      "subsequences", 
      "Goldwasser", 
      "decomposition", 
      "Lin", 
      "Jiang", 
      "input", 
      "WJ", 
      "Lu", 
      "sequence", 
      "density", 
      "time", 
      "approach", 
      "pairs", 
      "Kao", 
      "results", 
      "capability", 
      "analysis", 
      "features", 
      "segments", 
      "manner", 
      "paper"
    ], 
    "name": "An Optimal Algorithm for the Maximum-Density Segment Problem", 
    "pagination": "136-147", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1021848210"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-39658-1_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-39658-1_15", 
      "https://app.dimensions.ai/details/publication/pub.1021848210"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "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_360.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-39658-1_15"
  }
]
 

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_15'

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_15'

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_15'

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_15'


 

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

116 TRIPLES      23 PREDICATES      67 URIs      60 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-39658-1_15 schema:about anzsrc-for:01
2 anzsrc-for:0102
3 schema:author Nd41c3d76d8e14bf4ab889343bd29fa57
4 schema:datePublished 2003
5 schema:datePublishedReg 2003-01-01
6 schema:description We address a fundamental string problem arising from analysis of biomolecular sequences. The input consists of two integers L and U and a sequence S of n number pairs (ai,wi) with wi > 0. Let segmentS(i,j) of S be the consecutive subsequence of S starting index i to index j. The density of S(i,j) is d(i,j) = (ai + ai + 1 + ... + aj)/(wi + wi + 1 + ... + wj). The maximum-density segment problem is to find a maximum-density segment over all segments of S with L ≤ wi + wi + 1 + ... + wj ≤ U. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in O(n log(U − L + 1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for an input sequence S representable in O(k) space, we also show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(k) time.
7 schema:editor N4db3abfdad8542caa27576f7dab3280a
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N3f801c3ba2ed4761aba7b7d845facf05
12 schema:keywords Goldwasser
13 Jiang
14 Kao
15 Lin
16 Lu
17 WJ
18 algorithm
19 analysis
20 approach
21 biomolecular sequences
22 capability
23 chaos
24 consecutive subsequence
25 decomposition
26 density
27 features
28 genome-scale sequences
29 important features
30 index I
31 input
32 input sequence
33 integer L
34 manner
35 maximum-density segment problem
36 number pairs
37 online manner
38 optimal algorithm
39 pairs
40 paper
41 present paper
42 problem
43 results
44 segment problems
45 segments
46 sequence
47 sequence S
48 space
49 sparsity
50 string problem
51 subsequences
52 time
53 schema:name An Optimal Algorithm for the Maximum-Density Segment Problem
54 schema:pagination 136-147
55 schema:productId N4c27f1ad90954fa0bdb451a7d05c21b6
56 Nfe5cb51236854c1095c7226d00dd4fb1
57 schema:publisher N741867ba5b1046c1b89d3627f47cb8d8
58 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021848210
59 https://doi.org/10.1007/978-3-540-39658-1_15
60 schema:sdDatePublished 2022-05-20T07:46
61 schema:sdLicense https://scigraph.springernature.com/explorer/license/
62 schema:sdPublisher N59f62bc55e7b4c6c924062470bf8bd34
63 schema:url https://doi.org/10.1007/978-3-540-39658-1_15
64 sgo:license sg:explorer/license/
65 sgo:sdDataset chapters
66 rdf:type schema:Chapter
67 N3f801c3ba2ed4761aba7b7d845facf05 schema:isbn 978-3-540-20064-2
68 978-3-540-39658-1
69 schema:name Algorithms - ESA 2003
70 rdf:type schema:Book
71 N4c27f1ad90954fa0bdb451a7d05c21b6 schema:name doi
72 schema:value 10.1007/978-3-540-39658-1_15
73 rdf:type schema:PropertyValue
74 N4db3abfdad8542caa27576f7dab3280a rdf:first Nd3f59525df004c968cc856c81774793d
75 rdf:rest N847d14b0fbe348ebbffe8c182fa3332e
76 N59f62bc55e7b4c6c924062470bf8bd34 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N64c9175156ac450cb07e4d1632e1d51e rdf:first sg:person.013345515575.46
79 rdf:rest rdf:nil
80 N741867ba5b1046c1b89d3627f47cb8d8 schema:name Springer Nature
81 rdf:type schema:Organisation
82 N847d14b0fbe348ebbffe8c182fa3332e rdf:first Nae38fb3208cc4375b7e30b9104e17750
83 rdf:rest rdf:nil
84 Nae38fb3208cc4375b7e30b9104e17750 schema:familyName Zwick
85 schema:givenName Uri
86 rdf:type schema:Person
87 Nd3f59525df004c968cc856c81774793d schema:familyName Di Battista
88 schema:givenName Giuseppe
89 rdf:type schema:Person
90 Nd41c3d76d8e14bf4ab889343bd29fa57 rdf:first sg:person.015157715672.30
91 rdf:rest N64c9175156ac450cb07e4d1632e1d51e
92 Nfe5cb51236854c1095c7226d00dd4fb1 schema:name dimensions_id
93 schema:value pub.1021848210
94 rdf:type schema:PropertyValue
95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
96 schema:name Mathematical Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0102 schema:inDefinedTermSet anzsrc-for:
99 schema:name Applied Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.28665.3f
102 schema:familyName Lu
103 schema:givenName Hsueh-I
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
105 rdf:type schema:Person
106 sg:person.015157715672.30 schema:affiliation grid-institutes:grid.19188.39
107 schema:familyName Chung
108 schema:givenName Kai-min
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30
110 rdf:type schema:Person
111 grid-institutes:grid.19188.39 schema:alternateName Dept. Computer Science & Information Engineering, National Taiwan University, Taiwan
112 schema:name Dept. Computer Science & Information Engineering, National Taiwan University, Taiwan
113 rdf:type schema:Organization
114 grid-institutes:grid.28665.3f schema:alternateName Institute of Information Science, Academia Sinica, 128 Academia Road, Sec. 2, 115, Taipei, Taiwan, Republic of China
115 schema:name Institute of Information Science, Academia Sinica, 128 Academia Road, Sec. 2, 115, Taipei, Taiwan, Republic of China
116 rdf:type schema:Organization
 




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


...