A Parallel Algorithm for Longest Common Substring of Multiple Biosequences

摘要：

A parallel algorithm FAST_LCS for the longest common substring (LCS) problem is presented. For two sequences X and Y with length n and m, the time complexity of parallel computing is O (|LCS(X, Y)|), where |LCS(X,Y)| is the length of the LCS of X, Y. For n biosequences X1, X2,...,Xn, time complexity of our parallel algorithm is O(|LCS(X1, X2,..., Xn )|) which is independent of the number of sequences n. Experimental result on the gene sequences of tigr database shows that our algorithm is faster and more efficient than other LCS algorithms and can get exactly correct result.

关键词： bioinformatics longest common subsequence

作者: Wei Liu Ling Chen

作者单位: Department of Computer Science, Yangzhou University Yangzhou 225009 China National Key Lab of Novel Software Tech, Nanjing University Nanjing 210093 China

会议类型: 国际会议

会议名称: 2006 International Symposium on Distributed Computing and Applications to Business,Engineering and Science(2006年国际电子、工程及科学领域的分布式计算应用学术研讨会)

会议地点: 杭州

会议语种:英文

页码: 13-17

在线出版日期: 2006-10-12（万方平台首次上网日期，不代表论文的发表时间）