PARODS - A STUDY OF PARALLEL ALGORITHMS FOR ORDERING DNA-SEQUENCES

A suite of parallel algorithms for ordering DNA sequences (termed PARO DS) is presented. The algorithms in PARODS are based on an earlier ser ial algorithm, ODS, which is a physical mapping algorithm based on sim ulated 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 Si ngle Instruction Multiple Data (SIMD) algorithms on a 2048 processor M asPar MP-2 system and implementations of prvallel Multiple Instruction Multiple Data (MIMD) algorithms on an 8 processor Intel iPSC/860 syst em ave presented. The convergence, speedup and scalability characteris tics of the aforementioned algorithms are analyzed and discussed. The best SIMD algorithm is shown to have a speedup of similar to 1000 on t he 2048 processor MasPar MP-2 system, whereas the best MIMD algorithm is shown to have a speedup of similar to 5 on the 8 processor Intel iP SC/860 system.