Document Detail


A practical algorithm for optimal inference of haplotypes from diploid populations.
MedLine Citation:
PMID:  10977079     Owner:  NLM     Status:  MEDLINE    
Abstract/OtherAbstract:
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 tested, data that is expected to be more demanding than realistic biological data.
Authors:
D Gusfield
Related Documents :
18627599 - Malhaplofreq: a computer programme for estimating malaria haplotype frequencies from bl...
15699029 - Inference of missing snps and information quantity measurements for haplotype blocks.
18451979 - How to perform meaningful estimates of genetic effects.
16709279 - The use of configural frequency analysis for explorative data analysis.
16128609 - Automatic scoring and quality assessment using accuracy bounds for fp-tdi snp genotypin...
23919319 - Happy birthday: we are one year old.
20699699 - Determining the relative toxicity and rbe of internal emitters in animals.
11515939 - Optimal filtering and bayesian detection for friction-based diagnostics in machines.
22809379 - Recursive protein modeling: a divide and conquer strategy for protein structure predict...
Publication Detail:
Type:  Journal Article; Research Support, U.S. Gov't, Non-P.H.S.    
Journal Detail:
Title:  Proceedings / ... International Conference on Intelligent Systems for Molecular Biology ; ISMB. International Conference on Intelligent Systems for Molecular Biology     Volume:  8     ISSN:  1553-0833     ISO Abbreviation:  Proc Int Conf Intell Syst Mol Biol     Publication Date:  2000  
Date Detail:
Created Date:  2001-01-23     Completed Date:  2001-01-26     Revised Date:  2006-11-15    
Medline Journal Info:
Nlm Unique ID:  9509125     Medline TA:  Proc Int Conf Intell Syst Mol Biol     Country:  UNITED STATES    
Other Details:
Languages:  eng     Pagination:  183-9     Citation Subset:  IM    
Affiliation:
Department of Computer Science, University of California, Davis 95616, USA. gusfield@cs.ucdavis.edu
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Descriptor/Qualifier:
Algorithms*
DNA / analysis*
Genome, Human*
Haplotypes*
Human Genome Project*
Humans
Polymorphism, Genetic
Chemical
Reg. No./Substance:
9007-49-2/DNA

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine


Previous Document:  Intelligent aids for parallel experiment planning and macromolecular crystallization.
Next Document:  Finding regulatory elements using joint likelihoods for sequence and expression profile data.