EAGER: Haplotype Phasing Algorithms and Clark Consistency Graphs

EAGER：单倍型定相算法和克拉克一致性图

• 批准号: 1048831
• 负责人: Sorin Istrail
• 金额: $ 20万
• 依托单位: Brown University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-01-01 至 2012-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1048831&HistoricalAwards=false
• 关键词: EAGER; Haplotype; Phasing; Algorithms; Clark

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.

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