令T=(V, E)為一棵有n個點的樹，且對於任意一條邊e皆伴隨著一數對(v(e), w(e))，其中v(e)為一實數代表e的值，而w(e)為一正整數代表e的權重。給定兩個整數wmin和wmax與兩個實數dmin和dmax，若一條路徑P其權重落在wmin和wmax之間且密度落在dmin和dmax之間，則我們稱之為「可行路徑」。本論文中，我們首先展示一O(nlog2n+h)-time演算法在樹中尋找所有可行路徑，其中h為輸出大小。接著我們展示一O(nlog2n)-time演算法在樹中計算所有可行路徑的個數。最後，我們展示一O(nlog2n+h)-time演算法找出所有可行路徑中，密度為前k大的路徑。

Let $T = (V, E)$ be a tree of $n$ nodes in which each edge $e in E$ is associated with a pair $(v(e), w(e))$, where $v(e)$ is a real number that represents the {em value} of $e$ and $w(e)$ is a positive integer that represents the {em weight} of $e$. Given two integers $w_{min}$ and $w_{max}$ and two real numbers $d_{min}$ and $d_{max}$, a path $P = (v_{0}, e_{1}, v_{1},..., e_{k}, v_{k})$ is {em feasible} if $w_{min} leq sum_{i=1}^{k}w(e_{i}) leq w_{max}$ and $d_{min} leq sum_{i=1}^{k}v(e_{i})/sum_{i=1}^{k}w(e_{i}) leq d_{max}$.
In this thesis, we first present an $O(nlog^{2}n + h)$-time algorithm to find all feasible paths in a tree, where $h$ is the output size. Then, we present an $O(nlog^{2}n)$-time algorithm to count the number of all feasible paths in a tree. Finally, we present an $O(nlog^{2}n + h)$-time algorithm to find the $k$ feasible paths such that their densities are the $k$ largest over all feasible paths.

L. Allison. Longest biased interval and longest non-negative sum interval. Bioinformatics, 19(10):1294--1295, 2003.

F. Antequera. Structure, function and evolution of cpg island promoters. Cellular and Molecular Life Sciences, 60(8):1647--1658, 2003.

F. Antequera and A. Bird. Number of cpg islands and genes in human and mouse. In Proceedings of the National Academy of Science of the United States of America, volume 90, pages 11995--11999, 1993.

S. E. Bae and T. Takaoka. Algorithms for the problem of k maximum sums and a vlsi algorithm for the k maximum subarrays problem. In International Symposium on Parallel Architectures, Algorithms and Networks, pages 247--253, 2004.

S. E. Bae and T. Takaoka. Improved algorithms for the k-maximum subarray problem. The Computer Journal, 49(3):358--374, 2006.

F. Bengtsson and J. Chen. Efficient algorithms for k maximum sums. Algorithmica, 46:27--41, 2006.

A. Bergkvist and P. Damaschke. Fast algorithms for finding disjoint subsequences with extremal densities. Pattern Recognition, 39:2281--2292, 2006.

G. S. Brodal and A. G. Jorgensen. A linear time algorithm for the k maximal sums problem. In Proceedings of the 32nd International Symposium on Mathematical Foundations of Computer Science, volume 4708 of Lecture Notes in Computer Science, pages 442--453. Springer Verlag, Berlin, 2007.

K. M. Chao. On computing all suboptimal alignments. Information Sciences, pages 189--207, 1998.

K. M. Chao, R. C. Hardison, and W. Miller. Recent developments in linear-space alignment methods: a survey. Journal of Computational Biology, pages 271--291, 1994.

K. Y. Chen and K. M. Chao. Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint. Information Processing Letters, 96(6):197--201, 2005.

Y. H. Chen, H. I. Lu, and C. Y. Tang. Disjoint segments with maximal density. In Proceedings of the International Conference on Computational Science, volume 3515 of Lecture Notes in Computer Science, pages 845--850, 2005.

