Computing maximum-scoring segments optimally
2007 (English)Report (Other academic)
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. , 10 p.
Research report / Luleå University of Technology, ISSN 1402-1528 ; 2007:3
Research subject Dependable Communication and Computation Systems
IdentifiersURN: urn:nbn:se:ltu:diva-22852Local ID: 48a93dc0-5d75-11dc-8151-000ea68e967bOAI: oai:DiVA.org:ltu-22852DiVA: diva2:995901
Godkänd; 2007; 20070907 (ysko)2016-09-292016-09-29Bibliographically approved