Parallel computation of a maximum-likelihood estimator of a physical map

Area of Science:

• Genetics
• Computational Biology
• Bioinformatics

Background:

• Chromosome physical map reconstruction from genomic libraries is a fundamental computational challenge in genetics.
• Error-prone data significantly increases the computational complexity of this problem, necessitating advanced solutions.

Purpose of the Study:

• To develop and present parallelization strategies for a maximum-likelihood estimation (MLE) approach to physical map reconstruction.
• To address the computational complexity of physical map reconstruction with errors using parallel computing.

Main Methods:

• A two-level parallelization strategy was proposed, combining gradient descent and stochastic optimization algorithms.
• The gradient descent search was parallelized at a lower level for probe spacing optimization.
• Stochastic optimization algorithms, such as simulated annealing, were parallelized at a higher level for probe ordering.

Main Results:

• The study implemented and tested the parallelization strategy on a distributed-memory multiprocessor cluster using the Parallel Virtual Machine (PVM) environment.
• Experimental results were obtained using both simulated and real hybridization data, demonstrating the effectiveness of the approach.

Conclusions:

• The proposed two-level parallelization strategy offers an efficient computational solution for reconstructing accurate chromosome physical maps.
• This approach effectively handles errors in genomic data, advancing the field of computational genetics.