An optimal algorithm for maximum-sum segment and its application in bioinformatics extended abstract

Tsai Hung Fan, Shufen Lee, Hsueh I. Lu, Tsung Shan Tsou, Tsai Cheng Wang, Adam Yao

研究成果: 書貢獻/報告類型會議論文篇章同行評審

摘要

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.

原文???core.languages.en_GB???
主出版物標題Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
編輯Oscar H. Ibarra, Zhe Dang
發行者Springer Verlag
頁面239-250
頁數12
ISBN(列印)3540405615
出版狀態已出版 - 2003
事件8th International Conference on Implementation and Application of Automata, CIAA 2003 - Santa Barbara, United States
持續時間: 16 7月 200318 7月 2003

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
2759
ISSN(列印)0302-9743
ISSN(電子)1611-3349

???event.eventtypes.event.conference???

???event.eventtypes.event.conference???8th International Conference on Implementation and Application of Automata, CIAA 2003
國家/地區United States
城市Santa Barbara
期間16/07/0318/07/03

指紋

深入研究「An optimal algorithm for maximum-sum segment and its application in bioinformatics extended abstract」主題。共同形成了獨特的指紋。

引用此