搜索技术帮助研究人员在几分钟而不是几天内找到DNA序列

由于卡内基梅隆大学计算机科学家开发了一种新的搜索方法，现在可以在几分钟内完成数据库搜索DNA序列，这些DNA序列可以让生物学家和医学研究人员服用。由计算生物学副教授Carl Kingsford和博士研究生Brad Solomon开发的方法。计算生物学系的学生，旨在搜索所谓的“短读取” - 通过高通量测序技术生成的DNA和RNA序列。它依赖于一种新的索引数据结构，称为序列绽放树或SBT，研究人员在今天由Nature Biotechnology杂志在线发表的报告中描述了这种结构。

美国国立卫生研究院维护着一个名为Sequence Read Archive的庞大数据库，该数据库包含大约三个petabases，或总共三千万亿碱基对的序列。这些信息对于广泛的研究人员非常有用，从提出有关基本生物过程的问题到研究潜在癌症治疗的研究人员。

金斯福德说：“该数据库包含了无数尚未被发现的数据，并且被大量使用。” “它的主要问题是搜索非常困难。”

存储这些序列需要数千个硬盘驱动器。他指出，通过短读数(每个通常为50到200个碱基对)进行搜索，看看哪些可以组装形成大约10,000个碱基对的靶基因，这很麻烦，在某些情况下可能需要数天。

正如索引可以加快书籍或目录的搜索速度一样，Kingsford和Solomon开发的基于SBT的索引可以极大地加速对该生物信息学数据库的搜索。它们实际上将每个短读取表示为一组固定长度的子序列，采用称为布隆过滤器的数据结构，可以有效地将信息存储在一个小空间中，并可以测试一个元素是否是一个集合的一部分。

在第一级调查中，SBT可以判断数据库中是否包含目标DNA序列。如果是，则搜索进行到下一级别，其中SBT指示序列是在数据库的一半还是另一半中。在每个级别，查询以这样或那样的方式分支，直到识别出期望的实验。

Kingsford和Solomon使用2,652人血液，乳房和大脑实验数据库测试了他们的技术，每个实验通常包含超过10亿个碱基对的RNA序列。他们发现该数据库的大多数搜索都可以在平均20分钟内完成。他们估计使用现有技术(称为SRA-BLAST和STAR)的可比搜索时间分别需要2.2天和921天。

他们指出，可以进一步加速，因为可以同时执行超过200,000次查询。