多重生物序列的最长公共子序列的并行算法
本文针对生物序列提出一种快速的求最长公共子序列的并行算法,该算法首先对多条序列建立同字符后续表,随后对于所有的初始同字符组并行地搜索其后继同字符组,以得到所有的同字符组及相应的层次值。最后由最大层次值的同字符组进行回溯,得到相应的比对结果。对于n个序列X1,X2,…,Xn,该算法的并行复杂度为O(|LCS(X1,X2,…,Xn)|),该复杂度与序列个数n无关。定义了一些剪枝操作,以缩小搜索空间,加快处理速度。对tigr数据库中的基因序列在MPP并行处理机深腾1800上进行的实验结果证明,本算法与其它经典的LCS算法相比,不但能够取得准确的结果,而且在速度、效率上有了很大的提高。
生物信息学 最长公共子序列 同字符组 并行算法 搜索空间
刘维 陈峻 陈娟
扬州大学信息工程学院计算机系 扬州 225009 扬州大学信息工程学院计算机系 扬州 225009;南京大学计算机软件新技术国家重点实验室 南京 210093
国内会议
成都
中文
72-75
2006-08-17（万方平台首次上网日期，不代表论文的发表时间）