Parallel Pairwise Sequence Alignment Algorithm Based on Longest Common Subsequence

Main Article Content

Pich Tantichukaitikul
Sattara Hattirat
Hoyin Jonathan Chan


- There is an emerging paradigm in the field of computing towards parallelism at increasing levels. Among these, multi-core processors are fast becoming the norm in the world of modern computers. The potential enhancement in performance would allow certain fundamental procedures in molecular biology, such as biological sequence alignments of DNA and protein sequences, to be done faster, paving the way for more efficient multiple genome comparison. However, in order to harness the full power of multi-core processors, effective parallel algorithms are needed. This work aimed to develop a suitable parallel longest common subsequence (LCS) algorithm for pairwise sequence alignment. The proposed parallel LCS (PLCS) performed approximately 23-30% better than the traditional serial LCS, when using the median run-time as the measure.

Article Details

How to Cite
P. Tantichukaitikul, S. Hattirat, and H. J. Chan, “Parallel Pairwise Sequence Alignment Algorithm Based on Longest Common Subsequence”, JIST, vol. 1, no. 2, pp. 1–10, Dec. 2010.
Research Article: Soft Computing (Detail in Scope of Journal)


1. J. A. Kahle, M. N. Day, H. P. Hofstee, C. R. Johns, T. R. Maeurer, and D. Shippy, “Introduction to the cell multiprocessor,” IBM J. Res. & Dev., vol. 49, no. 4/5, pp. 589-604, 2005.

2. A. Driga, P. Lu, J. Schaeffer, D. Szafron, K. Charter and I. Parsons, “FastLSA: A Fast, Linear-Space, Parallel and Sequential Algorithm for Sequence Alignment,” Algorithmica, vol. 45, pp. 337-335, 2006.

3. K.-M. Chao and L. X. Zhang, Sequence Comparison: Theory and Method. Springer-Verlag, 2009.

4. C. M. Fraser, J. Eisen, R. D. Fleischmann, K. A. Ketchum, and S. Peterson, “Comparative genomics and understanding of microbial biology,” Emerging Infectious Diseases, vol. 6, no. 5, pp. 505–512, 2000.

5. S. J. Shyu and C. Y. Tsai, “Finding the longest common subsequence for multiple biological sequences by ant colony optimization,” Computers and Operations Research, vol. 36, pp. 73–91, 2009.

6. 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, vol. 48, no. 3, pp. 443-453, 1970.

7. S. R. .Eddy, “What is a hidden Markov model?” Nat Biotech, vol. 22, no. 10, pp. 1315-1316, 2004.

8. A. Buttari, J. Langou, J. Kurzak and J. Dongarra, “A class of parallel tiled linear algebra algorithms for multicore architectures,” Parallel Computing, vol. 35. pp. 38-53, January 2009.

9. D. Geer, “Chip makers turn to multicore processors,” Computer, vol. 38, no. 5, pp. 11-13, 2005.

10. L. Bergroth, H. Hakonen, and T. Raita, “A survey of longest common subsequence algorithms,” Proc. 7th International Symposium on String Processing Information Retrieval (SPIRE’00), Spain, 2000, pp. 39-48.

11. M. A. Weiss, Data Structures and algorithm analysis in C, 2nd Ed. Addison-Wesley, 1997.

12. T. T. Binnewies, Y. Motro, P. F. Hallin, O. Lund, D. Dunn, T. La, D. J. Hampson, M. Bellgard, T. M. Wassenaar and D. W. Ussery, “Ten years of bacterial genome sequencing: comparative-genomics based discoveries,” Functional and Integrative Genomics, vol. 6, pp. 165-185, 2006.