對一個有n個元素且每個元素si皆伴隨著一value-weight pair (vali, wi) 的序列S = s1, s2, …, sn，以及一棵有n個點且每個點v也伴隨著一value-weight pair (valv, wv) 的樹T = (V,E)，vali和valv為實數，wi和wv為非負的整數。子序列的長度定義為其所含元素的個數。令V(S)並且W(S)，此序列之密度定義為。樹T之密度定義為。給定一個序列，藉由刪除原序列某些元素且不破壞剩下元素的相對位置而成的序列為其子序列。給予兩整數wmin及wmax，則限重最大密度子序列問題為在序列S中尋找一子序列S’密度為最大且滿足wmin W(S’) wmax。給予一整數L，則限長最大密度子序列問題為在序列S中尋找一子序列S’長度至少L。本論文中，我們首先展示一O(wmaxn2)時間演算法在序列中尋找一限重最大密度子序列，接著展示一O(W(S)Ln2)時間演算法在序列中尋找一限長最大密度子序列。最後，同時在限重和限長下，我們展示一O(wmaxLn2)時間演算法在序列S中尋找一最大密度子序列和一個O(wmaxLn)時間演算法在樹中找一最大密度路徑。

Given a sequence of n elements S = <s1, s2, ..., sn> and a tree T = (V,E) of n vertices such that each element si and each node v are

both associated with a value-weight pair (vali,wi) for i = 1, 2; ..., n and (valv,wv), where value vali and valv are real numbers and

weight wi and wv are positive integers. The length of a sequence is the number of its elements. Let V(S) = Pni=1 vali and W(S) =

Pni=1 wi. The density of S, denoted by d(S), is denoted as V(S)/W(S) . The density of T, denoted by d(T), is denoted as §v2V valv

§v2V wv. A subsequence of a given sequence is a sequence formed from the given sequence by deleting some of the elements

without disturbing the relative positions of the remaining elements. Given two weight-bounded integers wmin and wmax, the weight-

constrained maximum-density subsequence problem is to find a maximum-density subsequence S0 satisfying wmin · W(S0) · wmax.

Given one length-bounded integer L, the length-constrained maximum-density subsequence problem is to find a maximum-density

subsequence of length at least L. In this paper, we present a O(wmaxn2)-time algorithm to solve the weight-constrained maximum-

density subsequence problem, and then present a O(W(S)Ln2)-time algorithm to solve the length-constrained maximum-density

subsequence problem. Finally, we present a O(wmaxLn2)-time algorithm to find a maximum-density subsequence in a given

sequence and find a maximum-density path in a tree in O(wmaxLn)-time under both the weight-constraint and the length-constraint.

[1] 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.
[2] 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.
[3] 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 gelelectrophoresis, ”NucleicAcidsResearch,26:1548–1549,1998.
[4] W. Henke, K. Herdel, K. Jung, D. Schnorr, and S. A. Loening, “Betaine improves the PCR amplification of GC-rich DNA

sequences, ”NucleicAcidsResearch,25:3957–3958,1997.
[5] 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.
[6] 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.
[7] R. B. Inman, “A denaturation map of the 1 phage DNA molecule determined by electron microscopy,”Journal of Molecular

Biology, 18:464–476, 1966.
[8] 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-rich cruciform?, ”The EMBO Journal, 16:4456–4466, 1997.
[9] S. K. Kim, “Linear-time algorithm for finding a maximum-density segment of a sequence, ”Information Processing Letters, 86

(6):339–342, 2003.
[10] 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.
[11] Y. L. Lin, T. Jiang, and K. M. Chao, “Algorithms for locating the length-constrained heaviest segments, with aplications to

biomolecular sequences analysis, ”Journal of Computer and System Sciences, 65(3):570–586, 2002.
[12] 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.
[13] 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.
[14] A. Nekrutenko and W. H. Li, “Assesment of compositional heterogeneity within and between eukaryotic genomes, ”Genome

Research, 10:1986–1995, 2000.
[15] P. Rice, I. Longden, and A. Bleasby, “EMBOSS: The European molecular biology open software suite, ”Trends in Genetics,

16(6):276–277, 2000.
[16] W. Smyth, Computing Patterns in Strings, Pearson-Addison Wesley, 2003.
[17] 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.
[18] D. B. West, Introduction to Graph Theory, 2nd ed, Prentice Hall, Upper Saddle River, NJ, 2001.
[19] 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.