PMID: 10977079Sep 8, 2000Paper

A practical algorithm for optimal inference of haplotypes from diploid populations

D Gusfield


The next phase of human genomics will involve large-scale screens of populations for significant DNA polymorphisms, notably single nucleotide polymorphisms (SNP's). Dense human SNP maps are currently under construction. However, the utility of those maps and screens will be limited by the fact that humans are diploid, and that it is presently difficult to get separate data on the two "copies". Hence genotype (blended) SNP data will be collected, and the desired haplotype (partitioned) data must then be (partially) inferred. A particular non-deterministic inference algorithm was proposed and studied before SNP data was available, and extensively applied more recently to study the first available SNP data. In this paper, we consider the question of whether we can obtain an efficient, deterministic variant of that method to optimize the obtained inferences. Although we have shown elsewhere that the optimization problem is NP-hard, we present here a practical approach based on (integer) linear programming. The method either returns the optimal answer, and a declaration that it is the optimal, or declares that it has failed to find the optimal. The approach works quickly and correctly, finding the optimal on all simulated data teste...Continue Reading

Related Concepts

DNA, Double-Stranded
Genetic Polymorphism
Genome, Human
Human Genome Diversity Project

Trending Feeds


Coronaviruses encompass a large family of viruses that cause the common cold as well as more serious diseases, such as the ongoing outbreak of coronavirus disease 2019 (COVID-19; formally known as 2019-nCoV). Coronaviruses can spread from animals to humans; symptoms include fever, cough, shortness of breath, and breathing difficulties; in more severe cases, infection can lead to death. This feed covers recent research on COVID-19.

Evolution of Pluripotency

Pluripotency refers to the ability of a cell to develop into three primary germ cell layers of the embryo. This feed focuses on the mechanisms that underlie the evolution of pluripotency. Here is the latest research.

Lipidomics & Rhinovirus Infection

Lipidomics can be used to examine the lipid species involved with pathogenic conditions, such as viral associated inflammation. Discovered the latest research on Lipidomics & Rhinovirus Infection.

Glut1 Deficiency

Glut1 deficiency, an autosomal dominant, genetic metabolic disorder associated with a deficiency of GLUT1, the protein that transports glucose across the blood brain barrier, is characterized by mental and motor developmental delays and infantile seizures. Follow the latest research on Glut1 deficiency with this feed.

Chronic Fatigue Syndrome

Chronic fatigue syndrome is a disease characterized by unexplained disabling fatigue; the pathology of which is incompletely understood. Discover the latest research on chronic fatigue syndrome here.

Alzheimer's Disease: MS4A

Variants within the membrane-spanning 4-domains subfamily A (MS4A) gene cluster have recently been implicated in Alzheimer's disease in genome-wide association studies. Here is the latest research on Alzheimer's disease and MS4A.

STING Receptor Agonists

Stimulator of IFN genes (STING) are a group of transmembrane proteins that are involved in the induction of type I interferon that is important in the innate immune response. The stimulation of STING has been an active area of research in the treatment of cancer and infectious diseases. Here is the latest research on STING receptor agonists.

Laryngeal Neoplasms

Laryngeal Neoplasms occur in the Larynx and are typically associated with smoking and alcohol consumption. Discover the latest research on Laryngeal Neoplasms here.

Cell Atlas Along the Gut-Brain Axis

Profiling cells along the gut-brain axis at the single cell level will provide unique information for each cell type, a three-dimensional map of how cell types work together to form tissues, and insights into how changes in the map underlie health and disease of the GI system and its crosstalk with the brain. Disocver the latest research on single cell analysis of the gut-brain axis here.

Related Papers

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
D Gusfield
Journal of Biomedical Informatics
Ghasem MahdevarHayedeh Ahrabian
Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
Ana GraçaArlindo L Oliveira
Advances in Neural Information Processing Systems
Mahdi Milani Fard, Joelle Pineau
© 2021 Meta ULC. All rights reserved