臺灣博碩士論文加值系統

在這篇論文裡，我們要探討具限制性之最長共同子序列問題。問題的定義如下：
給定兩條序列X、Y 及一條限制序列Z，我們要找出一條X 和Y 的最長共同序列P，
而且，Z 必須是P 的一個子序列。子序列P 就被稱做是X、Y 和Z 的最長共同子序列。
Chin 及另外四位作者在2004 年發表了一篇具限制性之最長共同子序列問題的論
文。那篇論文使用動態規劃的技巧來解決具限制性之最長共同子序列問題，其時間及
空間複雜度皆為O(nmr)，n、m 和r 是X、Y 和Z 的序列長度。藉由回顧Chin 的方法，
我們可以發現其中很多的運算都是可以被忽略的。
在此篇論文中，我們提出一個時間及空間複雜度同樣是O(nmr)的方法。但是，
相對於Chin 的方法，我們簡省掉相當多不必要的計算。所以，我們的方法會比Chin
的方法來得有效率。此外，我們也相對節省掉相當多的記憶體空間。

In this thesis, we address the constrained longest common subsequence problem
which is defined as follows. Given two sequences X and Y, and a constrained sequence Z,
find a longest common subsequence P of X and Y such that Z is a subsequence of P.
Recently, Chin and other four authors [CSFHK2004] proposed an O(nmr) time and
space algorithm to solve this problem using the dynamic programming technique, where n,
m and r are the lengths of X, Y and Z, respectively. By reviewing Chin’s method, we
found that many computations in Chin’s method can be ignored.
In this thesis, we present an algorithm to solve the constrained longest common
subsequence problem in O(nmr) time and space also. But, our method runs faster than
Chin’s method because fewer computations are need in our method. In addition, less
memory space is needed in our method.

List of Figures ...................................................................................................................... v
List of Tables ....................................................................................................................... vi
Chapter 1 Introduction .................................................................................................1-1
Chapter 2 A Dynamic Programming Approach .........................................................2-1
2.1 The Dynamic Programming Approach to the Constrained Longest Common Subsequence
Problem ..................................................................................................................................... 2-1
2.2 The Time Complexity................................................................................................................ 2-5
2.3 An Example............................................................................................................................... 2-5
Chapter 3 Our Method to Solve the Constrained Longest Common Subsequence
Problem..............................................................................................................3-1
3.1 The Characterization of the Constrained Longest Common Subsequence Problem.......... 3-1
3.2 The Main Idea of Our Method ................................................................................................. 3-3
3.3 Our Method to Solve the Constrained Longest Common Subsequence Problem................ 3-9
3.4 Our Algorithm........................................................................................................................ 3-18
3.5 The Time Complexity and Space Complexity....................................................................... 3-20
3.6 An Example............................................................................................................................. 3-21
Chapter 4 Experiments .................................................................................................4-1
Chapter 5 Conclusion....................................................................................................5-1
Bibliography.....................................................................................................................6-1
Appendix ...........................................................................................................................7-1

[ALP2004] Faster Algorithms for String Matching with k Mismatches, Amir, A.,
Lewenstein, M. and Porat, E., Journal of Algorithms, Vol. 50, 2004, pp. 257-275.
[LH2005] A Memory-Efficient Algorithm for Multiple Sequence Alignment with
Constraints, L, C. L. and H, Y. P., Bioinformatics, Vol. 21, No. 1, 2005, pp. 20-30.
[BLP97] Approximation Algorithms for Multiple Sequence Alignment, Bafna, V., Lawler,
E. L. and Pevzner, P. A., Theoretical Computer Science, Vol. 182, 1997, pp. 233-244.
[BM77] A Fast String Searching Algorithm, Boyer, R. S. and Moore, J. S.,
Communication of the ACM, Vol. 20, 1977, pp. 762-772.
[CL88] The Multiple Sequence Alignment problem in Biology, Carrillo, H. and Lipman, D.
J., SIAM Journal on Applied Mathematics, Vol. 48, 1988, pp. 1073-1082.
[CR2002] Jewels of Stringology, Crochemore, M. and Rytter, W., World Scientific, 2002.
[H75] A Linear Space Algorithm for Computing Maximal Common Subsequences,
Hirschberg, D. S., Communications of the ACM, Vol. 18, No. 6, 1975, pp. 341-343.
[HS77] A Fast Algorithm for Computing Longest Common Subsequences, Hunt, J. W. and
Szymanski, T. G., Communications of the ACM, Vol. 20, No. 5, 1977, pp. 350-353.
[KMP77] Fast Pattern Matching in Strings, Knuth, D., Morris, J. and Pratt, V., SIAM
Journal on Computing, Vol. 6, 1977, pp. 323-350.
[NW70] A General Method Applicable to the Search for Similarities in the Amino Acid
Bibliography
6-2
Sequence of Two Proteins, Needleman, S. B. and Wunsch, C. D., Journal of Biology, Vol.
48, 1970, pp. 443-453.
[SW81] Identification of Common Molecular Subsequences, Smith, T. F. and Waterman,
M. S., Journal of Molecular Biology, Vol. 147, 1981, pp. 195-197.
[ZBM98] Alignments Without Low-Scoring Regions, Zhang, Z., Berman, P. and Miller,
W., Research in Computational Molecular Biology (RECOMB), Vol. 5, 1998, pp.
294-301.
[T2003] The Constrained Longest Common Subsequence Problem, Tsai, Y. T.,
Information Processing Letters, Vol. 88, 2003, pp. 173-176.
[CSFHK2004] A Simple Algorithm for the Constrained Sequence Problem, Chin, F. Y. L.,
Santis, A. D., Ferrara, A. L., Ho, N. L. and Kim, S. K., Information Processing Letters, Vol.
90, 2004, pp. 175-179.
[D2005] Fast Algorithm for Constrained Longest Common Subsequence Problem,
Deorowicz, S., Technical Report, 2005.