کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650835 1342504 2007 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity of assigning genotypes to people in a pedigree consistently
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
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 m⩾3m⩾3 and that it can be solved in linear time O(n)O(n) when m=2m=2.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 307, Issue 16, 28 July 2007, Pages 2122–2131
نویسندگان
, ,