最长公共子序列的快速算法及其并行实现  

Parallel longest common subsequence algorithm based on pruning technology

作　　者：刘维[1] 陈崚[1] 

机构地区：[1]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机应用》2006年第6期1422-1424,1427,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(60473012);国家科技攻关项目(2003BA614A-14);江苏省自然科学基金(BK20005047)

摘　　要：求生物序列的最长公共子串是生物信息学中最重要的问题之一,提出了该问题的一个快速算法,可对所有初始同字符对并行地寻找其后继同字符对,并记录下相应层次值。最后通过最大层次值回溯得到比对结果。此外,该算法采用了剪枝技术,对于明显不能得出最优比对的同字符将中止其后继的搜索。实验结果证明,本文算法比其他算法速度快、精确度高。Searching for the Longest Common Substfing （LCS） of biosequenees is one of the most important problems in Bioinformaties. Smith-Waterman algorithm and FASTA algorithm are currently the most widely used algorithms. FASTA algorithm runs faster than Smith-Waterman algorithm, but Smith-Waterman algorithm can obtain higher precision. A fast algorithm for LCS problem was presented. The algorithm seeks the successors of the identical character pairs in parallel according to a successor table and record their levels. Finally it traces back from identical character pair with the largest level and get the result of LCS.

关 键 词：生物信息学 最长公共子串 同字符对 

分 类 号：TP37[自动化与计算机技术—计算机系统结构]