其中,基于CREW-PRAM算法模型,Aggarwal和Aprostolico等人提出了采用 mn/logm个处理机器,其时间复杂度为O(logmlogn)的并行LCS算法,其中,m和n分别为两个比较字符串的长度,并且。通过相同的计算模型,Lu和Lin在mn/logm个处理器下分别提出了两种其时间复杂度分别为O(log2m+logn)和O(logn)(当时)的并行LCS算法。Babu和Saxena对此进行了改进。Freschi和Bogliolo采用某种数组及m+n个处理器,基于RLE(Run-Length-Encoded String)提出了一种新的 LCS 并行算法,其算法的时间复杂度为 O(m'n+mn'−m'n'),其中,m'和n'是为两个比较字符串运行在RLE上的数量。基于支配点的方法,Korkin等人首先提出了其时间复杂度为O(s|D|)的并行MLCS算法。Liu和Chen亦基于支配点方法,通过有效的裁剪技术,提出了在字符集Σ={A,C,G,T}下其时间复杂度为 O(|MLCS|)高效的并行算法FAST_LCS。Korkin和Wang所提出的并行MLCS算法parMLCS是经典的MLCS串行算法的并行实现。而Wang等人采用支配点方法和分而治之的比较支配点方法,所提出的MLCS并行算法Quick-DP的时间性能高于现有最好的MLCS并行算法多个数量级。值得一提的是:Yang等人作为一种新的尝试,基于GPU开发了一种有效的并行LCS算法,但遗憾的是,该算法并不适合MLCS问题。

第三章  LCS/MLCS问题的算法

在目前的LCS/MLCS算法中,FAST_LCS和Quick_DP是最具代表性的,它们的效率也是目前的算法中非常优异的,在研究它们的过程中,也对FAST_LCS做出一些改进。

3。1 FAST_LCS

3。1。1 匹配点和它的后继表

,是两个生物序列,其中。可以定义4个字符的数组CH(1)=“A”,CH(2)=“C”,CH(3)=“G”, CH(4)=“T”。为了能找到X,Y的最长公子序列(LCS),先建立两个字符串匹配点的后继表[14]。X和Y的匹配点的后继表分别被标记为TX,TY,分别需要一个大小为4(n+1)*4*(m+1)的二维数组。对于字符序列在表TX中被定义如下

           (3-1)

其中,i=1,2,3,4,j=0,1,…,n从定义中可知如果TX(i,j)不为-,其值为第j点之后下一个与CH(i)相匹配的点,否则意味着第j个点之后没有字符与之相匹配。

例子1:X=“TGCATA”, Y=“ATCTGAT”,它们的后继表TX和TY如表3-1和3-2所示。对于字符序列X,Y,如果称它们为CH(k)的匹配字符对,并标记为(i,j)。X与Y的所有匹配点的集合为S(X,Y)。

表3-1 TX的后继表

i CH(i) 0 1 2 3 4 5 6

1 A 4 4 4 4 6 6

2 C 3 3 3

3 G 2 2

上一篇:java+mysql云平台的移动考试系统设计
下一篇:射频识别技术的公司会议签到系统后台子系统设计

基于PageRank算法的网络数据分析

大电流LED驱动器LTC3454【506字】

Windows操作系统最新补丁大全【3058字】

ERP技术发展的现状趋势及...

网页恶意代码的十一大危...

大网络环境下的数据挖掘用户的行为挖掘

C#+sqlserver大学体育馆预订管理系统设计

我国风险投资的发展现状问题及对策分析

麦秸秆还田和沼液灌溉对...

LiMn1-xFexPO4正极材料合成及充放电性能研究

互联网教育”变革路径研究进展【7972字】

老年2型糖尿病患者运动疗...

新課改下小學语文洧效阅...

安康汉江网讯

ASP.net+sqlserver企业设备管理系统设计与开发

张洁小说《无字》中的女性意识

网络语言“XX体”研究