C. H. Cheng, K. Y. Chen, W. C. Tien, , and K. M. Chao. Improved algorithms for the k maximum-sums problems. Theoretical computer science, 362:162--170, 2006.

C. S. Cheng and S. Y. Hsieh. The maximum-density subsequence problem and related problems, 2006.

K. M. Chung and H. I. Lu. An optimal algorithm for the maximum-density segment problem. SIAM Journal on Computing, 34(2):373--387, 2004.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. MIT Press, Cambridge, MA, second edition, 2002.

C. A. Crane. Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Dept. of Computer Science, Stanford University, CA, USA, 1972.

R. Durbin, S. Eddy, A. Krogh, and G. Mitchison. Biological Sequence Analysis: Probabilitic Models of Proteins and Nucleic Acids. Cambridge University Press, 1998.

I. Eidhammer, I. Jonassen, and W. R. Taylor. Protein Bioinformatics: An Algorithmic Approach to Sequence and Structure Analysis. Wiley, 2004.

M. Esteller. CpG island hypermethylation and tumer suppressor genes: a booming present, a brighter future. Oncogene, 21(35):5427--5440, 2002.

T. H. Fan, S. Lee, H. I. Lu, T. S. Tsou, T. C. Wang, and A. Yao. An optimal algorithm for maximum-sum segment and its application in bioinformatics. In Eighth International Conference on Implementation and Application of Automata, pages 251--257, 2003.

P. Fariselli, M. Finelli, M. Marchignoli, P. L. Martelli, I. Rossi, and R. Casadio. MaxSubSeq: An algorithm for segment-length optimization. The case study of the transmembrane spanning segments. Bioinformatics, 19:500--505, 2003.

G. N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104(2):197--214, 1993.

M. H. Goldwasser, M. Y. Kao, and H. I. Lu. Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. Journal of Computer and System Sciences, 70(2):128--144, 2005.

P. Guldberg, K. Gronbak, A. Aggerholm, A. Platz, P. T. Straten, V. Ahrenkiel, P. Hokland, and J. Zeuthen. Detection of mutations in GC-rich dna by bisulphite denaturing gradient gel electrophoresis. Nucleic Acids Research, 26:1548--1549, 1998.

W. Henke, K. Herdel, K. Jung, D. Schnorr, and S. A. Loening. Betaine improves the pcr amplification of gc-rich dna sequences.
Nucleic Acids Research, 25:3957--3958, 1997.

E. Horowitz, S. Sahni, and D. Mehta. Fundamentals of Data Structures in C++. Computer Science Press, 2002.

S. Y. Hsieh and C. S. Cheng. Finding a maximum-density path in a tree under the weight and length constraints. Information Processing Letters, 105:202--205, Feb. 2008.

S. Y. Hsieh and T. Y. Chou. Finding a weight-constrained maximum-density subtree in a tree. In Proceedings of the 16th International Symposium on Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, pages 944--953, 2005.

Y. H. Hsieh, C. C. Yu, and B. F. Wang. Optimal algorithms for the interval location problem with range constraints on length and average. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2007. accepted.

X. Huang. An algorithm for identifying regions of a dna sequence that satisfy a content requirement. Computer Applications in the Biosciences, 10(3):219--225, 1994.

K. Ikehara, F. Amada, S. Yoshida, Y. Mikata, and A. Tanaka. A possible origin of newly born bacterial genes: significance of GC-rich nonstop frame on antisense strand. Nucleic Acids Research, 24:4249--4255, 1996.

R. B. Inman. A denaturation map of the 1 phage dna molecule determined by electron microscopy. Journal of Molecular Biology, 18:464--476, 1966.

I. P. Ioshikhes and M. Q. Zhang. Large-scale human promoter mapping using cpg islands. Nature Genetics, 26:61--63, 2000.

R. Jin, M. E. Fernandez-Beros, and R. P. Novick. Why is the initiation nick site of an at-rich rolling circle plasmid at the tip of a gc-richcruciform? The EMBO Journal, 16:4456--4466, 1997.

