Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Parallel computing of physical maps--a comparative study in SIMD and MIMD parallelism

S M Bhandarkar1, S Chirravuri, J Arnold

  • 1Department of Computer Science, University of Georgia, Athens 30602-7404, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1996
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Osteoarthritis consumers as co-researchers: identifying consumer insights to improve osteoarthritis management by co-designing translational research solutions.

Osteoarthritis and cartilage·2023
Same author

Design and function of targeted endocannabinoid nanoparticles.

Scientific reports·2022
Same author

Epilepsy and the smell of fear.

Epilepsy & behavior : E&B·2021
Same author

Identifying a stochastic clock network with light entrainment for single cells of Neurospora crassa.

Scientific reports·2020
Same author

Boot camps in neonatal-perinatal medicine fellowship programs: A national survey.

Journal of neonatal-perinatal medicine·2019
Same author

Fragile: Please handle with care.

Radiography (London, England : 1995)·2018

This study introduces parallel algorithms for ordering genomic clones to reconstruct physical maps. A simulated annealing approach on massively parallel systems offers efficient chromosome mapping, outperforming independent searches on some architectures.

Area of Science:

  • Genetics
  • Computational Biology
  • Computer Science

Background:

  • Ordering clones from genomic libraries into physical maps is a key computational challenge in genetics.
  • Chromosome reconstruction via clone ordering is analogous to the NP-complete Optimal Linear Arrangement problem.

Purpose of the Study:

  • To propose and evaluate parallel Simulated Annealing (SA) algorithms for chromosome reconstruction.
  • To compare the performance of SA algorithms on Single Instruction, Multiple Data (SIMD) and Multiple Instruction, Multiple Data (MIMD) architectures.

Main Methods:

  • Development and implementation of parallel SA algorithms using Markov chain distribution.
  • Application of perturbation methods and problem-specific annealing heuristics.
  • Implementation on a 2048-processor MasPar MP-2 (SIMD) and an 8-processor Intel iPSC/860 (MIMD).

Related Experiment Videos

Main Results:

  • A parallel SA algorithm with periodically interacting searches performed best on the fine-grained SIMD MasPar MP-2.
  • A parallel SA algorithm with independent searches was optimal for the coarse-grained MIMD Intel iPSC/860.
  • Distributing clonal data across processors can increase the likelihood of the SA algorithm converging to a local optimum.

Conclusions:

  • Parallel SA algorithms provide effective solutions for the computational problem of chromosome reconstruction.
  • Algorithm performance is dependent on the underlying parallel architecture's characteristics (e.g., grain size, synchronization overhead).
  • Careful consideration of data distribution is necessary to mitigate local optima in parallel SA for genomic mapping.