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

最近的遗传证据表明，人类是一个比以前认为的更小的家族：任意的人群包括许多对隐藏的亲戚，他们不知道这些亲戚在几代人之前都有共同的祖先。研究人员开发了新的计算方法，从包含数十亿个遗传信息片段的大规模数据集中揭示这些遥远的家庭关系。这项研究工作将利用这些信息来编制数千个不相关个体的家谱。具有共同祖先的个体有机会共享一个或多个长DNA片段，这些片段在几个兆碱基上是同源的（IBD）。因此，来自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.