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

最近的遗传学证据表明，人类物种是一个比之前认为的更小的家族：任意群体的人包括许多隐藏的亲戚，他们不知道的是几代人之前的一个最近的祖先。研究人员开发了新的计算方法，从包含数十亿基因信息片段的大规模数据集中揭示这些遥远的家庭联系。这项研究工作将利用这些信息来汇编数以千计原本没有血缘关系的个体的家谱。拥有共同祖先的个体有机会分享一个或多个长DNA片段，这些片段在几个百万碱基上是相同的。因此，来自商业阵列的300,000-1,000,000个单核苷酸多态(SNPs)的高通量遗传数据可以确定地检测到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.