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 in almost linear time
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
2006 (English)Report (Other academic)
Abstract [en]

Given a sequence, the problem studied in this paper is to find a set of k disjoint continuous subsequences such that the total sum of all elements in the set is maximized. This problem arises naturally in the analysis of DNA sequences. The previous best known algorithm requires n log n time in the worst case. For a given sequence of length n, we present an almost linear-time algorithm for this problem. Our algorithm uses a disjoint-set data structure and requires O(n a(n, n) ) time in the worst case, where a(n,n) is the inverse Ackermann function.

Place, publisher, year, edition, pages
Luleå: Luleå tekniska universitet, 2006. , p. 21
Series
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2006:14
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-25447Local ID: f3c6bb30-b210-11db-bf9d-000ea68e967bOAI: oai:DiVA.org:ltu-25447DiVA, id: diva2:998499
Note
Godkänd; 2006; 20070201 (ysko)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-01-10Bibliographically approved

Open Access in DiVA

fulltext(212 kB)126 downloads
File information
File name FULLTEXT01.pdfFile size 212 kBChecksum SHA-512
b2bad5cf1a067f6a7a1b17fe5769c13ea2e9f6d3af76a0584270857752cde50f93be6c0e75d1ab28f1363e178b76a49d1a10d2d41c836701a9ac08ced96352c9
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: 126 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: 258 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