EMT: Computational methods for mapping genealogy of unrelated individuals from high throughput genetic data

最近的遗传学证据表明，人类物种是一个比以前认为的更小的家族：任意的人群包括许多对隐藏的亲属，他们不知道几代人前的最近祖先。研究人员开发了新的计算方法，从包含数十亿遗传信息片段的大规模数据集中揭示这些远程家庭关系。这项研究工作将利用这些信息编制一份数千个原本不相关的个体的家谱。具有共同祖先的个体有机会分享一个或多个长DNA片段，这些片段在几兆年内是相同的。因此，来自300，000 - 1，000，000个单核苷酸多态性（SNP）的商业阵列的高通量遗传数据可以确定地检测IBD。对于这些阵列的数万个个体的大规模数据的计算挑战是在搜索IBD时进行所有二次成对比较。研究人员开发了一种每位点散列算法，该算法在所有O（n2）样本对中检测相同的单倍型，但在线性时间内运行。他们正在使用这种方法来绘制公开样本中隐藏的相关性，为在无关人群中进行基于群体的连锁分析以及对最近几代人的群体遗传学进行推断创造了一个有用的工具。

Recent genetic evidence shows that the human species is a smaller family than previously thought: arbitrary groups of people include many pairs of hidden relatives, that unknown to them share a recent ancestor a few generations back. The investigators develop novel computational methods to reveal these remote family ties, from large scale datasets that contains billions of snippets of genetic information. This research effort will use this information to compile a genealogy of thousands of otherwise-unrelated individuals.Individuals with a common ancestor have a chance to share one or more long fragments of DNA, that are identical-by-descent (IBD) over several megabases. High throughput genetic data from commercial arrays of 300,000-1,000,000 Single Nucleotide Polymorphisms (SNPs) can therefore detect IBD with certainty. The computational challenge in large scale data of tens of thousands of individuals typed for these array is making all the quadratic number of pairwise comparisons in search for IBD. The investigators develop a per-locus hashing algorithm, that detects identical haplotypes across all O(n2) sample pairs, but operates in linear time. They are using this methodology to map hidden relatedness across publicly available samples, creating a useful tool for population-based linkage analysis in unrelateds, as well as inferences on population genetics of recent generations.