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-speci®c annealing heuristics in the context of the physical mapping problem. We describe implementations of parallel Single Instruction Multiple Data (SIMD) algorithms on a 2048processor MasPar MP-2 system and implementations of parallel Multiple Instruction Multiple Data (MIMD) algorithms on an 8-processor Intel iPSC/860 system and on a cluster of UNIX workstations using the Parallel Virtual Machine (PVM) system. We discuss and analyze the convergence, speedup and scalability characteristics of the aforementioned algorithms. We show the best SIMD algorithm to have a speedup of 1232 on the 2048 processor MasPar MP-2 system and the best MIMD algorithm to have a speedup of 5.35 on the 8-processor Intel iPSC/ 860 system and 3.40 on a 6-workstation cluster running PVM.