https://scholars.lib.ntu.edu.tw/handle/123456789/118291
標題: | Linear-Time Algorithms for Computing Maximum-Density Sequence Segments with Bioinformatics Applications | 作者: | Goldwasser, Michael H. Kao, Ming-Yang Lu, Hsueh-I |
關鍵字: | Bioinformatics; Density; Sequences | 公開日期: | 2005 | 起(迄)頁: | 128-144 | 來源出版物: | Journal of Computer and System Sciences | 摘要: | We study an abstract optimization problem arising from biomolecular sequence analysis. For a sequence A of pairs (ai,wi) for i=1,...,n and wi>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)=∑i≤k≤jwk, and the density is (∑i≤k≤jak)/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(nlogL)-time algorithm by Lin, Jiang and Chao. We then extend this result, providing an O(n)-time algorithm for the case when both L and U are specified. © 2004 Elsevier Inc. All rights reserved. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-15744368022&doi=10.1016%2fj.jcss.2004.08.001&partnerID=40&md5=2c4fc9d5884e29630269d18cb407871c | DOI: | 10.1016/j.jcss.2004.08.001 |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。