臺灣博碩士論文加值系統

最長共同子字串問題（longest common subsequence、LCS）自從70年代起就受到釵h學者的研究與注意。自此釵h循序或平行演算法即常見諸於國內外重要文獻。這篇論文的目的，就是在設計並且實作一個平行演算法來解 LCS 的問題，然後在一個PC cluster的環境下實做這些演算法，來分析他們的效能，特別是找出這些演算法的絕對增益比（absolute speedup）： Tsequential/Tparallel(p)，即最快的循序演算法在一部個人電腦執行所需時間除上p台個人電腦執行平行演算法所需時間的比值關係。實驗的結果顯示我們所提出的LCS平行演算法卓越效率。
此外我們也針對較複雜的多條字串中求取最長共同子字串問題（mLCS），提出一些透過Metaheuristic設計的近似演算法，文章最後會以實驗結果的方式與其他學者的演算法做個比較。

The longest common subsequence (LCS) problem has attracted many researchers’ attention since the ‘70s. Many sequential or parallel LCS algorithms can be found in the literature even since.
We propose new parallel algorithms for the longest common subsequence (LCS) problem in the coarse grained multicomputers (CGM) model, and some ant colony optimization (ACO) algorithms for finding the longest common subsequence among multiple sequences (mLCS) in the thesis. For the LCS problem, we empirically study the performances of our and other CGM parallel algorithms in the literature on a PC cluster. To report the absolute speedup, Tsequential/Tparallel(p), the ratio of time needed by running the best sequential algorithm over the time needed by the parallel algorithm running on p processors, we also implement and test some elegant sequential algorithms for LCS. For the mLCS problem, we testify our ACO algorithms against some proposed approximation algorithms. Besides the parallel implementation of ACO is realized on a PC cluster.
Experimental results about different kinds of input problem sets, such as DNA, protein or random sequences, demonstrate the efficiency and scalability of our CGM parallel algorithms for LCS and the ACO algorithms for mLCS.

Chapter 1 Introduction
Chapter 2 Brief Reviews on LCS Algorithms
2.1 Literature survey on LCS algorithms
2.1.1 Sequential LCS algorithms
2.1.1.1 Finding LCS by row by row approaches
2.1.1.2 Finding LCS by diagonal approaches
2.1.1.3 Finding LCS by Bit Vector algorithm
2.1.2 Parallel LCS algorithms
2.1.2.1 PRAM model
2.1.2.2 CGM model
2.2 Literature survey on mLCS Algorithms
2.2.1 Long Run Algorithms
2.2.2 Expansion Algorithms
2.2.3 Minimal Spanning Tree-based Greedy Algorithms
2.2.4 String by String Iterative Algorithms
2.2.5 ACO Framework
2.2.6 AS-LCS: ACO for mLCS by Hsu and Tsai
Chapter 3 Parallel Algorithms for LCS
3.1 Simple wavefront parallel algorithm
3.2 Wavefront Parameterized (WP) and Wavefront Divided (WD)
3.3 KC WP
Chapter 4 ACO Algorithms for mLCS
4.1 ACOTree for mLCS
4.2 ACOChar for mLCS
4.3 Parallel ACOChar for mLCS
Chapter 5 Experimental Results
5.1 Parallel platform
5.2 Parallel LCS Algorithms
5.3 mLCS Algorithms
Chapter 6 Concluding Remarks

