CHROMOSOME RECONSTRUCTION FROM PHYSICAL MAPS USING A CLUSTER OF WORKSTATIONS

Ordering clones from a genomic library into physical maps of whole chr omosomes presents a central computational problem in genetics. Chromos ome reconstruction via clone ordering is shown to be isomorphic to the classical NP-complete Optimal Linear Arrangement problem. Parallel al gorithms for simulated annealing and microcanonical annealing based on Markov chain decomposition are proposed and applied to the problem of chromosome reconstruction via clone ordering. These algorithms are im plemented on a cluster of UNIX workstations using the Parallel Virtual Machine (PVM) system. PVM is a software system that permits a heterog eneous collection of networked computers to be viewed by a user's prog ram as a single monolithic parallel computing resource. The parallel a lgorithms are implemented and tested on clonal data derived from Chrom osome IV of the fungus Aspergillus nidulans. Perturbation methods and problem-specific annealing heuristics for the parallel simulated annea ling and parallel microcanonical annealing algorithms are proposed and described. Convergence, speedup and scalability characteristics of th e various parallel algorithms are analyzed and discussed.