Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computing maximum-scoring segments optimally
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2007 (English)Report (Other academic)
Abstract [en]

Given a sequence of length n, the problem studied in this report is to find a set of k disjoint subsequences of consecutive elements such that the total sum of all elements in the set is maximized. This problem arises in the analysis of DNA sequences. The previous best known algorithm requires time proportional to n times the inverse Ackermann function of (n,n), in the worst case. We present a linear-time algorithm, which is optimal, for this problem.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2007. , p. 10
Series
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2007:3
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-22852Local ID: 48a93dc0-5d75-11dc-8151-000ea68e967bOAI: oai:DiVA.org:ltu-22852DiVA, id: diva2:995901
Note
Godkänd; 2007; 20070907 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

fulltext(174 kB)565 downloads
File information
File name FULLTEXT01.pdfFile size 174 kBChecksum SHA-512
a5295f0cad697093db190960993dcffc276fdf4972fa78eb43d3b7a8d0891af8ff6debcbefb0e01191049fa1587b0761bec4e2e89eb657be015fe8eac929e77a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Bengtsson, FredrikChen, Jingsen
By organisation
Computer Science
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 565 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 300 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf