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

Approximation properties of haplotype tagging.

Staal A Vinterbo1, Stephan Dreiseitl, Lucila Ohno-Machado

  • 1Decision Systems Group, Brigham and Women's Hospital, Boston, MA 02115, USA. staal@dsg.harvard.edu

BMC Bioinformatics
|January 13, 2006
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

Development of the authentication and authorization processes for the iAgree portal, a platform for patient-controlled data sharing across health systems.

JAMIA open·2026
Same author

Foundation Model-Guided Synthetic EHR Release: Performance Enhancement with Privacy Preservation.

AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science·2026
Same author

Large Models for Small Tables: Adapting Tabular Foundation Models to EHR Data.

AMIA Joint Summits on Translational Science proceedings. AMIA Joint Summits on Translational Science·2026
Same author

Memorization in large language models in medicine prevalence characteristics and implications.

Nature communications·2026
Same author

Privacy-enhancing sequential learning under heterogeneous selection bias in multi-site electronic health records data.

Journal of the American Medical Informatics Association : JAMIA·2026
Same author

Exploring patient motivations and preferences for medical data sharing with researchers: a simulation study using the iAgree platform.

Journal of the American Medical Informatics Association : JAMIA·2026
Same journal

Covariance decomposition for distance based species tree estimation.

BMC bioinformatics·2026
Same journal

SNPio: a Python interface for population genomic data processing.

BMC bioinformatics·2026
Same journal

SpaHNR: a spatial domain identification method via sparse attention-based hierarchical node representation and multi-view contrastive learning.

BMC bioinformatics·2026
Same journal

OpenIMC: an open-source platform for analyzing single-cell and spatial proteomics by imaging mass cytometry.

BMC bioinformatics·2026
Same journal

NAP: an open source pipeline for cross-domain microbiome profiling using Nanopore sequencing-derived amplicon data.

BMC bioinformatics·2026
Same journal

SurvGME: an R package for survival analysis with graphical and measurement error models.

BMC bioinformatics·2026
See all related articles

Identifying specific genetic variations called single nucleotide polymorphisms (SNPs) is crucial for disease association studies. A new algorithm efficiently solves the complex haplotype tagging problem, offering optimal solutions for pattern identification in genomic sequences.

Area of Science:

  • Genetics
  • Bioinformatics
  • Computational Biology

Background:

  • Single nucleotide polymorphisms (SNPs) represent variations in genomic sequences within populations.
  • Identifying patterns in SNPs, known as haplotype tagging, is essential for disease association studies.
  • Haplotype tagging is a complex combinatorial optimization problem.

Purpose of the Study:

  • To analyze the complexity and approximation properties of the haplotype tagging problem.
  • To develop an efficient algorithm for haplotype tagging.

Main Methods:

  • Formulation of haplotype tagging as a combinatorial optimization problem.
  • Analysis of the problem's NP-hard nature and approximation bounds.
  • Development and analysis of a simple, implementable algorithm.

Related Experiment Videos

Main Results:

  • The haplotype tagging problem is NP-hard but approximable.
  • An algorithm is presented with an upper bound on solution quality.
  • The algorithm's running time is analyzed in relation to haplotype number and size.
  • The approximation bound is shown to be asymptotically tight, making the algorithm optimal.

Conclusions:

  • The haplotype tagging problem, while computationally hard, is solvable with a practical algorithm.
  • The presented algorithm is simple, fast, and offers near-optimal solutions.
  • Significant improvements in computational efficiency require parallel processing.