Parallel Monte Carlo methods for physical mapping of chromosomes.
Reconstructing a physical map of a chromosome from a genomic library presents a central computational problem in genetics. Physical map reconstruction in the presence of errors is a problem of high computational complexity. Parallel Monte Carlo methods for a maximum likelihood estimation-based approach to physical map reconstruction are presented. The estimation procedure entails gradient descent search for determining the optimal spacings between probes for a given probe ordering. The optimal probe ordering is determined using a simulated Monte Carlo algorithm. A two-tier parallelization strategy is proposed wherein the gradient descent search is parallelized at the lower level and the simulated Monte Carlo algorithm is simultaneously parallelized at the higher level. Implementation and experimental results on a network of shared-memory symmetric multiprocessors (SMPs) are presented.
Bhandarkar
Suchendra M
SM
Department of Computer Science, The University of Georgia, Athens, Georgia 30602-7404, USA. suchi@cs.uga.edu
Huang
Jinling
J
Arnold
Jonathan
J
D000465:Algorithms; D003205:Computing Methodologies; D015342:DNA Probes / Q000235:genetics*; D016013:Likelihood Functions; D008957:Models, Genetic; D015233:Models, Statistical; D009010:Monte Carlo Method; D020161:Physical Chromosome Mapping / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D015342:DNA Probes