限定長度與平均範圍之區間找尋問題的最佳演算法

Optimal Algorithms for the Interval Location Problem with Range Constraints on Length and Average

謝詠翔(Yong-Hsiang Hsieh)

指導教授 ： 王炳豐

國立清華大學/電機資訊學院/資訊工程學系/博士(2007年)

摘要

無資料

關鍵字

演算法 ； 資料結構 ； 演算法分析 ； 即時演算法

並列摘要

Let A be a sequence of n real numbers, L1 and L2 be two integers such that L1 <= L2 , and R1 and R2 be two real numbers such that R1 <= R2. An interval of A is feasible if its length is between L1 and L2 and its average is between R1 and R2. In this dissertation, we study the following problems: finding all feasible intervals of A, counting all feasible intervals of A, finding a maximum cardinality set of non-overlapping feasible intervals of A, locating a longest feasible interval of A, and locating a shortest feasible interval of A. The problems are motivated from the problem of locating CpG islands of a DNA sequence. Locating CpG islands is important for gene finding as well as for cancer research. In this dissertation, we firstly show that all the problems have an Ω(n log n)-time lower bound in the comparison model. Then, we use geometric approaches to design optimal algorithms for the problems. All the presented algorithms run in an on-line manner and use O(n) space.

並列關鍵字

algorithms ； data structures ； analysis of algorithms ； on-line algorithms

參考文獻

[15] L. J. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees," in Proceedings of the 19th Annual Symposium on Foundations of Computer Science, pp. 8-21, 1978.

[2] L. Allison, "Longest biased interval and longest non-negative sum interval," Bioinformatics, vol. 19, no. 10, pp. 1294-1295, 2003.

[3] F. Antequera, "Structure, function and evolution of CpG island promoters," Cellular and Molecular Life Sciences, vol. 60, no. 8, pp. 1647-1658, 2003.

[4] F. Antequera and A. Bird, "Number of CpG islands and genes in human and mouse," in Proceedings of the National Academy of Sciences of the United States of America, vol. 90, no. 24, pp. 11995-11999, 1993.

[5] R. Bayer, "Symmetric binary B-trees: data structure and maintenance algorithms," Acta Informatica, vol. 1, pp. 290-306, 1972.