@inproceedings{86c18ebf5e5148b0ac03cf3888c52a1f,

title = "An optimal algorithm for maximum-sum segment and its application in bioinformatics extended abstract",

abstract = "We study a fundamental sequence algorithm arising from bioinformatics. Given two integers L and U and a sequence A of n numbers, the maximum-sum segment problem is to find a segment A[i, j] of A with L ≤ j−i+1 ≤ U that maximizes A[i]+A[i+1]+• • •+A[j]. The problem finds applications in finding repeats, designing low complexity filter, and locating segments with rich C+G content for biomolecular sequences. The best known algorithm, due to Lin, Jiang, and Chao, runs in O(n) time, based upon a clever technique called left-negative decomposition for A. In the present paper, we present a new O(n)-time algorithm that bypasses the left-negative decomposition. As a result, our algorithm has the capability to handle the input sequence in an online manner, which is clearly an important feature to cope with genome-scale sequences. We also show how to exploit the sparsity in the input sequence: If A is representable in O(k) space in some format, then our algorithm runs in O(k) time. Moreover, practical implementation of our algorithm running on the rice genome helps us to identify a very long repeat structure in rice chromosome 1 that is previously unknown.",

author = "Fan, {Tsai Hung} and Shufen Lee and Lu, {Hsueh I.} and Tsou, {Tsung Shan} and Wang, {Tsai Cheng} and Adam Yao",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2003.; 8th International Conference on Implementation and Application of Automata, CIAA 2003 ; Conference date: 16-07-2003 Through 18-07-2003",

year = "2003",

language = "???core.languages.en_GB???",

isbn = "3540405615",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "239--250",

editor = "Ibarra, {Oscar H.} and Zhe Dang",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}