Computing maximum-scoring segments in almost linear time
2006 (English)Report (Other academic)
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. , 21 p.
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2006:14
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-25447Local ID: f3c6bb30-b210-11db-bf9d-000ea68e967bOAI: oai:DiVA.org:ltu-25447DiVA: diva2:998499
Godkänd; 2006; 20070201 (ysko)2016-09-292016-09-29Bibliographically approved