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

Simple item page
dc.creatorGoldwasser, Michael H.
dc.creatorKao, Ming-Yang
dc.creatorLu, Hsueh-I
dc.date2002-07-08
dc.date2002-11-04
dc.date.accessioned2026-07-07T03:18:37Z
dc.date.available2026-07-07T03:18:37Z
dc.descriptionWe study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (a_i,w_i) for i = 1,..,n and w_i>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_{i <= k <= j} w_k, and the density is (sum_{i<= k <= j} a_k)/ 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 \log 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_i=1 for all i, and more generally in O(n+n\log(U-L+1)) time when w_i>=1 for all i.
dc.description23 pages, 13 figures. A significant portion of these results appeared under the title, "Fast Algorithms for Finding Maximum-Density Segments of a Sequence with Applications to Bioinformatics," in Proceedings of the Second Workshop on Algorithms in Bioinformatics (WABI), volume 2452 of Lecture Notes in Computer Science (Springer-Verlag, Berlin), R. Guigo and D. Gusfield editors, 2002, pp. 157--171
dc.identifierhttps://arxiv.org/abs/cs/0207026
dc.identifierhttp://arxiv.org/abs/cs/0207026
dc.identifierJournal of Computer and System Sciences, 70(2):128-144, 2005
dc.identifierdoi:10.1016/j.jcss.2004.08.001
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31183
dc.subjectData Structures and Algorithms
dc.subjectDiscrete Mathematics
dc.subjectF.2.2; J.3; G.2
dc.titleLinear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications
dc.typetext

Files

Collections

arXiv