title: Massively parallel algorithms for chromosome reconstruction.
abstract: 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.
authors.affiliation: Department of Computer Science, University of Georgia, Athens 30602-7404, USA.
authors.forename: S M
authors.initials: SM
authors.lastname: Bhandarkar
authors.forename: S
authors.initials: S
authors.lastname: Chirravuri
authors.forename: J
authors.initials: J
authors.lastname: Arnold
authors.forename: D
authors.initials: D
authors.lastname: Whitmire
mesh_terms: 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
chemical_list: D004247:DNA