Related Experiment Videos
Parallel Monte Carlo methods for physical mapping of chromosomes.
Suchendra M Bhandarkar1, Jinling Huang, Jonathan Arnold
1Department of Computer Science, The University of Georgia, Athens, Georgia 30602-7404, USA. suchi@cs.uga.edu
Proceedings. IEEE Computer Society Bioinformatics Conference
|April 20, 2005
Summary
This study presents parallel Monte Carlo methods to reconstruct chromosome physical maps from genomic libraries, tackling complex computational challenges with errors. The approach optimizes probe ordering and spacing for accurate genetic mapping.
Area of Science:
- Genetics
- Computational Biology
- Bioinformatics
Background:
- Physical map reconstruction from genomic libraries is a fundamental computational challenge in genetics.
- Errors in genomic data significantly increase the complexity of physical map reconstruction.
Purpose of the Study:
- To present parallel Monte Carlo methods for maximum likelihood estimation-based physical map reconstruction.
- To address the computational complexity associated with error-prone physical map reconstruction.
Main Methods:
- A two-tier parallelization strategy was employed, combining gradient descent search and a simulated Monte Carlo algorithm.
- Gradient descent determined optimal probe spacings for a given probe order.
- Simulated Monte Carlo algorithms identified the optimal probe ordering.
Main Results:
- The study details the implementation of these parallel methods.
- Experimental results were obtained using a network of shared-memory symmetric multiprocessors (SMPs).
Conclusions:
- The presented parallel Monte Carlo approach offers a computationally efficient solution for physical map reconstruction.
- This method effectively handles errors in genomic data, improving the accuracy of genetic mapping.