毕业论文移动版

其中，基于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 — — — — (责任编辑：qin)