Parallel Computation of a Maximum-Likelihood Estimator of a Physical Map

Parallel Computation of a Maximum-Likelihood Estimator of a Physical Map

Suchendra M. Bhandarkar^a, Salem A. Machaka^a, Sanjay S. Shete^b, and Raghuram N. Kota^a
^a Department of Computer Science, The University of Georgia, Athens, Georgia 30602-7404
^b Department of Statistics, The University of Georgia, Athens, Georgia 30602-7404

Corresponding author: Suchendra M. Bhandarkar, Department of Computer Science, The University of Georgia, 415 Boyd Graduate Studies Research Ctr., Athens, GA 30602-7404., suchi{at}cs.uga.edu (E-mail)

Communicating editor: J. ARNOLD

Reconstructing a physical map of a chromosome from a genomiclibrary presents a central computational problem in genetics.Physical map reconstruction in the presence of errors is a problemof high computational complexity that provides the motivationfor parallel computing. Parallelization strategies for a maximum-likelihoodestimation-based approach to physical map reconstruction arepresented. The estimation procedure entails a gradient descentsearch for determining the optimal spacings between probes fora given probe ordering. The optimal probe ordering is determinedusing a stochastic optimization algorithm such as simulatedannealing or microcanonical annealing. A two-level parallelizationstrategy is proposed wherein the gradient descent search isparallelized at the lower level and the stochastic optimizationalgorithm is simultaneously parallelized at the higher level.Implementation and experimental results on a distributed-memorymultiprocessor cluster running the parallel virtual machine(PVM) environment are presented using simulated and real hybridizationdata.

This article has been cited by other articles:

Z. Xu, B. Lance, C. Vargas, B. Arpinar, S. Bhandarkar, E. Kraemer, K. J. Kochut, J. A. Miller, J. R. Wagner, M. J. Weise, et al.
Mapping by Sequencing the Pneumocystis Genome Using the Ordering DNA Sequences V3 Tool
Genetics, April 1, 2003; 163(4): 1299 - 1313.
[Abstract] [Full Text] [PDF]

H. S. Kelkar, J. Griffith, M. E. Case, S. F. Covert, R. D. Hall, C. H. Keith, J. S. Oliver, M. J. Orbach, M. S. Sachs, J. R. Wagner, et al.
The Neurospora crassa Genome: Cosmid Libraries Sorted by Chromosome
Genetics, March 1, 2001; 157(3): 979 - 990.
[Abstract] [Full Text]

V. Aign, U. Schulte, and J. D. Hoheisel
Hybridization-Based Mapping of Neurospora crassa Linkage Groups II and V
Genetics, March 1, 2001; 157(3): 1015 - 1020.
[Abstract] [Full Text]

D. Hall, S. M. Bhandarkar, and J. Wang
ODS2: A Multiplatform Software Application for Creating Integrated Physical and Genetic Maps
Genetics, March 1, 2001; 157(3): 1045 - 1056.
[Abstract] [Full Text]

				H. S. Kelkar, J. Griffith, M. E. Case, S. F. Covert, R. D. Hall, C. H. Keith, J. S. Oliver, M. J. Orbach, M. S. Sachs, J. R. Wagner, et al. The Neurospora crassa Genome: Cosmid Libraries Sorted by Chromosome Genetics, March 1, 2001; 157(3): 979 - 990. [Abstract] [Full Text]

				V. Aign, U. Schulte, and J. D. Hoheisel Hybridization-Based Mapping of Neurospora crassa Linkage Groups II and V Genetics, March 1, 2001; 157(3): 1015 - 1020. [Abstract] [Full Text]

				D. Hall, S. M. Bhandarkar, and J. Wang ODS2: A Multiplatform Software Application for Creating Integrated Physical and Genetic Maps Genetics, March 1, 2001; 157(3): 1045 - 1056. [Abstract] [Full Text]