N. C. Jones and P. A. Pevzner. An Introduction to Bioinformatics Algorithms. MIT Press, Cambridge, MA, 2004.

S. K. Kim. Linear-time algorithm for finding a maximum density segment of a sequence. Information Processing Letters, 86(6):339--342, 2003.

S. K. Kim. Finding a longest nonnegative path in a constant degree tree. Information Processing Letters, 93:275--279, 2005.

D. E. Knuth. The art of computer programming, volumn 3: sorting and searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, second edition, 1998.

H. C. Lau, T. H. Ngo, and B. N. Nguyen. Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics. Discrete Optimization, 3:385--391, 2006.

D. T. Lee, T. C. Lin, and H. I. Lu. Fast algorithms for the density finding problem. Algorithmica, 2007.

A. M. Lesk. Introduction to Protein Architecture. Oxford University Press, 2003.

B. Lewin. Genes VIII. Pearson Prentice Hall, Upper Saddle River, 2004.

R. R. Lin, W. H. Kuo, and K. M. Chao. Finding a length-constrained maximum-density path in a tree. Journal of Combinatorial Optimization, 9(2):147--156, 2005.

T. C. Lin and D. T. Lee. Algorithmic studies of sequence manipulation and related problems. PhD thesis, National Taiwan University, Taiwan, 2007.

Y. L. Lin, X. Huang, T. Jiang, and K. M. Chao. MAVG: Locating non-overlapping maximum average segments in a given sequence.
Bioinformatics, 19(1):151--152, 2003.

Y. L. Lin, T. Jiang, and K. M. Chao. Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. Journal of Computer and System Sciences, 65(3):570--586, 2002.

H. F. Liu and K. M. Chao. On locating disjoint segments with maximum sum of densities. Algorithmica, 2007. accepted.

G. Macaya, J. P. Thiery, and G. Bernardi. An approach to the organization of eukaryotic genomes at a macromolecular level. Journal of Molecular Biology, 108:237--254, 1976.

E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257--276, 1985.

C. Miklos. Maximum-scoring segment sets. IEEE/ACM Transations on Computatonal Biology and Bioinformatics, 1(4):139--150, 2004.

A. Nekrutenko and W. H. Li. Assessment of compositional heterogeneity within and between eukaryotic genomes.
Genome Research, 10:1986--1995, 2000.

D. L. Nelson and M. M. Cox. Lehninger Principles of Biochemistry. Freeman, fourth edition, 2004.

P. Rice, I. Longden, and A. Bleasby. EMBOSS: The european molecular biology open software suite. Trend in Genetics, 16(6):276--277, 2000.

D. D. Sleator and R. E. Tarjan. Self-adjusting heaps. SIAM Journal on Computing, 15(1):52--69, 1986.

W. Smyth. Computing Patterns in Strings. Pearson-Addison Wesley, 2003.

N. Stojanovic, L. Florea, C. Riemer, D. Gumucio, J. Slightom, M. Goodman, W. Miller, and R. Hardison. Comparison of five methods for finding conserved sequences in multiple alignments of gene regulatory regions. Nucleic Acids Research, 27:3899--3910, 1999.

H. H. Su, C. L. Lu, and C. Y. Tang. An improved algorithm for finding a length-constrained maximum-density subtree in a tree.
Proceedings of the 25th Workshop on Combinatorial Mathematics and Computational Theory, pages 146--150, 2008.

L. Wang and Y. Xu. SEGID: Identifying interesting segments in (multiple) sequence alignments. Bioinformatics, 19(2):297--298, 2003.

D. B. West. Introduction to Graph Theory. Prentice Hall, Upper Saddle River, NJ, second edition, 2001.

J. W. J. Williams. ACM Algorithm 232: Heapsort. Communications of the ACM, 7(6):347--348, June 1964.

B. Y. Wu, K. M. Chao, and C. Y. Tang. An efficient algorithm for the length-constrained heaviest path problem on a tree. Information Processing Letters, 69:63--67, 1999.