An Optimal Algorithm for the Maximum-Density Segment Problem

Original · EN

We address a fundamental problem arising from analysis of biomolecular sequences. The input consists of two numbers w and w and a sequence S of n number pairs (aᵢ,wᵢ) with wᵢ>0. Let segment S(i,j) of S be the consecutive subsequence of S between indices i and j. The density of S(i,j) is d(i,j)=(aᵢ+aᵢ₊₁+...+aⱼ)/(wᵢ+wᵢ₊₁+...+wⱼ). The maximum-density segment problem is to find a maximum-density segment over all segments S(i,j) with w≤ wᵢ+wᵢ₊₁+...+wⱼ ≤ w. The best previously known algorithm for the problem, due to Goldwasser, Kao, and Lu, runs in O(n(w-w+1)) time. In the present paper, we solve the problem in O(n) time. Our approach bypasses the complicated right-skew decomposition, introduced by Lin, Jiang, and Chao. As a result, our algorithm has the capability to process the input sequence in an online manner, which is an important feature for dealing with genome-scale sequences. Moreover, for a type of input sequences S representable in O(m) space, we show how to exploit the sparsity of S and solve the maximum-density segment problem for S in O(m) time.