Massively parallel algorithms for chromosome reconstruction

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.