PARODS——一项关于DNA序列排序并行算法的研究。

PARODS--a study of parallel algorithms for ordering DNA sequences.

作者信息

Bhandarkar S M, Chirravuri S, Arnold J

机构信息

Department of Computer Science, University of Georgia, Athens 30602-7404, USA.

出版信息

Comput Appl Biosci. 1996 Aug;12(4):269-80. doi: 10.1093/bioinformatics/12.4.269.

DOI:10.1093/bioinformatics/12.4.269

PMID:8902353

Abstract

A suite of parallel algorithms for ordering DNA sequences (termed PARODS) is presented. The algorithms in PARODS are based on an earlier serial algorithm, ODS, which is a physical mapping algorithm based on simulated annealing. Parallel algorithms for simulated annealing based on Markov chain decomposition are proposed and applied to the problem of physical mapping. Perturbation methods and problem-specific annealing heuristics are proposed and described. Implementations of parallel Single Instruction Multiple Data (SIMD) algorithms on a 2048 processor MasPar MP-2 system and implementations of parallel Multiple Instruction Multiple Data (MIMD) algorithms on an 8 processor Intel iPSC/860 system are presented. The convergence, speedup and scalability characteristics of the aforementioned algorithms are analyzed and discussed. The best SIMD algorithm is shown to have a speedup of approximately 1000 on the 2048 processor MasPar MP-2 system, whereas the best MIMD algorithm is shown to have a speedup of approximately 5 on the 8 processor Intel iPSC/860 system.

摘要

提出了一套用于对DNA序列进行排序的并行算法（称为PARODS）。PARODS中的算法基于早期的串行算法ODS，ODS是一种基于模拟退火的物理映射算法。提出了基于马尔可夫链分解的模拟退火并行算法，并将其应用于物理映射问题。提出并描述了微扰方法和针对特定问题的退火启发式算法。给出了在2048处理器的MasPar MP-2系统上并行单指令多数据（SIMD）算法的实现，以及在8处理器的Intel iPSC/860系统上并行多指令多数据（MIMD）算法的实现。分析和讨论了上述算法的收敛性、加速比和可扩展性特征。结果表明，最佳的SIMD算法在2048处理器的MasPar MP-2系统上的加速比约为1000，而最佳的MIMD算法在8处理器的Intel iPSC/860系统上的加速比约为5。