臺灣博碩士論文加值系統

共同環式子序列(common cyclic subsequence)為兩環式字串經環式位移(cyclic shift)後的共同子序列。最長共同環式子序列(longest common cyclic subsequence, LCCS)的問題就是要找出所有共同環式子序列中長度最長者。本論文提出一個解決LCCS問題的心跳式(systolic)演算法。對長度分別為m與n (m �d n)的A與B兩字串，用LCS[A, Bj]代表A與Bj字串的最長共同子序列(longest common subsequence, LCS)，其中Bj為B字串經環式位移後以第j字元為首的字串，1 �T j �T n。我們利用n個處理器的ring架構，能在mn + n個步驟求出LCS[A, B1], LCS[A, B2] ,…, LCS[A, Bn]與其長度，而其中最長的LCS即為A與B的LCCS。若用已有的心跳式演算法求出LCS[A, B1], LCS[A, B2] ,…, LCS[A, Bn]與其長度，則需要2n2 + mn – n個步驟。

Given two strings A and B, the longest common cyclic subsequence (LCCS) problem is to find the longest of all subsequences of A and of some cyclic shift of B and its length. In this thesis, a systolic algorithm is presented to solve the LCCS problem. Given strings A and B of lengths m and n (m �d n), respectively, let LCS[A, Bj] represent the longest common subsequence of strings A and Bj , where Bj is a cyclic shift of B with the jth character at the beginning, 1 �T j �T n。Our systolic algorithm computes LCS[A, B1], LCS[A, B2] ,…, LCS[A, Bn] and their lengths in mn + n time steps with a ring of n processors.

摘要……………………………………………………………………………………I
Abstract………………………………………………………………………………II
誌謝……………………………………………………………………………………III
目錄……………………………………………………………………………………IV
第1章 緒論………………………………………………………………………1
1.1簡介………………………………………………………………………………1
1.2相關研究…………………………………………………………………………2
1.3環式字串的應用…………………………………………………………………3
1.4心跳式架構………………………………………………………………………5
1.5論文組織…………………………………………………………………………6
第2章 相關文獻回顧……………………………………………………………7
2.1 LCS相關的平行演算法…………………………………………………………7
2.2 Lin與Chen的心跳式演算法……………………………………………………8
2.3求LCCS的探討……………………………………………………………………15
第3章 LCCS的心跳式演算法……………………………………………………17
3.1平行架構…………………………………………………………………………17
3.2 演算法概要 (overview)………………………………………………………20
3.3 演算法細節 ……………………………………………………………………24
第4章 時間複雜度………………………………………………………………29
第5章 結論………………………………………………………………………32
附錄A Property 1的證明…………………………………………………………33
參考文獻 ……………………………………………………………………………34

[1]A. Aggarwal, J. Park, Notes on searching in multidimensional monotone arrays, in: Proc. 29th Annual IEEE Symposium on Foundations of Computer Science, White Plains, NY, USA, 1988, pp. 497-512.
[2]B. Alberts, D. Bray, J. Lewis, M. Raff, K. Roberts, J.D. Watson, Molecular Biology of the Cell, Garland, New York, 1983.
[3]A. Apostolico, M.J. Atallah, L.L. Larmore, S. McFaddin, Efficient parallel algorithms for string editing and related problems, SIAM Journal on Computing 19 (5) (1990) 968-988
[4]M.J. Flynn, K.W. Rudd, Parallel architectures, ACM Computing Surveys 28 (1) (1996) 67-70.
[5]G.M. Landau, E.W. Myers, J.P. Schmidt, Incremental string comparison, SIAM Journal on Computing 27 (2) (1998) 557-582.
[6]T. Lecroq, G. Luce, J.F. Myoupo, A faster linear systolic algorithm for recovering a longest common subsequence, Information Processing Letters 61 (3) (1997) 129 - 136.
[7]Y.-C. Lin, New systolic arrays for the longest common subsequence problem, Parallel Computing 20 (9) (1994) 1323 - 1334.
[8]Y.-C. Lin, J.-C. Chen, Another efficient systolic algorithm for the longest common subsequence problem, Journal of the Chinese Institute of Engineers 23 (5) (2000) 607-613.
[9]Y.-C. Lin, J.-C. Chen, An efficient systolic algorithm for the longest common subsequence problem, The Journal of Supercomputing 12 (4) (1998) 373-385.
[10]Y.-C. Lin, J.-W. Yeh, A scalable and efficient systolic algorithm for the longest common subsequence problem, Journal of Information Science and Engineering 18 (4) (2002) 519-532.
[11]W. Liu, L. Chen, A parallel algorithm for solving LCS of multiple bioseqences, in: Proc. International Conference on Machine Learning and Cybernetics, Dalian, 2006, pp. 4316 - 4321.
[12]M. Lu, H. Lin, Parallel algorithms for the longest common subsequence problem, IEEE Transactions on Parallel and Distributed Systems 5 (8) (1994) 835 - 848
[13]G. Luce, J.F. Myoupo, An efficient linear systolic algorithm for recovering longest common subsequences, in: Proc. IEEE First International Conference on Algorithms and Architectures for Parallel Processing, Brisbane, Qld., Australia, vol. 1, 1995, pp. 20-29.
[14]S.S. Mader, Biology, 7th ed., McGraw-Hill, Toronto, 2001.
[15]A. Marzal, G. Peris, Normalized cyclic edit distances: An efficient algorithm, in: Proc. 10th Conference of the Spanish Association for Artificial Intelligence, San Sebastian, Spain, 2003, pp. 435-444.
[16]F. Nicolas, E. Rivals, Longest common subsequence problem for unoriented and cyclic strings, Theoretical Computer Science 370 (2007) 1-18.
[17]P. Quinton, Y. Robert, Systolic Algorithms & Architectures, Prentice Hall, New Jersey, 1991.
[18]S.A.M. Rizvi, P. Agarwal, A new bucket-based algorithm for finding LCS from two given molecular sequences, in: Proc. The Third International Conference on Information Technology: New Generations 2006, pp. 560 - 561
[19]Y. Robert, M. Tchuente, A systolic array for the longest common subsequence problem, Information Processing Letters 21 (4) (1985) 191-198.
[20]J.P. Schmidt, All highest scoring paths in weighted grid graphs and their application to finding all approximate repeats in strings, SIAM Journal on Computing 27 (4) (1998) 972-992.
[21]D. Seme, S. Youlou, Computing the longest common subsequence on a linear array with reconfigurable pipelined bus system., in: Proc. ISCA 18th International Conference on Parallel and Distributed Computing Systems, Las Vegas, Nevada, USA, 2005, pp. 49-54.
[22]A. Tiskin, Semi-local string comparison: Algorithmic techniques and applications, Mathematics in Computer Science 1 (4) (2008) 571-603.
[23]Y.-H. Wang, Image indexing and similarity retrieval based on spatial relationship model, Information Sciences 154 (1-2) (2003) 39-58.
[24]B. Wilkinson, M. Allen, Parallel Programming: Techniques and Applications using Networked Workstations and Parallel Computers, 2nd ed., Prentice Hall, New Jersey, 2005.