# Fast Algorithms for the Density Finding Problem

Ontology type: schema:ScholarlyArticle

### Article Info

DATE

2007-09-14

AUTHORS ABSTRACT

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a1,w1),(a2,w2),…,(an,wn) of n ordered pairs (ai,wi) of numbers ai and width wi>0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i*,j*) over all O(n2) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑r=ijwr≤u such that its density \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$d(i^{*},j^{*})=\sum_{r=i^{*}}^{j*}a_{r}/w(i^{*},j^{*})$\end{document} is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog 2m) time and O(n+mlog m) space, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m=\min\{\lfloor\frac{u-\ell}{w_{\mathrm{min}}}\rfloor,n\}$\end{document} and wmin=min r=1nwr. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. More... »

PAGES

298-313

TITLE

Algorithmica

ISSUE

3

VOLUME

53

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-007-9023-8

DOI

http://dx.doi.org/10.1007/s00453-007-9023-8

DIMENSIONS

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

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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Information and Computing Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computation Theory and Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan",
"id": "http://www.grid.ac/institutes/grid.28665.3f",
"name": [
"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan",
"Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan"
],
"type": "Organization"
},
"familyName": "Lee",
"givenName": "D. T.",
"id": "sg:person.016673047776.63",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016673047776.63"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan",
"id": "http://www.grid.ac/institutes/grid.28665.3f",
"name": [
"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan",
"Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan"
],
"type": "Organization"
},
"familyName": "Lin",
"givenName": "Tien-Ching",
"id": "sg:person.010166662045.68",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010166662045.68"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan",
"id": "http://www.grid.ac/institutes/grid.19188.39",
"name": [
"Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan"
],
"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"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-45784-4_12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039638112",
"https://doi.org/10.1007/3-540-45784-4_12"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1038/79189",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1027828828",
"https://doi.org/10.1038/79189"
],
"type": "CreativeWork"
}
],
"datePublished": "2007-09-14",
"datePublishedReg": "2007-09-14",
"description": "Abstract\nWe study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a1,w1),(a2,w2),\u2026,(an,wn) of n ordered pairs (ai,wi) of numbers ai and width wi>0 for each 1\u2264i\u2264n, two nonnegative numbers \u2113, u with \u2113\u2264u and a number \u03b4, the Density Finding Problem is to find the consecutive subsequence A(i*,j*) over all O(n2) consecutive subsequences A(i,j) with width constraint satisfying \u2113\u2264w(i,j)=\u2211r=ijwr\u2264u such that its density \n\\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}$d(i^{*},j^{*})=\\sum_{r=i^{*}}^{j*}a_{r}/w(i^{*},j^{*})$\\end{document} \nis closest to \u03b4. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with \u03b4=\u221e. We show that the Density Finding Problem has a lower bound \u03a9(nlog\u2009n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog\u2009n) time and O(nlog\u2009n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog\u20092m) time and O(n+mlog\u2009m) space, where \n\\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}$m=\\min\\{\\lfloor\\frac{u-\\ell}{w_{\\mathrm{min}}}\\rfloor,n\\}$\\end{document} \nand wmin=min\u2009r=1nwr. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-007-9023-8",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
}
],
"keywords": [
"algebraic decision tree model",
"consecutive subsequence",
"finding problem",
"pair of numbers",
"maximum-density segment problem",
"general case",
"biomolecular sequences",
"fast algorithm",
"special case",
"nonnegative numbers",
"number \u03b4",
"space algorithm",
"width constraints",
"algorithm",
"segment problems",
"problem",
"subsequences",
"space",
"tree model",
"computation",
"constraints",
"Wmin",
"number",
"cases",
"model",
"width",
"sequence",
"decision tree model",
"time",
"density",
"pairs",
"byproducts",
"analysis",
"min"
],
"name": "Fast Algorithms for the Density Finding Problem",
"pagination": "298-313",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1026897642"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-007-9023-8"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-007-9023-8",
"https://app.dimensions.ai/details/publication/pub.1026897642"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-10T09:59",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_453.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-007-9023-8"
}
]

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/s00453-007-9023-8'

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/s00453-007-9023-8'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9023-8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9023-8'

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

