(3.227.208.0) 您好!臺灣時間:2021/04/20 14:24
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:彭兆立
研究生(外文):Chao-Li Peng
論文名稱:附加條件限制之最長共同子序列方法
論文名稱(外文):An Approach for Solving the Constrained Longest Common Subsequence Problem
指導教授:楊昌彪楊昌彪引用關係
指導教授(外文):Chang-Biau Yang
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:29
中文關鍵詞:最長共同子序列限制序列比對動態規劃
外文關鍵詞:sequence alignmentdynamic programmingcostrainedlongest common subsequence
相關次數:
  • 被引用被引用:1
  • 點閱點閱:121
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:14
  • 收藏至我的研究室書目清單書目收藏:0
一個子序列是經由把一個給定的序列不刪或刪掉一些符號得來的。給定兩個序列,最長共同子序列問題就是找出一個共同擁有的子序列中長度最長的。而有條件限制的最長共同子序列問題則是找出一個最長的內含指定序列的子序列。注意一個附加條件限制的最長子序列可能比一般的最長子序列短。
在本論文中我們提出一個動態規劃方法的演算法來解有條件限制的最長共同子序列問題。所需的時間複雜度是O(pmn),其中m和n為給定的序列的長度,p為要求的序列的長度。我們的演算法也可以應用到附加條件限制的序列比對問題。也就是序列比對問題在額外要求指定的符號對齊在同一行。
A subsequence is obtained by deleting zero or more symbols from a given sequence. For given two sequences, the longest common subsequence problem is to find a common subsequence whose length is the longest. The constrained longest common subsequence (CLCS) problem is to find a longest common subsequence that contains a specific subsequence. Note a CLCS may be shorter than an LCS.
In this thesis, we propose a dynamic programming algorithm for solving the CLCS problem. The time complexity is O(pmn), where m and n are the lengths of the given sequences and p is the length of the constraint sequence. Our algorithm
can also be applied to solve the constrained sequence alignment problem, which is a sequence alignment problem with the requirement that some specific symbols must be aligned together.
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
Chapter 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
Chapter 2. Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 The Longest Common Subsequence Problem . . . . . . . . . . . . . . . . . . 4
2.2 The Constrained LCS Problem . . . . . . . . . . . . . . . . . . . . . . . 8
Chapter 3. An Algorithm for Solving the Constrained LCS Problem . . . . . . .10
3.1 The Constrained LCS Problem . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Algorithm and Complexity . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Proof of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 17
Chapter 4. Simplified Algorithm . . . . . . . . . . . . . . . . . . . . . . . 21
4.1 Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Algorithm and Complexity . . . . . . . . . . . . . . . . . . . . . . . . 22
Chapter 5. Extension to the Sequences Alignment Problem . . . . . . . . . . . 23
5.1 Multiple Sequences Alignment . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Multiple Sequences Alignment with Constraints . . . . . . . . . . . . . . 25
Chapter 6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
[1] A. Aho, D. Hirschberg, and J. Ullman, “Bounds on the complexity of the longest common subsequence problem,” Journal of the ACM, Vol. 23, No. 1, pp. 1–12, 1976.
[2] A. Apostolico and C. Guerra, “The longest common subsequence problem revisited,” Algorithmica, No. 2, pp. 315–336, 1987.
[3] L. Bergroth, H. Hakonen, and T. Raita, “A survey of longest common subsequence algorithms,” Seventh International Symposium on String Processing
Information Retrieval, pp. 39–48, 2000.
[4] V. Chavatal, D. Klarner, and D. Knuth, “Selected combinatorial research problem,” Tech. Rep. STAN-CS-72-292, Stanford Univ., p. 26, 1972.
[5] D. S. Hirschberg, “Algorithms for the longest common subsequence problem,”
Journal of the ACM, Vol. 24, No. 4, pp. 664–675, 1977.
[6] J. W. Hunt and T. G. Szymanski, “A fast algorithm for computing longest
common subsequences,” Communications of the ACM, Vol. 20, No. 5, pp. 350–353, 1977.
[7] J. Modelevsky, “Computer applications in applied genetic engineering,” Advances in Applied Microbiology, Vol. 30, pp. 169–195, 1984.
[8] E. W. Myers, “An O(nd) difference algorithm and its variations,” Algorithmica, No. 1, pp. 251–266, 1986.
[9] N. Nakatsu, Y. Kambayashi, and S. Yajima, “A longest common subsequence
algorithm suitable for similiar texts,” Acat Informatica, Vol. 18, pp. 171–179, 1982.
[10] C. Rick, “Simple and fast linear space computation of longest common subsequences,” Information Processing Letters, pp. 275–281, 2000.
[11] T. F. Smith and M. S. Waterman, “Comparison of biosequences,” Advances in Applied Mathematics, Vol. 2, pp. 482–489, 1981.
[12] R. A. Wagner and M. J. Fischer, “The string-to-string correction problem,”Journal of the ACM, Vol. 21, No. 1, pp. 168–173, 1975.
[13] S. Wu, U. Manber, G. Myers, and W. Miller, “An O(NP) sequence comparison
algorithm,” Information Processing Letters, Vol. 35, pp. 317–323, 1990.
[14] C. B. Yang and R. C. T. Lee, “Systolic algorithm for the longest common
subsequence problem,” Journal of the Chinese Institue of Engineers, Vol. 10,
No. 6, pp. 691–699, 1987.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