大数据搜索更快

了十多年,基因测序仪比计算机更快提高需要理解他们的输出。寻找DNA序列在现有的基因组数据库已经可以花费几个小时的时间,这个问题可能会变得更糟。

最近,邦妮·伯杰的小组在麻省理工学院计算机科学和人工智能实验室(CSAIL)一直在调查技术使生物和化学数据更容易分析,在某种意义上,压缩它。

在最新一期的《细胞》杂志上系统,伯格和他的同事们提出一个理论分析,说明了为什么他们之前的压缩方案已经如此成功。他们确定数据集的属性,使其适合压缩和现在的一个算法来决定是否一个给定的数据集具有这些属性。他们还表明,一些现有的数据库化合物和生物分子的确表现出他们。

给出测量的属性,研究人员也可以计算提高搜索效率,压缩技术能力。他们分析的数据集,这些次线性效率规模,这意味着更大的数据集,更高效的搜索。

“这篇论文提供了一个框架,我们如何压缩算法应用于大规模生物数据,”伯杰说,麻省理工学院应用数学教授。“我们也证明了我们可以得到多少效率。”

研究者的压缩方案的关键是,进化是小气的良好的设计。往往有很多冗余的基因组——甚至远亲——生物密切相关。

这意味着所有可能的序列的DNA的四个字母,,T, C和G -只有一个很小的子集是由真正的生物体的基因组。此外,空间内的基因组,这些真正的生物并不是随机分布的。相反,他们跟踪连续模式,代表物种分化的速度相对较慢。

鸟类的羽毛
提高搜索效率,伯杰集团的压缩算法聚集在一起类似的基因组序列——那些只有少数偏离了DNA字母,然后选择一个序列作为集群的代表。一个搜索只能集中在最有可能的集群;大部分的数据从来没有检查。

如果预想为基因组数据跟踪连续路径通过一个更大的空间的可能性,那么集群可以设想为球体叠加在数据。数据点,在一个领域是密切相关的。

伯杰和她的同事——第一作者诺亚丹尼尔斯,她的小组的博士后,和威廉,在应用数学研究生,和大卫·丹科,本科主修计算生物学——显示数据集是适合他们的压缩搜索技术是否满足两个条件。首先他们称之为度量熵。这意味着数据居住在只有一小部分的更大空间的可能性。

第二个是低的分形维数。这意味着数据点的密度不差别很大,用户通过数据。如果他们的搜索要求他们探索三个球体,而不是一个,只需要三倍的时间——不是十倍,100倍。

在他们的论文中,麻省理工学院的研究人员分析三个数据集。两个描述蛋白质——一个根据他们的氨基酸序列,根据他们的形状和其他第三描述有机分子。在一个单独的纸,正在提交,研究者应用相同的类型的DNA片段分析32和63个字母的长度之间的关系。

时间的箭头
鳞次线性搜索算法的效率,而不是数据点的数量,但随着数据集的熵度量,这是一个正式的衡量数据的连续性及其稀少,相对于空间的可能性。因为进化是保守,基因组数据的熵度量应该增加新的基因组测序。即不会增加新的基因组,十有八九,添加新的分支模式追踪在空间的可能性;相反,它将填补空白的现有模式,增加熵度量。

然而,许多其他大型数据集可能是保守的以同样的方式。网络用户行为的范围,例如,可以相对于整个空间的可能性,是受到生物、文化历史,或两者兼而有之。麻省理工学院研究人员的压缩技术可以适用于广泛的生物学数据外。