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

作者：刘维; 陈崚

来源：计算机应用, 2006, (06): 1422-1424+1427.

• 生物信息学
• 最长公共子串
• 同字符对 bioinformatics
• the longest common subsequence
• the identical character pair

求生物序列的最长公共子串是生物信息学中最重要的问题之一,提出了该问题的一个快速算法,可对所有初始同字符对并行地寻找其后继同字符对,并记录下相应层次值。最后通过最大层次值回溯得到比对结果。此外,该算法采用了剪枝技术,对于明显不能得出最优比对的同字符将中止其后继的搜索。实验结果证明,本文算法比其他算法速度快、精确度高。

• 单位
  扬州大学; 计算机软件新技术国家重点实验室; 南京大学