A Comparative Study of Various Parallel Longest Common Subsequence Algorithms

International Journal of Computer Trends and Technology (IJCTT)          
© - Issue 2013 by IJCTT Journal
Volume-4 Issue-2                           
Year of Publication : 2013
Authors :M.V.Ramakrishnan, Prof.Mrs.Sumathy Eswaran


M.V.Ramakrishnan, Prof.Mrs.Sumathy Eswaran"A Comparative Study of Various Parallel Longest Common Subsequence Algorithms"International Journal of Computer Trends and Technology (IJCTT),V4(2):183-186 Issue 2013 .ISSN 2231-2803.www.ijcttjournal.org. Published by Seventh Sense Research Group.

Abstract: - Sequence alignment is one of the most important tasks in bio-informatics or computational biology field. It helps identifying the similarity between the biological sequences. Longest Common Subsequence is the fundamental problem for sequence alignment techniques. Due to the emerging growth in bio-informatics applications, new biological sequences with longer length have been used for processing. Sequential algorithmic implementations take more time to find Longest Common Subsequence. Sequential implementations sometimes become intractable for longer biological sequences. To compute Longest Common Subsequence of longer biological sequences more efficiently and quickly, parallel algorithms are used. This paper presents a comparative study of three parallel LCS algorithms.


[1]Smith TF, Waterman MS: Identification of common molecular Subsequence, Journal of Molecular Biology 1990, 215:403-410.
[2]Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two Proteins, J Mol Biol 1970, 48(3):443-453.
[3]Yixi Chen, Andrew Wan and Wei Liu , A fast Parallel Algorithm for finding the Longest Common Subsequence of multiple biosequences , BMC Bioinformatics 2006, 7 (suppl 4): 54, ©2006 Chen et al; licensee BioMed Central Ltd.
[4]An Efficient Fast Pruned Parallel Algorithm for finding LCS in Biosequences, Anale Seria Informatica. Vol. VIII fasc. 1 – 2010.
[5]Parallel Computing the Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability, INFOCOMP 2011: The First International Conference on Advanced Communications and Computation.
[8] http://www.pdb.org
[9] www.ebi.ac.uk

Keywords— Dynamic Programming, EFP_LCS, FAST LCS, Parallel Algorithms, Parallel LCS.