[1]R. A. Wagner, and M. J. Fischer. The string-to-string correction problem. Journal of the ACM, 21(1):168-173, 1974.
[2]D. Sankoff, and J. B. Kruskal (eds.). Time Warps, String Edits, and Macromolecules, The Theory and Practice of Sequence Comparison. Addison-Wesley, 1983.
[3]J. Modelevsky. Computer applications in applied genetic engineering. Advances in Applied Microbiology, 30:169-195, 1984.
[4]A. Apostolico, M. Atallah, L. Larmore, and S. Mcfaddin. Efficient parallel algorithms for string editing and related problems. SIAM Journal on Computing, 19:968-988, 1990.
[5]D. Gusfield. Algorithms on Strings, Trees and Sequences, Cambridge University Press, New York, 1997.
[6]A. V. Aho, D. S. Hirschberg, and J. D. Ullman. Bounds on the complexity of longest common subsequence problem, Journal of the ACM, 23(1):1-12, 1976.
[7]D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18 (6):341-343, 1975.
[8]J.W. Hunt, and T. G. Szymanski. A fast algorithm for Computing Longest Common Subsequences, Communications of the ACM, 20(5):350-353, 1977.
[9]W. J. Hsu, and M. W. Du. New algorithms for the LCS problem, Journal of Computers and System Sciences, 29:133-152, 1984.
[10]A. Apostolico, and C. Guerra. The longest common subsequence problem revisited. Algorithmica. 18(1):315-336, 1987.
[11]S. Kuo, and G. R. Cross. An improved algorithm to find the length of the longest common subsequence of two strings. ACM SIGIR Forum, 23(3-4):89-99, 1989.
[12]S. Wu, U. Manber, G. Myers, and W. Miller. An O(NP) sequence comparison algorithm. Information Processing Letters, 35:317-323, 1990.
[13]C. Rick. A new flexible algorithm for the longest common subsequence problem. In Proc. of the 5rd Combinatorial Pattern Matching, pages 340-351, LNCS 937, 1995.
[14]N. Nakatsu, Y. Kambayashi and S. Yajima. A Longest Common Subsequence Algorithm Suitable for Similar Text Strings, Informatica, 18, 1982
[15]W. Miller and E. W. Myers. A File Comparision Program, Softw Pract. Exp., 15(11): 1025-1040, 1985.
[16]M. Paterson, and V. Dancik. Longest common subsequences. In Proc. of the 19th Mathematical Foundations of Computer Science (MFCS), pages 127-142, LNCS 841, 1994.
[17]L. Bergroth, H. Hakonen, and T. Raita. A survey of longest common subsequence algorithms. SPIRE’2000, pages 39-48, 2000.
[18]M. Crochemore, C. S. Iliopoulls, Y. J. Ponzon and J. F. Reid, A fast and practical bit-vector algorithm for the longest common subsequence problem, Information Processing Letters, 80, 279-285, 2001. (2001)
[19]E. Myers. A Fast Bit-Vector Algorithm for Approximate String Matching based on Dynamic Programming, J.Assoc. Comput. Mach., 46(3):395-415 ,1999
[20]L. Allison and T. L. Dix, A bit-string longest common subsequence algorithm, Inform. Process. Lett., 23, 305-310, 1986
[21]R.A. Baeza-Yates and G.H. Gonnet, A new approach to text searching, Comm. Assoc. Comput. Match., 35, 74-82, 1992.
[22]S. Wu and U. Manber, Fast text searching allowing errors, Comm. Assoc. Comput. Mach., 35, 83-91, 1992.
[23]R. A. Baeza-Yates and G. Navarro, A fast algorithm for approximate string matching, Proceedings of the 7th Symp. On Combinatorial Pattern Matching, LNCS 1075, 1-23, 1996.
[24]M. Lu, and H. Lin. Parallel algorithm for the longest common subsequence problem. IEEE Transaction on Parallel and Distributed Systems, 5(8): 835-848, 1994.
[25]Z. Galil, and K. Park. Dynamic programming with convexity, concavity and sparsity. Theoretical Computer Science 92(1):49-76, 1992.
[26]J.E. Myoupo, and D. Seme. Time-Efficient Parallel Algorithms for the Longest Common Subsequence and Related Problems. Journal of Parallel and Distributed Computing, 57:212-223, 1999.
[27]L. Valiant. A bridging model for parallel computation. Communication of the ACM, 33(8):103-111, 1990.
[28]F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel geometric algorithms for Coarse Grained Multicomputers. In Proc. ACM 9th Annual Computational Geometry, pages 298-307, 1993.
[29]F. Dehne, A. Fabri, and A. Rau-Chaplin. Scalable parallel computational geometry for Coarse Grained Multicomputers. International Journal on Computational Geometry, 3:379-400, 1996.
[30]C. E. R. Alves, E. N. Cáceres, and F. Dehne. Parallel dynamic programming for solving the string editing problem on CGM/BSP. In Proc. ACM Symp on Parallel Algorithms and Architectures SPAA, 2002.
[31]C. E. R. Alves, E. N. Cáceres, F. Dehne, and S. W. Song, Gramado-RS, Brazil. A CGM/BSP parallel similarity algorithm, October, 2002.
[32]C. E. R. Alves, E. N. Cáceres, and S.W. Song. A BSP/CGM algorithm for the all-substrings longest common subsequence problem. In Proc. of the International Parallel and Distributed Processing Symposium, IPDPS’03, 2003.
[33]T. Garcia, J-F. Myoupo, and D. Seme. A Coarse-Grained Multicomputer Algorithm for the Longest Common Subsequence Problem. Eleventh Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 349, 256, LNCS 2668, 2003.
[34]S. B. Needleman, and C. D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48:443-453, 1970.
[35]D. S. Hirschberg. Algorithms for the longest common sequence problem. Journal of the ACM, 24(4):664-675, 1977.
[36]C. E. R. Alves, E. N. Cáceres, F. Dehne, and S.W. Song. A parallel wavefront Algorithm for efficient biological sequence. Intl Conf on Computational Science and its Applications (ICCSA), 2003.
[37]T. Jiang and M. Li, On the approximation of shortest sommon supersequences and longest common subsequences, SIAM J on Computing, 24(5), 1122-1139, 1995.
[38]P. Barone, P. Bonizzoni, G. D. Vedova and G. Mauri, An Approximation Algorithm for the Shortest Common Supersequence Problem: An Experimental Analysis, Proc. of the ACM symposium on Applied computing, 2001, pages 56-60.
[39]Y. T. Tsai and J. T. Hsu. An Approximation Algorithm for Multiple Longest Common Subsequence Problem, 2001.
[40]D. Corne, M. Dorigo, and F. Glover (eds.), New Ideas in Optimization. New York: McGraw-Hill, pp. 11–32
[41]Colorni, M. Dorigo and V. Maniezzo, Distributed optimization by ant colonies. In: Varela F, Bourgine P, eds. Proc. of the ECAL''91 European Conf. of Artificial Life. Paris: Elsevier, 1991. 134~144.
[42]M. Dorigo, Optimization, learning and natural algorithms. Ph.D.Thesis, Politecnico di Milano, Italy, 1992
[43]M. Dorigo and L. M. Gambardella, Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem, IEEE Transactions on Evolutionary Computation, Vol. 1, No. 1, 1997
[44]M. Dorigo and L. M. Gambardella, Ant colonies for the traveling salesman problem, BioSystems, Vol. 43, 1997b, pp. 73-81.
[45]D. Costa and A. Hertz, Ant can color graph. Journal of the Operational Research Society, 48:295-305, 1997
[46]Maniezzo and Colorni, The ant system applied to the quadratic assignment problem, IEEE Transactions on Knowledge and Data Engineering, 11(5):2063-2070 , 1999
[47]S. J. Shyu, P. Y. Yin, B. M. T. Lin and M. Haouari, Ant-Tree: An Ant Colony Optimization approach to the generalized minimum spanning tree problem, Journal of Experimental and Theoretical Artificial Intelligence, 15(1):103-112, 2003
[48]L. M. Gambardella and M. Dorigo, Ant Colony System hybridized with a new local search for the sequential ordering problem. INFORMS Journal on Computing, 3:237-255, 2000
[49]G. Di Caro and M. Dorigo, Mobile agents for adaptive routing, Proceedings of the 31st Hawaii International Conference on System, IEEE Computer Society Press, Los Alamitos, CA, pages 74-83, 1998.
[50]A. Bauer, B. Bullnheimer, R. F. Hartl and C. Strauß, An Ant Colony Optimization Approach for the Single Machine Total Tardiness Problem, Proceedings of the Congress on Evolutionary Computation, 1999
[51]L.M. Gambardella, E. D. Taillard and G. Agazzi, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, In: D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization, McGraw-Hill, London, UK, pages 63-76, 1999.
[52]V. K. Jayaraman, B. D. Kulkarni, S. Karale and P. Shelokar, Ant colony framework for optimal design and scheduling of batch plants, Computers and Chemical Engineering, 24:1901-1912, 2000
[53]P. R. McMullen, An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives, Articial Intelligence in Engineering, 15(3):309-317, 2001
[54]V. T''kindt, N. Monmarche, F. Tercinet and D. Laugt, An Ant colony Optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem, European Journal of Operational Research, 142(2):250-257, 2002
[55]D. Merkle, M. Middendorf and H. Schmeck, Ant Colony Optimization for Resource-Constrained Project Scheduling. IEEE Trans. On Evolutionary Comput.,6(4):333-346 , 2002
[56]V. Maniezzo and A. Carbonaro, Ant Colony Optimization: An Overview, CiteSeer, 1999
[57]G. N. Varela and M. C. Sinclair, Ant colony optimization for virtual-wavelength-path routing and wavelength allocation, Proceedings Of the Congress on Evolutionary Computation (CEC’99), Washington DC, USA, July 1999.
[58]M. Dorigo, G. D. Caro and L. M. Gambardella, Ant Algorithm for Discrete Optimization, Artificial Life 5: 137-172, 1999
[59]A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam, PVM- Parallel Virtual Machine A Users Guide and Tutorial for Networked Parallel Computing. The MIT Press Cambridge, Massachusetts London, England, 1994
[60]Y. C. Lin and J. W. Yeh, A Scalable and Efficient Systolic Algorithm for the Longest Common Subsequence Problem, 2002
[61]R. W. Irving and C. B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, Lecture Notes in Computer Science 644, Springer Verlag, pp.214-229, 1992.
[62]K. Hakata and H. Imai, The longest common subsequence problem for small alphabet size between many strings, Lecture Notes in Computer Science 650, Springer Verlag, pp.469-478, 1992.