The complexity of assigning genotypes to people in a pedigree consistently

摘要

We discuss the complexity of a combinatorial problem in the field of genetics, which we call Genotype ASsignability problem and abbreviate as GAS. A pair of genes at a position on a pair of chromosomes is called a genotype. GAS is defined as follows: “A pedigree is given and, for one of positions where genotypes are located in a set of pairs of chromosomes of a person, the genotypes at the position of some people in the pedigree are given. Is it possible to assign all other people (i.e., all of the people of which the genotypes are not given) genotypes for the position so as not to cause inconsistency in the heredity of genotypes at the position in the whole of the pedigree?” GAS can be used to compute, from the genotypes at the same position of some people in a pedigree, the genotypes that each person in the pedigree can possess at the position. Although many combinatorial problems have been studied so far, GAS seems not to have been done yet. Let m be the number of different genes in a pedigree and n that of people in the pedigree. We prove that GAS is NP-complete when m3 and that it can be solved in linear time O(n) when m=2.