多序列比对问题的并行近似算法  

Some Parallel Approximation Algorithms for Multiple Sequence Alignment Problem

作　　者：宋彬[1] 陈国良[2] 鄢超[2] 沈一飞[2] 

机构地区：[1]中国科学技术大学计算机科学与技术系,安徽合肥230027 [2]国家高性能计算中心,安徽合肥230027

出　　处：《中国科学技术大学学报》2005年第5期656-664,共9页JUSTC

基　　金：国家"863"计划(2001AA111041;2002AA104560);中科院高标准高校建设项目

摘　　要：基于中心方法的思想,采用分治策略,在SIMD-CREW模型上设计了一个使用O(k2m)个处理器(其中k为序列个数,m为最长的序列长度),时间复杂度为O(m+logk)的并行近似算法.在实际情况中,由于logk远远小于m,相对于时间复杂度为O(m2k2)的串行中心方法,该算法在理论上达到线性加速.与现有的并行算法相比,它可以适用于任意情况,且易于分析时间复杂度.利用LARPBS模型的特点和并行求前缀和的方法,调用LARPBS模型上求和与最大(小)值的并行算法,首次给出了在LARPBS模型上的多序列比对问题的并行近似算法.该算法使用O(k2m)个处理器,时间复杂度为O(m+log logD),其中D为序列两两比对的代价值的最大值.该算法同样适用于任何情况,由于log logD通常远小于m,所以它在理论上也是线性加速的.Based on the idea of center star method and the divide-and-conquer strategy, A parallel approximation algorithm on SIMD-CREW model is presented to solve it. The algorithm needs O （m＋log k） time in use of O（k^2m） processors, where k is the number of sequences, rn is the length of the longest sequence. In fact, logk is much less than m, so it obtains a linear speedup in theory and is much faster than the sequential center star method which runs in O（m^2k^2）. It is more efficient than the existing parallel algorithms for multiple sequence alignment, for some of existing ones have been applied to some special situations and some have had trouble analyzing time complexities. The presented algorithm can solve the problem in any situation. On the other hand, the first parallel approximation algorithm is given for multiple sequence alignment on linear arrays with a reconfigurable pipelined bus system （LARPBS）model using the properties of LARPBS model and the technique of parallel computing the prefix sums and applying the parallel algorithms for computing sums and maximum （minimum）on LARPBS. It runs in O（m＋log log D） time by O（k^2m） processors, where D is the highest cost of the optimal pairwise sequence alignments. Especially, O（m＋log log D） is independent of k and related only to m. Then it is much better than the former O（m＋log k） that is on SIMI）-CREW model. Also, the algorithm can be applied in any situation and analyzing time complexity with ease. It obtains a linear speedup in theory, for log log D is much less than m.

关 键 词：多序列比对 并行算法 SIMD-CREW LARPBS模型 SP比对 

分 类 号：TP339[自动化与计算机技术—计算机系统结构] TP301[自动化与计算机技术—计算机科学与技术]