BRICS Report Series · 2003 · 11 citations · 17 references
Life SciencesGeneticsMathematicsComputational BiologyHuman GeneticsStatistical GeneticsMendelian InheritancePedigree AnalysisConsistency CheckingPedigree Consistency CheckingPedigree InformationPedigree TheoryPolynomial Time ComplexityPolynomial-time AlgorithmsSingle-gene Inheritance
Consistency checking is a fundamental computational problem in genetics. Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim of consistency checking is to determine whether these data are consistent with the classic Mendelian laws of inheritance. This problem arose originally from the geneticists' need to filter their input data from erroneous information, and is well motivated from both a biological and a sociological viewpoint. This paper shows that consistency checking is NP-complete, even with focus on a single gene and in the presence of three alleles. Several other results on the computational complexity of problems from genetics that are related to consistency checking are also offered. In particular, it is shown that checking the consistency of pedigrees over two alleles, and of pedigrees without loops, can be done in polynomial time.
17
Graph-Based Algorithms for Boolean Function Manipulation
Bryant · IEEE Transactions on Computers · 1986 · 8.9K citations · Full text
Merlin—rapid analysis of dense genetic maps using sparse gene flow trees
Gonçalo R. Abecasis, Stacey S. Cherny, William Cookson et al. · Nature Genetics · 2001 · 3.4K citations
Parametric and nonparametric linkage analysis: a unified multipoint approach.
Leonid Kruglyak, Mark J. Daly, Mary Pat Reeve-Daly et al. · PubMed · 1996 · 2.9K citations · Full text
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations