基于剪枝跳跃技术的最长公共子序列算法

计算机科学 20 0 6 V o l. 3 3吻 . 8 (增刊) 基于剪枝跳跃技术的最长公共子序列算法 ‘ ) A n A lg o r ithm fo r So l v in g Lo n g es t Co m m o n S u b se q u e n e e Ba se d o n Pr u n in g a n d Sk ip pi n g R u le s 刘 维 , 陈 峻1,2 (扬州大学信息工程学院计算机系 扬州 22 500 9) ‘ (南京大学计算机软件新技术国家重点实验室 南京 2100 9 3) ’ A坛七节d th e in itia l by tra e ing FA g 几】丈万 15 Pre s e n ted. T he a lgo ri thm fi to a su e ce sso r ta ble to o b t巨n all the id en tica l rs t see k s t he su e ee sso rs o f 件irs a n d the ir le v e ls . Th e n肥Lcaltheter Pa lr诚th the la落e s t lev e l, the res u lt o fLCS ca n be o bta in e比FO r two箕器辍盖黑轰黯饥蕊银黑忿窦架黯盘蜜尝架黯浦;。。m pu ta ti呱 E x pe r im e n ta l re sul t o n the g en e s叹uenc e s o f tig r d a ta ba s e sh o w s tha re e t re s u lt a n d 15 fa s te r a n d me re eff i e ien t tha n o the r LCS al g o ri thm s . 众州份山 Bi o in fo rma tie s , Lo 咚e s t co n ”刀o n s u b s闪 uen e e , Ide n tica le ho e ter 琳ir he re L 15 the n um be r of 记e n t i sea rc h吨 sPa ce a n d acce le ra te the t o u r a lgo ri thm can ge t exa e t co r - 1 引言 在生物信息学中[1, 2〕, 对 D N A 的研究实质上就 是对生物序列进行比较分析比月 , 通过检测其相似 成分来探测其生物特性的相似性 。 而探测序列相似 性的方法之一就是找出序列间的最长公共子序列 (LCS )阁 。 本文提出一种快速的最长公共子序列的 算法 FA S毛 LCS 。 对于长度为 n 和 m 的两序列 X , Y , 该算法所需的计算时间为 O (L ) , 这里 L 指同 字符对的个数 。 实验结果证明 , 本文算法与其它经 典的 LCS 算法相比 , 不但能够取得准确的结果 , 而 且在速度 、效率上有了很大的提高。 G A T ”则 T X 及 T Y 分别为 : 丁X : iiiii CH(i))) 0 1 2 3 4 5 666 11111 AAA 4 4 4 4 6 6 一一 22222 CCC 3 3 3 一 一 一 一一 33333 GGG 2 2 一 一 一 一 一一 44444 TTT 1 5 5 5 5 一 一一 2 同字符后续 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 及其同字符对 设欲比对的生物序列分别为 X ~ (x ; , x : , ⋯ , x , ) , Y = (夕1 , 少: , ⋯ , 为 ) , 其中 , x ‘, 夕、任 {A , C , G , T} 。 为了找出这两条序列的最长公共子序列 , 我们 首先要对这两条序列分别建立同字符后续表 。 我们 定义 ‘A ’ = C H (l ) , ‘C ’= C H (2 ) , ‘ G ’ = CH (3 ) , ‘ T , ~ C H (4) , 将 X , Y 的同字符后续表分别记为 T X , T Y , 这里 , T X 、 T Y分别为 4 二 (n + l ) 、 4 , (m + l) 的二维数组 。 我们对 T X (i , j) 定义如下 : ~ , , , 二 、 lm in {k }k e S X (i , z ) } S X (i , j)笋价, , 、 T X (i , j) 一 ( ” - 一 ” ‘ ” 一丁一 ‘ “ ’ . ” (l ) } 一 o th e rw ise ’ 一 ’ 其中 SX (i , j) = {k lx 。= CH (i ) , k > j} , i = l , 2 , 3 , 4 , j 一 。, 1 , ⋯ , n 。 “ 一 ”表示无定义 。 由此定义 可知 , 若 T X (i , j) 不为“一 ” , 它表示 X 第 j 个字符 后面第一个为 C H (i) 的字符的位置 。 例 1 设 X = “T G C A T A , , , Y = “A T C T iiiii CH (i))) 0 1 2 3 4 5 6 777 11111 AAA 1 6 6 6 6 6 一 一一 22222 CCC 3 3 3 一 一 一 一 一一 33333 GGG 5 5 5 5 5 一 一 一一 44444 TTT 2 2 4 4 7 7 7 一一 在 X 、Y 中 , 若有 x ‘一 为 , 则记(i , j) 为一个同 字符对 。 X 、Y 所有同字符对的集合记为 S (X , Y ) 。 若(i , j) 、 (k , l) 皆为同字符对 , 且有 i< k 、 j< l则 称(i , j)为(k , l)的一个前驱 , 或称 (k , l)为(i , j) 的一个后继 , 记为(i , j) < (k , l) 。 若设集合 尸(i , j)= {( 犷 , : )I(i , j)< ( r , s ) , (r , s)e s (x , y )}为 (i , j) 的所有后继同字符对集合 , 若有(k , l)任尸“ , j) , 且不存在(走‘ , z ‘)任P (i , j) , 使得 : (走, , z‘)< (掩, l) , 则称 (k , l) 为“ , j) 的直接后继 , 记为(l’ , j) < (k , l) 。 对没有前驱的同字符对 , 我们称为初始同 字符对 。 对任意的同字符对(i , j) e s (X , Y ) , 它的 层次号 le ve l(i , j) 定义为 : 门 if(i , i)为一初始同字符对 Z批l(i, j)= 弓ma x {Z粼Z(k , l)+ l }(k , l)< (i , 少)} (2 ) (o therwi se 二 )基金项 目: 国家自然科学基金 (604 7 301 2 ) ;国家科技攻关项目(2 00 3 BA 6 1 4 A 一 14 ) ;江苏省 自然科学基金 (HK 2 0() 5 04 7 ) 。 刘 维 硕 I 研究 生 , 主要研究方向为算法优化和并行计算。 陈 峨 教授 , 博士生导师 , 主要研究方向为算法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 和并行计算 。 · 3 2 2 · 记 X 、Y 最长公共子序列的长度为 }I刃S( X , Y ) } , 则 }I一S (X , Y ) }= m a x {leve l (i , j) }(i, j )任 S (X , Y ) } 。 3 产生后继及剪枝跳跃操作 在我们的算法中 , 首先对所有初始同字符对利 用同字符后续表产生其所有的直接后继 , 然后再对 这些后继并行地产生其所有直接后继 。 重复这样的 操作 , 直至不能继续产生后继为止 。 对某同字符对 (i , j)任S (x ,必 , 由(i , j)产生其所有后继同字符对 的操作可表示为 : (i , j)” {(T X (k , i) , T Y (k , j)) }k = l , 2 , 3 , 4 , T X (乏, i)井 , 一‘a n dT Y (走, j)护 , 一 ‘} (3) 即对 T X 的第 i 列 、 T Y 的第 j 列相应元素配成对 偶 。 例如对例 1 中的同字符对 (2 , 5 ) , 上述操作可 表示为 : 输人 :长度分别为 m , n 的序列 X , Y ; 输出 : X , Y 的最长公共子序列 IJCS( X , Y ) ; Be g i n 1 . 构造 了火 , T Y表 ; 2 . 找出所有的初始同字符对 : (了次(k , 0 ) , T Y (k , 0 )) , k - 2 , 3 , 4 ; le理l= 1 ; 3 . 将所有初始同字符对 (h , TX (k , o ) , T Y(k , o ) , 1 ,叻, a e ti* ) . k = l , 2 , 3 , 4 加人到表 力a irs 中 。 / , 对所有初始同字符对 ,赋予层号 1 , 户耐= 办 , ta te = a’’ - ti 货 ’ / 4 . w hile 表 Pa irs 中有处于 a c ti* 状态的项 do 4 . 1 对表 Pai rs 中所有层号为 le * l的同字符对进行剪枝 ,将所有冗余的同字符对从表中去掉 4 . 2 对表 如 irs 中所有层号为 le * l的活动同字符对 (k , i , j , l。红Pre d , ac ti * )并行地进行 : 4 . 2 . 1 使用产生后继操作和跳跃操作产生 (k , i, J l绷l, P理d , h , l粼l+ 1 , ac t i* )的所有后 k , a e ri* ) , 再将 i (k ’ , g , 人到表 P.a irs 中; 4 . 2 . 2 将 (k , i , j, le , l, Pre d , a c ri* )的状态置为 in - a e t i优 . 4 . 3 le货l= le货l十 l; en d w hile 计算 r = 表 Pa irs 中的最大层次值 . 对于表中进行 : 字符对 (k , i , J , : , l , in a o ri* )并行地 6 . 1 6 . 2 En d l; LCS( r )= rs 中得到其前驱 (Pre d , g , h , : ‘ , 即 (2 , 5)的后继为 (4 , 6 )和 (5 , ina cti优 ) 6 . 2 . ZPred = l ‘ , LCS ( r ‘)= x’ 左‘口匕 一 ‹eeweweesleses‘seseesesJ6)--)幼7)7)刀任nj一二†了气了.、。了吸、r‘eseseseseseses‘es卜esL ” ‹.leses,eeweesesesesJ6一一743一5一!se⋯esL今亡J9白 。 对任一同字符 对 (i , j) , 反复使用上述方法可 以产生其所有的后 继 。 ( T X ( k , 0 ) , T Y( k , O) ) , k = l , 2 , 3 , 4 , 为 X 、 Y 的所有初始同字符对 。 由这些初始同字符对 , 我们 可以得到所有同字符对及其层次值。 在利用上述方 法产生后继同字符对的过程中 , 我们可进行剪枝跳 跃操作 , 删除某些明显不能得出最长公共子序列的 同字符对 , 以缩小搜索空间 、加快搜索速度 。 定理 1 如果在同一层上所产生的同字符对 ( i , j )和 (k , l)中 , 有 ( k , l) > ( i , j) , 则删去 ( k , l ) 不影响算法得到最优解 。 由于篇幅限制 , 定理 1 的证明略去 。 根据定理 1 , 我们可以在每一层产生同字符对后进行剪枝及跳 跃操作。 类似于定理 1 , 还有一些有用的剪枝跳跃 操作 。 这些操作基于如下一些定理和推论 。 定理 2 若在同一层中有同字符对 (i ; , j) 及 ( i : , j) , 其中 11 < i : , 则 ( i : , j)可以剪去 。 推论 1 若在同一层中 , 有 同字符对 “ 1 , j) , ( i : , j) , ⋯ , ( i , , j) , 其中 i , ( 12 < ⋯< i r , 则 ( i : , j) , ⋯ , “r , j) 可以剪去 。 由于篇幅限制 , 定理 2 和推论 1 的证明略去 。 4 算法框架及复杂性分析 在算法中 , 我们设立一个同字符对表 Pai r.c , 表 中的每一项由四元组 ( k , i , j , le ve l , 户re d , s ta te ) 构成 , 分别表示 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 号 、 同字符对“ , j) 、层次号 、直 接前驱以及当前的状态 。 算法框架如下 : 算法 FA S Il I JCS ( X , Y ) 设 X , Y 中同字符对的个数为 L , 由于剪枝跳跃 技术 , 本算法对 X 、Y 中所有同字符对至多进行一次 产生后继操作 , 因此算法 FA ST-- I刃S( X , Y )串行执 行的过程至多为对所有同字符对进行一次产生后继 操作的过程 , 因此算法的时间复杂度为 O (L ) 。 由 于表 Pai rs 记录所需处理的同字符对 , 其所占的存 储空间为 O (L ) , 同字符后续表 T X , T Y 的存储空间 分别为 4 , ( n + l )及 4 二 (m + 1 ) 。 本文算法所需的 存储复杂度为 m a x {4 , ( n + 1 ) + 4 , ( m + l ) , L ) 。 5 实验结果及分析 我们从 ti gr 圈数据库中抽取 了稻谷基因序列对 本文算法 FA ST ~ IJCS 进行了实验 , 并将本文算法 分别 与 目前应 用最 广泛 的 Sm ith一W a t e rm a n 算 法 [7, 8〕及 FA ST A 算法比‘0] 在速度上进行了比较 , 由 于本文算法与 Sm ith一W at er m an 算法都可 以得到精 确解 , 因此我们将 FA S T 一 I .C S 算法与 Sm it h一w a - te rm a n 算法在速度上作了比较 , 同样地 , 我们在计 算时间相同的前提下 , 也将本文算法与 FA ST A 算 法在精度上作了比较 。 我们对不同长度的基因组序列使用本文算法 FA ST _ I J CS 与 Sm ith- W a te r m a n 算法分别进行了 测试 , 并在计算速度上作了比较 。 结果如图 1 所示 。 由图 1 可以看出 , 对于不同长度的序列 , 本文算法要 明显快于 S m it h一W a te r m a n 算法 。 在输人序列长度 为 15 0 之前 , 两者速度差距变化较为缓慢 , 而在序列 长度为 1 5 0 之后 , 速度差距变化异常迅速 , 本文算法 · 3 2 3 · 的速度大大超过 SW 算法 。 由此可见 , 对于长序列 的 LCS 问题 , 本文算法和 SW 算法虽然都能获得精 确的解 , 但本文算法的速度更快 、效率更高 。 ƒ巴回蓄 . 已公 暇甘9一哎†, .‘匕dC” 50 10 0 1 50 物入序列长度 —FA ST Lc S · · - 二 S W 算法图 1 本文算法 FA ST es LCS 与骊it 卜W at ~ n 算法在计算时间上的比较 娜娜 1 0 2 1 10 0 卜.—~ ~一—一- -9 8 1, 6 1 _ 二 。 。 . · · · · · ·⋯⋯ _9 4 1 -9 2 ’ 一 法 。 结论 为了在不影响精确度的前提下提高 LCS 计算的速度 ,本文提出了基于同字符对的求生 物序列的最长公共子序列的算法 FAST 一 LCS 。 该 算法通过对两条序列建立相应的同字符后续表 , 随 后对于所有的初始同字符对 , 在该表中逐层地搜索 其后继同字符对 , 以得到所有的同字符对及相应的 层次值 。 最后由最大层次值的同字符对进行回溯 , 依次求得其所有前驱同字符对 , 最后得到相应的比 对结果 。 对于长度为 n 和 m 的两序列 X , Y , 该算法 所需的内存为 ma x {4 , ( n + 1 ) + 4 , ( m + l ) , L } , 时间为 O (L ) , 这里 L 指初始同字符对的个数 。 我 们还给出了一些剪枝跳跃操作 , 以加快计算速度 。 我们对 ti gr 数据库中的基因序列进行的实验结果 证明 , 本文算法与其它经典的 LCS 算法相比 , 不但 能够取得准确的结果 , 而且在速度 、效率上有了很大 的提高。 1 0 0 15 0 2 0 0 怡入序列长度 —本文算法 · · · 一FASTA 2 5 0 算法 郝柏林 2 0 00 . 1 参 考 文 献 , 张淑誉 . 生物信息学手册【M〕. 上海科学技术出版杜 , 17 1~ 1 7 2 图 2 本文算法 FA ST 声LCS 与FA ST A 算法在精度上的 比较 译 . 生物信息学~墓因和蛋白质分析的实用指出版杜 , 200 0 . 1 3 8 S B , W u ns ch C n A g en e ra l tha s e a比h fo r s imi l颐t ie s in tbe a而no ad d me t h司 a PP lica ble t o , 叫u en ce of tw O P价 同样地 , 我们用本文算法与 R 玺刃A 算法在计算 时间相同的情况下 ,对计算结果精度进行了比较 , 这里 te in ‘ J . M o】. B io L , 1 9 7 0 , 48 ( 3 ) : 4 4 3一 4 5 3 W a te n l坦 n M 5 I n t r司u c t ion t o l压ol o g y , M a Ps ,濡哭筑恶留晋乞糯恕: 念黔然之恐黑it , 。 fthe LD n g e s t 伪 n妞n o n S u bs 阅 u en 倪 Pro bl翻 , J. As 戏 C冶m p u t.精度是指 :精度= 正确匹配中的最长公共子序列长度’ 其结果如图 2 所示 。 由图 2 可见 , 不管输人序列长 度如何增加 , 本文算法都能够取得准确的结果 , 而 FA ST A 算法则随着序列长度的增加 , 精度明显下 降 。 因此本文算法的精度要明显优于 FAST A 算 M a e 瓦 6 ht tP : / 7 S rn ith , 2 3 ( l ) : 1~ 12乙缪竺.tig r.o 叼芝啊坪件1卿r k , , , l r , W 扭t e n l砚 n n ll 吞 I Q e n t lllCS [ 10 n o ! O o n妞们o n n 洲0 1吧C U I已r 0 , 2 15 : 4 0 3~ 4 1 0 a nd Li即na n D J. 19 9 0 , 2 15 : 4 0 3~ 199w,以,1妇氏su b别殉u e n o已 Jo u m a l o fM o lec u lar Al t s ch u lS F , G i sh W , Mill e r W , 压s ie l临1 al ig 川的e n t sea r e h too l, 4 1 0 压。IO g y My ers 荃 J . M o L 9 ht t p : / / a lpha lo . b ioc 瓦沂匆n ia. 司 u / fas t卜~ /馆i/ 1 0 ht tP: / / 叭八犷钾 . e b i . a e . u k / se 州ces / (上接第 3 1 4 页 ) 且 0 . 7 > 又~ 0 . 6 , 可 以匹配 , 故框架规则 R ul el 可 用 。 º计算结论的可信度 CF ( H ‘, ) , 由于 尸, 一 1 , 尸: ~ 1 , 因此 E’ : 和 厂 : 是 A N D 关系 , 运用式 ( 4) 计 算 cF ( H , 1 ) 一氏。以 ( E , E’ ) x R c x 全cM, 一。. : xi二 I 0 . 6 X ( 1X 0 . 7 + 1X 0 . 3) = 0 . 42 ( 2)按 ( 1) 步骤计算 氏助云 ( E , E ‘) 和 邵 ( H , : ) 氏耐 ( E , E ‘) = 0 . 8 ) 又= 0 . 6 故框架规则可用 CF ( H ‘: )一 0 . 56 (3) 对于相同的证据却得到两种结果 , 我们采用 匹配度大的那个作为最后结论 , 由于 0 . 8 > 0 . 7 , 故 H ‘: 为最后结果 , 且其可信度为 0 . 56 。 结论 从以上可以看出 , 这种带重要度可信度 框架规则知识表示方法可 以较准确地表示知识 , 它 弥补了单独运用规则表示或框架表示的不足 。 同时 本文把模糊理论的思想运用到这种混合知识表示推 理中 , 具有一定的现实意义 。 在不精确推理中 , 一般 的推理算法 , 都推到终结点 ,其动态强度超过规定的 闭值 , 则为成立 , 否则为不成立 , 而不能在推理过程 中 , 随时就能判断是否还须往下推 , 所以 , 影响了推 理速度 。 本文没有解决这个问题 , 有待于继续研究 解决。 参 考 文 献 l 尹朝庆 , 尹皓 . 人工智能与专家系统〔M」. 北京 :中国水利水电出 版社 , 20 0 2 2 程伟良. 广义专家系统【M」. 北京 : 北京理工大学出版社 , 200 5 3 Go ld ing A R , R o s e n blo Om P S. I m Pro vi ng A cc u ra e y b y Co m b - yi呢 R u le- ha s曰 a nd Ca se- ha s曰 R e a so n i叱 〔J〕. A rt ifie ia l I n te lli- g e n e e , 19 9 6 , 87 ( l一2) : 215一254 4 Za d e h I A . T he R Ol e o f Fu zz y l刀g ie in t he 卜坛n眼 e m e n t o f U n - e ert a in ty in E x详rt 匆s re rns 〔J〕. Fuz z y 反 ts a n d S ys t e m s , 19 8 3 , 11 : 19 9 ~ 227 5 赵瑞清 , 王晖 , 邱涤虹 . 知识表示与推理厂M〕. 北京 :气象出版社 , 19 9 1 6 赵瑞清. 广义规则表示及其推理算法 [月. 计算机学报 , 19 92 . 2 : 120 ~ 127 7 钟绍春 . Proc e s s i呢 o f U n e e r t a in ty T e m po ra l R e la t io n , [J〕. 计算机学报 ( 英文版 ) , 19 9 6 , 11( 1) 32 d