逍遥学能 2017-09-29 13:43
从数据库中检索DNA序列需要花费生物学家和医学研究人员几天的时间，多亏美国卡耐基梅隆大学计算机科学家们开发出的一种新的检索方法，如今这种检索只需几分钟时间就可完成。
由计算生物学副教授CarlKingsford和计算生物学系博士生BradSolomon开发的这种方法旨在检索所谓的短测序片段(shortreads)，即由高通量测序技术产生的DNA和RNA序列。它依赖一种新的被称作序列布隆树(SequenceBloomTree,SBT)的索引数据结构。
美国国家卫生院维护着一个庞大的被称作序列片段归档(SequenceReadArchive)的数据库，该数据库总共含有(3×1015)个碱基对。这种信息对很多研究人员---从对基础生物学过程提出问题的那些研究人员到研究潜在癌症治愈方法的那些研究人员---有用。
Kingsford说，“这种数据库含有未知数量的迄今为止尚未发现的新认识，而且被人们大量地使用。它的主要问题是检索比较困难。”
它需要上千个硬盘来储存这些序列。他注意到，通过短测序片段---通常每个片段长50到200个碱基对---进行搜索以便观察哪些短测序片段能够组装成可能长1万个碱基对的靶基因，是比较繁琐的，在某些情形下需要数天时间才能完成。
正如索引能够加快书本或目录检索，这种由Kingsford和Solomon开发的基于SBT的索引能够极大地加快这种生物信息学数据库检索。利用被称作布隆过滤器(Bloomfilters)的数据结构，他们实际上将每个短测序片段描述为一个固定长度的子序列集合。布隆过滤器能够高效地在小空间中储存信息，并且能够测试一种元素是不是一个集合的成员。
在一级查询水平上，SBT能够判别靶DNA序列是否包含在这个数据库中。如果包含的话，那么这种检索进行到下一个水平：SBT指示这种序列是否存在于这个数据库的前半部分还是后半部分。在每个水平上，这种查询以某种方式扩散开去直到所需检索的序列被检索到。
Kingsford和Solomon利用2652项人血液、乳腺和大脑实验---其中每项实验产生的数据经常含有十亿多个RNA序列碱基对---产生的数据库测试了它们的技术。他们发现对这种数据库的绝大多数的检索可以在平均20min内完成。作为比较，他们利用现有的被称作SRA-BLAST和STAR之类的技术估计了所需的检索时间：SRA-BLAST需要2.2天，而STAR需要921天。
他们注意到，进一步的加快检索是可能的，这是因为这种新检索方法每批次能够同时进行20万多个查询。