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

The incomplete perfect phylogeny haplotype problem.

Gad Kimmel1, Ron Shamir

  • 1School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. kgad@tau.ac.il

Journal of Bioinformatics and Computational Biology
|April 27, 2005
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

The Effect of Nephrology Referral on CKD Outcomes in Israel.

Clinical journal of the American Society of Nephrology : CJASN·2026
Same author

Demography-dependent variability in the human tumor mycobiome.

Microbiology spectrum·2026
Same author

Optimizing Parkinson's disease progression scales using computational methods.

NPJ Parkinson's disease·2026
Same author

HLA export by melanoma cells decoys cytotoxic T cells to promote immune evasion.

Cell·2025
Same author

ProFiT-SPEci-FISH: a novel approach for linking plasmids to hosts in complex microbial communities at the single-cell level.

Microbiome·2025
Same author

Molecular Systems Biology at 20: reflecting on the past, envisioning the future.

Molecular systems biology·2025
Same journal

CNV-ECOD: A copy number variation detection method based on ECOD algorithm using next-generation sequencing data.

Journal of bioinformatics and computational biology·2026
Same journal

ReinVar: A model-free paradigm-based reinforcement learning approach to detect copy number variation.

Journal of bioinformatics and computational biology·2026
Same journal

When pipelines run but coordinates fail: A simple spatial specificity check for false locality in post-GWAS analysis.

Journal of bioinformatics and computational biology·2026
Same journal

Comparative benchmarking of template-based, evolutionary-diffusion, and generative language models for IsPETase structure prediction.

Journal of bioinformatics and computational biology·2026
Same journal

Trap spaces as labelled ideals of SCC posets: A structural-functional theory of reachability in asynchronous boolean networks.

Journal of bioinformatics and computational biology·2026
Same journal

Erratum - DDINet: Drug-drug interaction prediction network based on multi-molecular fingerprint features and multi-head attention centered weighted autoencoder.

Journal of bioinformatics and computational biology·2026
See all related articles

Resolving genotypes into haplotypes with missing data is NP-complete. A new probabilistic model and algorithm efficiently solve this problem, even with significant missing genotype information.

Area of Science:

  • Computational Biology
  • Genetics
  • Bioinformatics

Background:

  • Haplotype resolution from genotype data is crucial in genetic studies.
  • Existing methods for handling missing genotype data are heuristic and suboptimal.
  • The perfect phylogeny model is a common framework for haplotype inference.

Purpose of the Study:

  • To investigate the computational complexity of haplotype resolution with missing data under the perfect phylogeny model.
  • To develop a novel probabilistic model for genotype generation and missing data occurrence.
  • To create an efficient algorithm for haplotype resolution incorporating missing data.

Main Methods:

  • Proving the NP-completeness of the perfect phylogeny haplotype problem with missing data.
  • Defining a biologically motivated probabilistic model for genotype and missing data.

Related Experiment Videos

  • Developing an expected polynomial-time algorithm based on the probabilistic model.

    • Main Results:

    • The perfect phylogeny haplotype problem is NP-complete when data entries are missing, even for rooted phylogenies.
    • A novel probabilistic model for genotype generation and missing data was established.
    • The developed algorithm demonstrates efficient performance in resolving genotypes with high rates of missing data in simulations.

    Conclusions:

    • Haplotype resolution with missing data is computationally challenging.
    • The proposed probabilistic model and algorithm offer an effective solution for handling missing genotype data.
    • This work advances computational methods for genetic data analysis, particularly in the presence of incomplete information.