Bhandarkar S M, Chirravuri S, Arnold J, Whitmire D
Department of Computer Science, University of Georgia, Athens 30602-7404, USA.
Pac Symp Biocomput. 1996:85-96.
Ordering clones from a genomic library into physical maps of whole chromosomes presents a central computational problem in genetics. Chromosome reconstruction via clone ordering is shown to be isomorphic to the NP-complete Optimal Linear Ordering problem. Massively parallel algorithms for simulated annealing based on Markov chain distribution are proposed and applied to this problem. Perturbation methods and problem-specific annealing heuristics are proposed and described. Experimental results on a 2048 processor MasPar MP-2 system are presented. Convergence, speedup and scalability characteristics of the various algorithms are analyzed and discussed.
将基因组文库中的克隆排序到完整染色体的物理图谱中是遗传学中的一个核心计算问题。通过克隆排序进行染色体重建被证明与NP完全的最优线性排序问题同构。提出了基于马尔可夫链分布的大规模并行模拟退火算法并将其应用于该问题。提出并描述了扰动方法和特定问题的退火启发式算法。给出了在2048处理器的MasPar MP-2系统上的实验结果。分析并讨论了各种算法的收敛性、加速比和可扩展性特征。
