國立臺灣大學資訊工程學系Lin, Yaw-LingYaw-LingLinJiang, TaoTaoJiangKUN-MAO CHAO2006-09-272018-07-052006-09-272018-07-05200200220000http://ntur.lib.ntu.edu.tw//handle/246246/20060927122844992215https://www.scopus.com/inward/record.uri?eid=2-s2.0-23844487447&doi=10.1016%2fS0022-0000%2802%2900010-7&partnerID=40&md5=5bf1cc06df273d2067b073569f6b3aa8We study two fundamental problems concerning the search for interesting regions in sequences:(i)given a sequence of real numbers of length n and an upper bound U摯瑬敳獩 find a consecutive subsequence of lengthat most U withth maximum sum and (ii)given a sequence of real numbers of length n and a lower bound L摯瑬敳獩 find a consecutive subsequence of lengthat least L withth maximum average.We present an O摯瑬敳獩 n捡牯渀 ⴀ琀椀洀攀 愀氀最漀爀椀琀栀洀 昀漀爀 琀栀攀⃻Ā爀猀琀 瀀爀漀戀氀攀洀ഀ਀愀渀搀 愀渀 佤潴汥獳椀 渀 氀漀最 䱣慲潮 -time algorithm for the second.The algorithms have potential applications in several areas of biomolecular sequence analysis including locating GC-richregions in a genomic DNA sequence,post-processing sequence alignments,annotating multiple sequence alignments,and computing length-constrained ungapped local alignment.Our preliminary tests on both simulated and real data demonstrate that the algorithms are very ef ficient and able to locate useful (suchas GC-rich)regions.application/pdf313284 bytesapplication/pdfzh-TWAlgorithmEfficiencyMaximum consecutive subsequenceLength constraintBiomolecular sequence analysisUngapped local alignmentjournal article10.1016/S0022-0000(02)00010-72-s2.0-23844487447http://ntur.lib.ntu.edu.tw/bitstream/246246/20060927122844992215/1/2002_jcss.pdf