Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications

Original · EN

We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (aᵢ,wᵢ) for i = 1,..,n and wᵢ>0, a segment A(i,j) is a consecutive subsequence of A starting with index i and ending with index j. The width of A(i,j) is w(i,j) = sumᵢ <₌ ₖ <₌ ⱼ wₖ, and the density is (sumᵢ<₌ ₖ <₌ ⱼ aₖ)/ w(i,j). The maximum-density segment problem takes A and two values L and U as input and asks for a segment of A with the largest possible density among those of width at least L and at most U. When U is unbounded, we provide a relatively simple, O(n)-time algorithm, improving upon the O(n L)-time algorithm by Lin, Jiang and Chao. When both L and U are specified, there are no previous nontrivial results. We solve the problem in O(n) time if wᵢ=1 for all i, and more generally in O(n+n(U-L+1)) time when wᵢ>=1 for all i.