An efficient rule-based algorithm is presented for haplotype inference from general pedigree genotype data, with the assumption of no recombination. This algorithm generalizes previous algorithms to handle the cases w...An efficient rule-based algorithm is presented for haplotype inference from general pedigree genotype data, with the assumption of no recombination. This algorithm generalizes previous algorithms to handle the cases where some pedigree founders are not genotyped, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in exactly one nuclear family. The importance of this generalization lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. The algorithm runs in O（m^3n^3） time, where m is the number of single nucleotide polymorphism （SNP） loci under consideration and n is the number of genotyped members in the pedigree. This zero-recombination haplotyping algorithm is extended to a maximum parsimoniously haplotyping algorithm in one whole genome scan to minimize the total number of breakpoint sites, or equivalently, the number of maximal zero-recombination chromosomal regions. We show that such a whole genome scan haplotyping algorithm can be implemented in O（m^3n^3） time in a novel incremental fashion, here m denotes the total number of SNP loci along the chromosome.展开更多
This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an al...This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardnessof Maximum Resolution problem.展开更多
基金supported in part by AARI,AICML,ALIDF,iCORE,and NSERC
文摘An efficient rule-based algorithm is presented for haplotype inference from general pedigree genotype data, with the assumption of no recombination. This algorithm generalizes previous algorithms to handle the cases where some pedigree founders are not genotyped, provided that for each nuclear family at least one parent is genotyped and each non-genotyped founder appears in exactly one nuclear family. The importance of this generalization lies in that such cases frequently happen in real data, because some founders may have passed away and their genotype data can no longer be collected. The algorithm runs in O（m^3n^3） time, where m is the number of single nucleotide polymorphism （SNP） loci under consideration and n is the number of genotyped members in the pedigree. This zero-recombination haplotyping algorithm is extended to a maximum parsimoniously haplotyping algorithm in one whole genome scan to minimize the total number of breakpoint sites, or equivalently, the number of maximal zero-recombination chromosomal regions. We show that such a whole genome scan haplotyping algorithm can be implemented in O（m^3n^3） time in a novel incremental fashion, here m denotes the total number of SNP loci along the chromosome.
文摘This note settles the complexity of the single genotype resolution problemshowing it is NP-complete. This solves an open problem raised by P. Bonizzoni, G.D. Vedova, R.Dondi, and J. Li. The same proof also gives an alternative and simpler reduction of the NP-hardnessof Maximum Resolution problem.
