Parallel computing for chromosome reconstruction via ordering of DNA sequences

摘要

In this paper we present our practical experience with the design and implementation of a suite of parallel algorithms called PARODS, for chromosome reconstruction via ordering of DNA sequences. PARODS contains parallel algorithms based on an earlier serial algorithm ODS which is a physical mapping algorithm based on simulated annealing. The parallel Simulated annealing(PSA)algorithms for physical mapping in PARODS are based on Markov chain decomposition. We propose and describe perturbation methods and problem- Specific annealing heuristics in the context of the physical mapping problem.