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

Massively parallel algorithms for chromosome reconstruction

S M Bhandarkar1, S Chirravuri, J Arnold

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

Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing
|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

Computational genetics faces challenges in ordering clones for chromosome mapping. This study introduces parallel algorithms for simulated annealing to solve the NP-complete Optimal Linear Ordering problem, improving clone ordering efficiency.

Area of Science:

  • Genomics
  • Computational Biology
  • Bioinformatics

Background:

  • Ordering clones from genomic libraries into physical maps is crucial for whole chromosome reconstruction.
  • This computational problem is analogous to the NP-complete Optimal Linear Ordering problem, posing significant algorithmic challenges.

Purpose of the Study:

  • To develop and evaluate massively parallel algorithms for efficient clone ordering in physical mapping.
  • To address the computational complexity of chromosome reconstruction using simulated annealing and Markov chain methods.

Main Methods:

  • Application of simulated annealing algorithms based on Markov chain distribution.
  • Development of perturbation methods and problem-specific annealing heuristics.
  • Implementation and testing on a 2048-processor MasPar MP-2 system.

Related Experiment Videos

Main Results:

  • Demonstration of the isomorphism between chromosome reconstruction and the Optimal Linear Ordering problem.
  • Experimental validation of proposed parallel algorithms on a large-scale computing system.
  • Analysis of convergence, speedup, and scalability of the developed algorithms.

Conclusions:

  • Massively parallel simulated annealing offers a viable approach for tackling the computational demands of clone ordering in genomics.
  • The proposed algorithms show promising characteristics for efficient and scalable chromosome mapping.
  • Further analysis of algorithm performance provides insights into optimizing computational genetics workflows.