TY - JOUR
T1 - A parallel non-alignment based approach to efficient sequence comparison using longest common subsequences
AU - Bhowmick, S.
AU - Shafiullah, M.
AU - Rai, H.
AU - Bastola, D.
PY - 2010
Y1 - 2010
N2 - Biological sequence comparison programs have revolutionized the practice of biochemistry, and molecular and evolutionary biology. Pairwise comparison of genomic sequences is a popular method of choice for analyzing genetic sequence data. However the quality of results from most sequence comparison methods are significantly affected by small perturbations in the data and furthermore, there is a dearth of computational tools to compare sequences beyond a certain length. In this paper, we describe a parallel algorithm for comparing genetic sequences using an alignment free-method based on computing the Longest Common Subsequence (LCS) between genetic sequences. We validate the quality of our results by comparing the phylogenetic tress obtained from ClustalW and LCS. We also show through complexity analysis of the isoefficiency and by empirical measurement of the running time that our algorithm is very scalable.
AB - Biological sequence comparison programs have revolutionized the practice of biochemistry, and molecular and evolutionary biology. Pairwise comparison of genomic sequences is a popular method of choice for analyzing genetic sequence data. However the quality of results from most sequence comparison methods are significantly affected by small perturbations in the data and furthermore, there is a dearth of computational tools to compare sequences beyond a certain length. In this paper, we describe a parallel algorithm for comparing genetic sequences using an alignment free-method based on computing the Longest Common Subsequence (LCS) between genetic sequences. We validate the quality of our results by comparing the phylogenetic tress obtained from ClustalW and LCS. We also show through complexity analysis of the isoefficiency and by empirical measurement of the running time that our algorithm is very scalable.
UR - http://www.scopus.com/inward/record.url?scp=79952397362&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79952397362&partnerID=8YFLogxK
U2 - 10.1088/1742-6596/256/1/012012
DO - 10.1088/1742-6596/256/1/012012
M3 - Article
AN - SCOPUS:79952397362
SN - 1742-6588
VL - 256
JO - Journal of Physics: Conference Series
JF - Journal of Physics: Conference Series
IS - 1
M1 - 012012
ER -