International Journal of Computer
Trends and Technology

Research Article | Open Access | Download PDF

Volume 4 | Issue 2 | Year 2013 | Article Id. IJCTT-V4I2P126 | DOI : https://doi.org/10.14445/22312803/IJCTT-V4I2P126

A Comparative Study of Various Parallel Longest Common Subsequence Algorithms

M.V.Ramakrishnan, Prof.Mrs.Sumathy Eswaran

Citation :

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), vol. 4, no. 2, pp. 183-186, 2013. Crossref, https://doi.org/10.14445/22312803/IJCTT-V4I2P126

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.

Keywords

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

References

[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.
[6]ftp://ftp.ebi.ac.uk/pub/databases/fastafiles/asd/
[7]ftp://ftp.ebi.ac.uk/pub/databases/pdb_seq/
[8] http://www.pdb.org
[9] www.ebi.ac.uk