118 TRIPLES      22 PREDICATES      61 URIs      51 LITERALS      6 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0802
3 schema:author N292970a24d5d440ea613e31523f0876c
4 schema:citation sg:pub.10.1007/3-540-45784-4_12
5 sg:pub.10.1038/79189
6 schema:datePublished 2007-09-14
7 schema:datePublishedReg 2007-09-14
8 schema:description Abstract We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a1,w1),(a2,w2),…,(an,wn) of n ordered pairs (ai,wi) of numbers ai and width wi>0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i*,j*) over all O(n2) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑r=ijwr≤u such that its density \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$d(i^{*},j^{*})=\sum_{r=i^{*}}^{j*}a_{r}/w(i^{*},j^{*})$\end{document} is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog 2m) time and O(n+mlog m) space, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$m=\min\{\lfloor\frac{u-\ell}{w_{\mathrm{min}}}\rfloor,n\}$\end{document} and wmin=min r=1nwr. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem.
9 schema:genre article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N33bdd1024fde40d98987697acf979b2c
13 N87cb6fa15bea48b89533b292648bf1a5
14 sg:journal.1047644
15 schema:keywords Wmin
16 algebraic decision tree model
17 algorithm
18 analysis
19 biomolecular sequences
20 byproducts
21 cases
22 computation
23 consecutive subsequence
24 constraints
25 decision tree model
26 density
27 fast algorithm
28 finding problem
29 general case
30 maximum-density segment problem
31 min
32 model
33 nonnegative numbers
34 number
35 number δ
36 pair of numbers
37 pairs
38 problem
39 segment problems
40 sequence
41 space
42 space algorithm
43 special case
44 subsequences
45 time
46 tree model
47 width
48 width constraints
49 schema:name Fast Algorithms for the Density Finding Problem
50 schema:pagination 298-313
52 Ndcbe91e7528c4559a55ca51903e7eb42
53 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026897642
54 https://doi.org/10.1007/s00453-007-9023-8
55 schema:sdDatePublished 2022-05-10T09:59
57 schema:sdPublisher Nfc91e7c23a6048548e4ff1c20d276908
58 schema:url https://doi.org/10.1007/s00453-007-9023-8
60 sgo:sdDataset articles
61 rdf:type schema:ScholarlyArticle
62 N0cba6ce0072e4b44b5c23af78ac18745 rdf:first sg:person.010166662045.68
63 rdf:rest N171cddd9c3234f64bc122a080e41e891
64 N171cddd9c3234f64bc122a080e41e891 rdf:first sg:person.013345515575.46
65 rdf:rest rdf:nil
66 N292970a24d5d440ea613e31523f0876c rdf:first sg:person.016673047776.63
67 rdf:rest N0cba6ce0072e4b44b5c23af78ac18745
69 rdf:type schema:PublicationVolume
71 schema:value 10.1007/s00453-007-9023-8
72 rdf:type schema:PropertyValue
73 N87cb6fa15bea48b89533b292648bf1a5 schema:issueNumber 3
74 rdf:type schema:PublicationIssue
75 Ndcbe91e7528c4559a55ca51903e7eb42 schema:name dimensions_id
76 schema:value pub.1026897642
77 rdf:type schema:PropertyValue
78 Nfc91e7c23a6048548e4ff1c20d276908 schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:journal.1047644 schema:issn 0178-4617
87 1432-0541
88 schema:name Algorithmica
89 schema:publisher Springer Nature
90 rdf:type schema:Periodical
91 sg:person.010166662045.68 schema:affiliation grid-institutes:grid.28665.3f
92 schema:familyName Lin
93 schema:givenName Tien-Ching
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010166662045.68
95 rdf:type schema:Person
96 sg:person.013345515575.46 schema:affiliation grid-institutes:grid.19188.39
97 schema:familyName Lu
98 schema:givenName Hsueh-I
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345515575.46
100 rdf:type schema:Person
101 sg:person.016673047776.63 schema:affiliation grid-institutes:grid.28665.3f
102 schema:familyName Lee
103 schema:givenName D. T.
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016673047776.63
105 rdf:type schema:Person
106 sg:pub.10.1007/3-540-45784-4_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039638112
107 https://doi.org/10.1007/3-540-45784-4_12
108 rdf:type schema:CreativeWork
109 sg:pub.10.1038/79189 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027828828
110 https://doi.org/10.1038/79189
111 rdf:type schema:CreativeWork
112 grid-institutes:grid.19188.39 schema:alternateName Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
113 schema:name Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
114 rdf:type schema:Organization
115 grid-institutes:grid.28665.3f schema:alternateName Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan
116 schema:name Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan
117 Institute of Information Science, Academia Sinica, 115, Nankang, Taipei, Taiwan
118 rdf:type schema:Organization