HAPLOTYPE INFERENCE USING PEDIGREE DATA

这个子项目是许多研究子项目中的一个 由NIH/NCRR资助的中心赠款提供的资源。子项目和 研究者（PI）可能从另一个NIH来源获得了主要资金， 因此可以在其他CRISP条目中表示。所列机构为 研究中心，而研究中心不一定是研究者所在的机构。 我们研究了零重组假设下的单倍型推断问题，这是很好的支持真实的数据紧密连锁的标记（即单核苷酸多态性（SNP））在一个相对较大的染色体片段。我们解决了这个问题，在一个严格的数学方式制定基因型约束作为一个线性系统的遗传变量。然后，我们利用不相交集结构来编码个体之间的连接信息，检测基因型的约束，并检查约束的一致性。在没有缺失数据的树谱系上，我们的算法可以在近似线性的时间O（mn）内输出通解以及全部特定解的数量。α（n）），其中m是基因座的数量，n是个体的数量，α是逆阿克曼函数，这是对现有函数的进一步改进。我们还扩展了这个想法，考虑现有的（部分）继承变量的约束，以循环谱系和谱系缺失的数据。

This subproject is one of many research subprojects utilizing the resources provided by a Center grant funded by NIH/NCRR. The subproject and investigator (PI) may have received primary funding from another NIH source, and thus could be represented in other CRISP entries. The institution listed is for the Center, which is not necessarily the institution for the investigator. We study the haplotype inference problem from pedigree data under the zero recombination assumption, which is well supported by real data for tightly linked markers (i.e. single nucleotide polymorphisms (SNPs)) over a relatively large chromosome segment. We solve the problem in a rigorous mathematical manner by formulating genotype constraints as a linear system of inheritance variables. We then utilize disjoint-set structures to encode connectivity information among individuals, to detect constraints from genotypes, and to check consistency of constraints. On a tree pedigree without missing data, our algorithm can output a general solution as well as the number of total specific solutions in a nearly linear time O(mn . alpha(n)), where m is the number of loci, n is the number of individuals and alpha is the inverse Ackermann function, which is a further improvement over existing ones. We also extend the idea to looped pedigrees and pedigrees with missing data by considering existing (partial) constraints on inheritance variables.