在兩個序列的所有共同子序列中最長的我們稱之為最長共同子序列( longest common subsequence , LCS) 。LCS問題為求出兩個序列的最長共同子序列與最長共同子序列的長度。 LCS與相關的序列比對問題在生物科學領域中扮演著相當重要的角色，特別是在DNA序列或蛋白質序列的相似性比對研究上。而LCS問題在資料壓縮、 圖案辨識 與電腦檔案管理的應用上都相當重要。
　　心跳式架構的組織與網路類似，具有一維線性陣列或是二維矩行陣列。在心跳式架構中，所有的處理單元均在同一個時脈下同時運算，且由於其具有相連結的網路架構而可同時執行許多的計算。除此之外心跳式架構更具有簡單、具規則性、資料只在相鄰處理單元間傳輸等優點。
　　在本論文中我們提出一新式心跳式陣列，它不但可求出最長共同子序列長度更可同時建構出一新式動態規劃表。我們也另外提出PRINT-LCS’演算法，藉由此演算法可由新式動態規劃表中求出全部的最長共同子序列。
　　LCS軟智產已經分別在Xilinx的Vertex 400型FPGA以及TSMC 0.35 μm元件庫(Cell Library)上實現與驗證。在FPGA設計部分，工作頻率為48 MHz，資料處理量最高為724 Mbps，消耗了Vertex 400型FPGA實驗板上89%的LUT；在元件庫設計的部分，工作頻率為74 MHz，資料處理量最高為1900 Mbps，核心(core)面積為1806 μm × 1715 μm，等效邏輯閘數量(gate count)約為41366個，消耗功率為70.41 mW。

A longest common subsequence problem (LCS) of two strings is a maximal length common subsequence between them. The LCS problem is to find an LCS of two given strings and the length of the LCS (LLCS). LCS and related string matching problems play an important role in biosciences in which similarities of sequences of DNA or proteins are studied. These problems are also of great importance for data compression, pattern recognition, and the management of computer file.
A systolic architecture is organized as a network, for example, a linear array or a rectangular array. All (processor element) PEs operate concurrently under a global clock and several computations are performed at the same time by the network. Moreover, the systolic architecture has the merit of simplicity, regularity, and locality. In this paper, we present a new systolic array algorithm for solving the LLCS problem and building a new dynamic programming table. We also present a modified PRINT-LCS’ algorithm which can find all LCSs from the new dynamic programming table.
The resulting LCS IP has been implemented and verified with both Xilinx Vertex 400 FPGA and TSMC 0.35 μm cell library. In the FPGA part, it operates at 48 MHz and achieves a high throughput of 724 Mbps. It takes up LUTs of 89% in FPGA board. In the cell-based part, it operates at 74 MHz and achieves a high throughput of 1900 Mbps. The core occupies the area of 1806 μm × 1715 μm, which is approximately equivalent to 41366 gates, and consumes about 70.41 mW .

