The Complexity of Checking Consistency of Pedigree Information and Related Problems  

作　　者：LucaAceto JensA.Hansen AnnaIngdlfsddttir JacobJohnsen JohnKnudsen 

机构地区：[1]BasicResearchinComputerScience,CentreoftheDanishNationalResearchFoundation,DepartmentofComputerScience,AalborgUniversity,Fr.Bajersvej7E,9220AalborgΦ,Denmark [2]deCODEGenetics,Sturlugata8,101Reykjavik,Iceland

出　　处：《Journal of Computer Science & Technology》2004年第1期42-59,共18页计算机科学技术学报（英文版）

摘　　要：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 ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.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 ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.

关 键 词：consistency checking PEDIGREES GENOTYPES NP-COMPLETENESS SATISFIABILITY polynomial time complexity critical genotypes 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]