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.
Bhandarkar
S M
SM
Department of Computer Science, University of Georgia, Athens 30602-7404, USA.
Chirravuri
S
S
Arnold
J
J
Whitmire
D
D
D000465:Algorithms; D002875:Chromosomes / Q000737:chemistry*; D003001:Cloning, Molecular; D003198:Computer Simulation; D004247:DNA / Q000737:chemistry*; D005821:Genetic Techniques; D015698:Genomic Library; D008390:Markov Chains; D012984:Software
D004247:DNA