EAGER: Haplotype Phasing Algorithms and Clark Consistency Graphs

目前，大多数SNP测定数据可从全基因组关联研究（GWAS）获得，其通过鉴定携带疾病或性状的许多个体并将其与不携带或未知携带疾病/性状的个体进行比较来进行。然后对两组个体进行大量单核苷酸多态性（SNP）遗传变异的基因分型，然后测试其与疾病/性状的关联。使用数万人的GWAS研究正变得越来越普遍，并且越来越成为遗传变异与疾病相关的规范。这些研究通常通过汇集来自多项研究的大量全基因组数据来进行，在一项荟萃分析研究中总共有数万人。可以预期，如果不是数百万，也有数十万人将很快被研究与单一疾病或特征的关联。尽管SNP是两个个体之间最丰富的变异形式，但还存在其他形式的变异，例如拷贝数变异？大规模的染色体缺失、插入和复制。这些变异已被证明是许多疾病中的影响因素，但使用目前的SNP阵列技术无法探测。会计的新趋势是什么？缺少遗传性？是吗？原始父母遗传变异仅在从特定父母遗传时才会带来风险。长距离单倍型定相是确定单倍型模式与特定亲本起源的关联的关键。本研究的前提是，除非单倍型在血统上相同（IBD），否则长的遗传束不太可能（共享），而短的共享遗传束则可能在状态上相同（IBS）。一个困难的算法挑战是在m个人的样本的基因型矩阵中在n个SNP处进行基因分型的道发现。 我们研究的前提是，除非单倍型在血统上是相同的（IBD），否则长片段不太可能（被共享），而短片段的共享可能在状态上是相同的（IBS）。一个困难的算法挑战是在m个人的样本的基因型矩阵中在n个SNP处进行基因分型的道发现。为了将这种长程定相算法应用于美国人群，估计必须对200万个体进行基因分型。这里提出的策略表明，克拉克一致性图的组合结构可以提供强大的算法，将大大减少这个数字的基础上的承诺。 该项目的主要产出将是新的远程定相软件、文档和源代码，所有这些都将作为开源软件立即并持续地提供给科学界，用于研究和教育。

Currently, most SNP assay data is made available from genome-wide association studies (GWAS), which proceed by identifying a number of individuals carrying a disease or a trait and comparing them to those that do not or are not known to carry the disease/trait. Both sets of individuals are then genotyped for a large number of single-nucleotide polymorphism (SNP) genetic variants that are then tested for association to the disease/trait. GWAS studies using tens of thousands of individuals are becoming commonplace and are increasingly the norm in the association of genetic variants to disease. These studies generally proceed by pooling large amounts of genome-wide data from multiple studies, for a combined total of tens of thousands of individuals in a single meta-analysis study. It can be expected that hundreds of thousands, if not millions, of individuals will soon be studied for association to a single disease or trait. Although SNPs are the most abundant form of variation between two individuals, other forms of variation exist, such as copy-number variation ? large-scale chromosomal deletions, insertions, and duplications. These variations, which have been shown to be influential factors in many diseases, are not probed using the current technology of SNP arrays. An emerging trend in accounting for ?missing heritability? is ?parent-of-origin? effects, where genetic variants confer risk only when inherited from a specific parent. Long-range haplotype phasing is key to identifying the association of the haplotype pattern to the specific parent of origin.The premise of this research is that long tracts are unlikely (to be shared) unless the haplotypes are identical by descent (IBD), in contrast to short shared tracts, which may be identical by state (IBS). A difficult algorithmic challenge is that of tract finding in genotype matrices of a sample of m people genotyped at n SNPs. The premise of our research is that long tracts are unlikely (to be shared) unless the haplotypes are identical by descent (IBD), in contrast to short shared tracts, which may be identical by state (IBS). A difficult algorithmic challenge is that of tract finding in genotype matrices of a sample of m people genotyped at n SNPs. To apply such a long-range phasing algorithm to the U.S. population, it is estimated that 2 million individuals must be genotyped. Algorithmic strategies proposed here show promise that the combinatorial structure of Clark Consistency Graphs can provide the basis for powerful algorithms that will decrease this number substantially. The primary output of this project will be new long-range phasing software, documentation, and source code, all to be immediately and continually available to the scientific community as open-source for research and education.