[1] D. S. Hirschberg, “A linear space algorithm for computing maximal common subsequences,” Communications of the ACM, Vol. 18, No. 6, pp. 341-343, June 1975.
[2] M. Lu and H. Lin, “Parallel algorithms for the longest common subsequence problem,” IEEE Trans. Parallel Distributed Syst., Vol. 5, No. 8, pp. 835-848, Aug. 1994.
[3] Y. Robert and M. Tchuente, “A systolic array for the longest common subsequence problem,” Information Processing Letters, Vol. 21, No. 4, pp. 191-198, Oct. 7, 1985.
[4] D. Sankoff and J. B. Kruskal, Time Warps, String Edits and Macromolecules: The Theory and Pactice of Sequence Comparison. Reading, MA : Addison-Wesley, 1983.
[5] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 2nd ed., McGraw-Hill Bok Co., 2001.
[6] R. Hughey, “Parallel hardware for sequence comparison and alignment,” Comput Appl Biosci., Vol. 12, No. 6, pp. 473-479, 1996.
[7] T. Lecroq, G. Luce, and J. F. Myoupo, “A faster linear systolic algorithm for recovering a longest common subsequence,” Information Processing Letters, Vol. 61, No. 3, pp. 129-136, 1997.
[8] T. Lecroq, J. F. Myoupo, and D. Seme, “A one-phase parallel algorithm for the sequence alignment problem,” Parallel Processing Letters, Vol. 8, No. 4, pp. 515-526, 1998.
[9] Y. C. Lin, “New systolic arrays for the longest common subsequence problem,” Parallel Computing, Vol. 20, No. 9, pp. 1323-1334, 1994.
[10] Y. C. Lin. and J. C. Chen, “An efficient systolic algorithm for the longest common subsequence problem,” The journal of Supercomputing, Vol. 12, No. 4, pp. 373-385, 1998.
[11] Y. C. Lin. and J. C. Chen, “Another efficient systolic algorithm for the longest common subsequence problem,” Journal of the Chinese Institute of Engineers, Vol. 23, No. 5, pp. 607-613, 2000.
[12] Y. C. Lin and J. W. Yeh, “A scalable and efficient systolic algorithm for the longest common subsequence problem,” Journal of Information Science and Engineering, Vol. 18, No. 4, pp. 519-532, 2002.
[13] Y. C. Lin and J. W. Yeh, “Deriving a systolic algorithm for the LCS problem,” International Conference on Parallel and Distributed Processing Techniques and Applications, pp. 1890-1897, 1998.
[14] Y. C. Lin and J. W. Yeh, “Deriving a fast systolic algorithm for the longest common subsequence problem,” Parallel Algorithms and Applications, Vol. 17, No. 1, pp. 1-18, 2002.
[15] G. Luce, and J. F. Myoupo, “Systolic-based parallel architecture for the longest common subsequences problem,” Integration, the VLSI Journal, Vol. 25, No. 1, pp. 53-70, 1998.
[16] N. Ranganathan and R. Sastry, “VLSI architectures for pattern matching,” International Journal of Pattern Recognition and Artificial Intelligence, Vol. 8, No. 4, pp. 815-843, 1994.
[17]Y. C. Lin and J. C. Chen, “Another fastest systolic algorithm for the longest common subsequence problem,” Proc. International Computer Symp., Vol. 3, pp. 34-39, 1997.
[18] C. B. Yang and R. C. T. Lee, “Systolic algorithms for the longest common subsequence problem,” Journal of the Chinese Institute of Engineers, Vol. 10, No. 6, pp. 691-699, 1987.
[19] P. D. Michailidis and K.G. Margaritis, “ New processor Array Architectures for the Longest Common Subsequence Problem,” The Journal of Supercomputing, Vol. 32, No. 1, pp. 51 – 69, April 2005.
[20]Robert W. Brodersen, VLSI signal processing, III, IEEE Press, 1998.
[21]K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation, Wiley-Interscience Publication, 1999.
[22]S. Y. Kung, VLSI Array Processors, Prentice Hall, Englewood Cliffs, New Jersey, 1988.
[23]Lars Wanhammar, DSP Integrated Circuits, ACADEMIC Press,1999.
[24] G. S. Almasi and A. Gottlieb, Highly Parallel Computing, Benjamin/Cummings, Redwood City, CA, 1989.
[25]T. Fountain, Processor Arrays, Architecture and Applications, Academic Press, London, 1987.
[26]A. J. van de Goor, Computer Architecture and Design, Addison-Wesley, Wokingham, England, 1989.
[27]R. E. Morely, G. E. Christensen and T. J. Sullivan, Systolic Array Processors, Prentice Hall, New York, 1989.
[28]P. Prisch, Architectures for Digital Signal Processing, John Wiley and Sons, Chichester, 1998.
[29]GenBank, URL: http://www.ncbi.nlm.nih.gov/.