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

Algorithms for computing and integrating physical maps using unique probes

M Jain1, E W Myers

  • 1Department of Computer Science, University of Arizona, Tucson 85721, USA. jainm@cs.arizona.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1997
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

Black Hole Spectroscopy and Tests of General Relativity with GW250114.

Physical review letters·2026
Same author

GW250114: Testing Hawking's Area Law and the Kerr Nature of Black Holes.

Physical review letters·2025
Same author

Anaesthesia evaluation and perioperative strategies in liver disease patients with cardiohepatic syndrome.

Revista espanola de anestesiologia y reanimacion·2025
Same author

Changes in spino-pelvis-lower extremity alignment in patients with knee osteoarthritis: a prospective radiographic study.

Musculoskeletal surgery·2025
Same author

Rapidly Progressive Renal Failure in Type 2 Diabetic versus Non-diabetic Patients: Changing Trends, Natural History, and Outcome in an Indian Tertiary Care Center.

Saudi journal of kidney diseases and transplantation : an official publication of the Saudi Center for Organ Transplantation, Saudi Arabia·2024
Same author

ECFS standards of care on CFTR-related disorders: Towards a comprehensive program for affected individuals.

Journal of cystic fibrosis : official journal of the European Cystic Fibrosis Society·2024
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

This study converts physical mapping into a linear programming problem, allowing integration of diverse data. A relaxed algorithm efficiently solves large mapping problems with high accuracy.

Area of Science:

  • Genomics
  • Bioinformatics
  • Computational Biology

Background:

  • Physical mapping projects utilize Sequence Tagged Site (STS) probes with varying data sources.
  • Integrating disparate data types into a single algorithm is challenging and algorithms quickly become obsolete.
  • New experimental data types necessitate adaptable mapping solutions.

Purpose of the Study:

  • To develop a flexible and scalable algorithm for physical mapping.
  • To incorporate diverse data clues, including probe location and clone ends, into a unified framework.
  • To address the limitations of existing tailored algorithms in handling varied and evolving data.

Main Methods:

  • Formulating the physical mapping problem as a 0/1 linear programming (LP) problem.

Related Experiment Videos

  • Incorporating additional data clues as constraints within the LP formulation.
  • Developing a relaxed LP algorithm for efficient problem-solving and a heuristic for ordering contigs.

    • Main Results:

    • The LP approach successfully integrates varied data for physical mapping.
    • A relaxed LP algorithm achieves comparable or better optimization levels than tailored algorithms for problems up to 100 probes.
    • A heuristic algorithm links contigs with high confidence (>=90% likelihood), prioritizing accuracy over potentially misleading optimal solutions with noisy data.

    Conclusions:

    • Linear programming offers a robust framework for physical mapping, accommodating diverse and evolving data.
    • The relaxed LP algorithm provides an efficient and accurate solution for medium-scale mapping problems.
    • Prioritizing high-confidence joins in contig assembly is crucial for reliable physical maps, especially with noisy data.