共同環式子序列(common cyclic subsequence)為兩環式字串經環式位移(cyclic shift)後的共同子序列。最長共同環式子序列(longest common cyclic subsequence, LCCS)的問題就是要找出所有共同環式子序列中長度最長者。本論文提出一個解決LCCS問題的心跳式(systolic)演算法。對長度分別為m與n (m  n)的A與B兩字串，用LCS[A, Bj]代表A與Bj字串的最長共同子序列(longest common subsequence, LCS)，其中Bj為B字串經環式位移後以第j字元為首的字串，1  j  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  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  j  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.

[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.