Tag Archives: search engine

腾讯的DNA搜索引擎

  腾讯研究院刚刚推出了实验性的DNA搜索引擎,去年他们发表过一篇学术论文How to build a DNA search engine like Google?,还申请了与此相关的专利。当时引起了国内外很多科技媒体的关注

  关于这个DNA搜索引擎,扬子江@42qu刚刚发表的这篇文章里面有更详细的介绍。

  先简单介绍一下这篇论文的思路。现代搜索引擎的一个常规预处理环节,是对文档进行分词然后创建倒排索引。中英文在分词这个环节上有很大差别,英文单词天然被空格隔开,中文句子里的词汇都是连在一起的,所以更加难以划分,例如“南京市长江大桥”,分词算法一不小心就切成了这样:南京/市长/江/大桥。因此最常见的处理,是开一个移动窗口,不断扫描连续几个字形成的子串,创建倒排索引,当然最终只会保留频率较高的串。考虑到基因串搜索的特点与此很类似,所以现有中文搜索引擎的技术可以应用到生物基因搜索里去。

  如果对分词算法更感兴趣的话,可以参考《算法导论》里“动态规划”那一章的计算字符串最小距离的那个例题,书里还特别提示了一句:这个模型被应用于基因比对领域。进一步,还可以Google更专业经典的生物信息算法,例如BLAST(我记得IBM开发社区有过一篇BLAST算法的介绍写得很好)。

算法导论

  文本信息检索和基因分析两个领域之间有很多故事。

  在本领域的超大规模序列匹配算法和软件尚未成熟之前,早期的生物信息学者就曾经试图借助过Google协助自己的研究。他们的办法是把基因数据放到Web上,然后吸引Google的爬虫过来抓取,最后再用Google搜索自己想要的序列片段。不过由于人类基因字符串长达三十万,Google对匹配模式的长度有上限,所以这种方法的结果并不是特别精确。按说号称更懂中文的百度应该能派上用场……悲剧的是……百度限制更多……嗯……我记得……那时候搜索内容不能超过32个汉字(或64个字母)。

  当BLAST等经典基因比对算法出现以后,又反过来被信息检索领域应用,在某些特殊的场合(例如版本比对、谣言分析、抄袭判断等领域)发挥了重大作用,很多人大概都听说过分析“赶快把这封邮件抄送给十个朋友,否则……”这类蠕虫email内容几十年演变过程的那篇著名论文。

  稍微了解领域知识的生物信息人员都会明白,腾讯的这个引擎还只是一个演示性的玩具。真正常规的工业级基因深度测序数据处理,是要对多达几T的测序数据进行拼接和匹配,然后再搜索基因库,寻找突变点。不过俺个人看法是,如果有一天网络巨头真把目光投向生物信息领域了,这个行业就该重新洗牌了。目前看,还是产业规模和利润兴趣的问题,而具体的技术能力并不会形成太大的壁垒,就算有,在高薪挖墙角的人才战面前也是浮云。

  说到这里,LinkedIn上面的Bio-IT World: Bioinformatics小组里刚有过一个有趣的讨论:So why hasn’t the Bioinformatics industry rocketed to success? (为什么生物信息产业始终不温不火,没有出现爆炸性发展?)