| PRAM和LARPBS模型上有向序列翻转距离并行算法 |
| |
| 引用本文： | 沈一飞,陈国良,张强锋.PRAM和LARPBS模型上有向序列翻转距离并行算法[J].软件学报,2007,18(11):2683-2690. |
| |
| 作者姓名： | 沈一飞 陈国良 张强锋 |
| |
| 作者单位： | 中国科学技术大学,计算机科学技术系,安徽,合肥,230027;国家高性能计算中心(合肥),安徽,合肥,230027 |
| |
| 摘 要： | 分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn).
|
| 关 键 词： | 并行算法 光总线并行模型 反转距离 基因组重排 序列比较 CREW-PRAM模型 |
| 收稿时间： | 2006-01-17 |
| 修稿时间： | 2006-06-27 |
Parallel Algorithms for Reversal Distance of Permutations on PRAM and LARPBS |
| |
| SHEN Yi-Fei,CHEN Guo-Liang and ZHANG Qiang-Feng.Parallel Algorithms for Reversal Distance of Permutations on PRAM and LARPBS[J].Journal of Software,2007,18(11):2683-2690. |
| |
| Authors: | SHEN Yi-Fei CHEN Guo-Liang and ZHANG Qiang-Feng |
| |
| Affiliation: | 1.Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027, China; 2.National High Performance Computing Center at Hefei, Hefei 230027, China |
| |
| Abstract: | This paper presents two parallel algorithms to compute reversal distance of two signed permutations on different models. These two algorithms are based on Hannenhalli and Pevzner's theory and composed of three key steps: Construct break point graph, compute the number of cycles in break point graph and compute the number of hurdles in break point graph. The first algorithm runs in O(log2n) time using O(n2) processors in SIMD-CREW model. The second one can solve the problem in O(logn) bus cycles by using O(n3) processors on the linear array with a reconfigurable pipelined bus system (LARPBS). |
| |
| Keywords: | parallel algorithm optical bus parallel model reversal distance genome rearrangements sequence comparison CREW-PRAM model |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
