A PARALLEL ALGORITHM FOR SOLVING LCS OF MULTIPLE BIOSEQENCES

摘要：

A fast algorithm named FAST_LCS is presented for the longest common substring (LCS) problem. The algorithm firstly seeks the successors of the initial identical character tuples according to successor tables to obtain all the identical tuples and their levels. Then the result of LCS can be obtained by tracing back from the identical character tuple with the complexity of sequentially execution of our algorithm is O(L).Here L is the number of identical character tuples. The time complexity of our parallel algorithm is O(|LCS|), where LCS is This time complexity is independent of the number of sequences n. Some experiments have been conduceted on the gene sequences of tigr database using MPP parallel computer Shenteng 1800. The results show that our algorithm is accurate and more efficient than other LCS algorithms.

关键词： Bioinformatics longest common subsequence identical character tuple

作者: WEI LIU LING CHEN

作者单位: Department of Computer Science,Yangzhou University, Yangzhou 225009 China Department of Computer Science,Yangzhou University, Yangzhou 225009 China;National Key Lab of Novel

会议类型: 国际会议

会议名称: 2006 International Conference on Machine Learning and Cybernetics(IEEE第五届机器学习与控制论坛)

会议地点: 大连

会议语种:英文

页码: 4316-4321

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