Tag Archives: 搜索引擎

腾讯的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? (为什么生物信息产业始终不温不火,没有出现爆炸性发展?)

pFind引擎的第四代索引模块

  因为CNCP2010,同时也有些私事,最近很忙。live spaces又拆迁。所以BLOG节奏受影响。这周末陆续敲点流水帐。

  首先要祝贺zhch的后缀数组论文经过一年历练总算被BMC Bioinformatics接收。相关专利也提交了。(在这之前,sun老师的ETD论文也发表了,BOSS H昨天说,今年一年组里发了6、7篇,快等于此前几年的总和了)。

  pFind搜索引擎的索引技术一直不断传承和推进:dq老大最先奠定基础,推出IndexToolkit开源项目并在Bioinformatics发表Application notes;之后ly哥凭借不懈努力吃透了倒排技术,重构了索引模块,发表论文申请专利;接下来zhch凭借ACM金牌的强悍算法功底继续前进,先是将倒排索引的数据容量上限提高了几个数量级,然后又另辟蹊径引入后缀数组技术,颠覆了前人的工作。

  年底推出pFind 2.6之后,我们将着手把zhc的模块从develop分支移到release分支。这是pFind的第四代索引了。当然这只是刚开头,它必须通过全面严厉的测试,才能证明自己有资格替代老版本索引,在工业级产品中担当主力。

流水帐.2010.10.4

  还没有确定是不是WordPress.com。办妥了会通告。先补前一段时间落下的内容。好久没写BLOG,不好意思。

  9月份工作很紧张,终于把软件著作权、专利和商标的申请都搞定了。pFind并行版内容最终拆分为三个互相掩护的子专利,因为涉及到MapReduce技术,还特意和专利代理律师一起研究了有关资料,除了论文,还包括今年1月份刚刚公开的7650331号专利。这期间还注意到一条新闻:Google最新版引擎Caffeine已经放弃MapReduce架构。接下来补更多实验,要啃一个超过五百万张谱图的庞大数据集。偏偏碰到深腾7000停机修整,踅摸中……

  最近不仅没精力写BLOG,也没空买书。前两天才抽出空来去了一趟中关村图书大厦,买到了爱德华·吉本的《罗马帝国衰亡史》、沈群的《美国也荒唐》、W.Bruce等的《搜索引擎》(也就是Search Engines: Information Retrieval in Practice的中文版)、周汝昌的《红楼小讲》、林语堂的《平心论高鹗》

pFind集群的论文正式发表

  俺和瓶子的pFind集群论文:An efficient parallelization of phosphorylated peptide and protein identification已在英文期刊RAPID COMMUNICATIONS IN MASS SPECTROMETRY (2.772)正式发表。

  论文主要论述了我们在并行加速方面的研究。实验表明:pFind搜索引擎对一个含有100个Raw文件的磷酸化公共数据集进行鉴定,在100个处理器核 上,加速比为83.7;对另一个更大的、共含有1,366,471张质谱的磷酸化数据进行鉴定,在320个核上,加速比为258.9,加速效率达到 80.9%。

  目前pFind并行版已经投入一线分析实用。俺们正在千核条件下继续研发。

pFind引擎内核建立Trace机制

  必须上来写点,否则对不起订阅BLOG的读者了。

  这周我们封闭开发,重构pFind引擎内核引入Trace机制。我预研了Log4cppACE_TRACE的源码,还是决定自己动手实现底层机制,更贴近pFind系统的实际要求。

  像pFind这样的复杂系统,不免有大量输出信息,有些是给用户看的,有些是程序员调试时用来追踪进度和现场情况的。传统做法,调试信息会被用宏开关控制,产品发布时被关掉,以免输出过于庞杂导致用户体验变差,但这又会增大事故现场诊断Bug的困难。要调和这对矛盾,就需要灵活的Trace机制,通过设 置参数实时控制输出,例如范围(指定的算法模块、线程或集群节点)、级别(过滤或保留debug信息)和目标(命令行输出或写入日志文件)。

  这种基础设施涉及到整个系统,大部分模块都需要重构,工作量不小。在Win32下开发调试比较顺利,移植到曙光大机的64位Suse Linux时,出现了一些动态链接问题,调整了模块划分。(为了解决这个问题,去查阅俞甲子、石凡和潘爱民的《程序员的自我修养——链接、装载与库》,的确是好书。)

程序员的自我修养

  遇到了Gcc 3.4.5的这个Bug,编译STL总会出现大量Warning。从GNU Bugzilla上的讨论来看,Gcc 3.*系列的维护已经停止了,推荐升级到4.*系列。一直想升级pFind的默认编译器,但之前尝试时,ACE在Gcc 4.4(MinGW)下无法正常编译(刚刚搜索,貌似今年1月份刚刚有人把这个Bug解决掉了)。像陈硕这篇BLOG说的,ACE很值得学习借鉴,但代码臃肿,有很多使用问题。

  在重构后期,大家已经开始利用Trace本身进行调试。“吃自己的狗食”是个好现象。

  建立Trace机制、升级Gcc消除Warning,都是为单元测试(Unit Test)和持续集成(Continuous Integration)做准备。自动化测试是我今年的重点目标。衡量一个团队有多精锐,不在于统计技术牛人的个数,而要看它是否拥有超出平均水平的制度 平台。我发现凡是不用版本管理(SVN、CVS或VSS均可)的软件开发组都很烂,甭管团队里有多少能工巧匠。前瞻研究实验室年度汇报,听到浩哥讲Godson-T的开发,他们就构建了很强大的自动化测试平台,让人不服不行。

  还在考虑为pFind引擎构建“黑盒子”机制,把一段时间内的系统实时状态都记录下来,用以重现事故现场。云风做过类似的设计。不过这样一来,如何保证运行效率就成了关键问题。

  这周很累,但有成就感。接下来折腾RCMS论文,19日deadline。大家的批改纷纷返回,多谢,汇总中。

基于云计算的蛋白质组学

  又到了写BLOG的Deadline。对我来说写作是种享受。只是之前这段碎碎念太多,BLOG总在码琐事。所以这次Todo List要求必须写技术。

  这个月的Journal of Proteome Research上刚刚发表了一篇论文,利用Amazon Web Services提供的EC2平台进行质谱数据的肽和蛋白质鉴定。这正是俺加入生物信息课题组五年来朝思暮想的目标。科学界对云计算概念接受速度之快令人惊讶,已经看到物理、生化、机器翻译领域的不少研究,都是租用云服务以完成海量计算任务。

  今年7月我们将发布pFind 2.3。速度精度都将有进一步提高,敬请期待。

  虽说要写技术,还是忍不住写点八卦。

  周五带小弟去和美女们KTV。通宵的麦克风争夺战打完,五打(60瓶)啤酒喝下去,得出鉴定结果:计算所的程序员男生实在太腼腆内向,无论是飙歌还是拼酒,都被生化丫头们比下去了,与写代码时的生猛劲头儿形成鲜明对照。

  和职业有关?错!恰恰是俺们唯一的女生不露怯,对方阵营唯一的男士三次敬酒,wyj美女都是干干脆脆吹下去一整瓶,和她开发新版搜索引擎一样气势逼人。

  没有生人,这帮家伙就活跃多了。上周末,请组里未婚人士到家里玩WII。整晚俺都在担心客厅的木地板,也奇怪楼下邻居为何不在临晨3点报警。

pFind 2.0历程

  前两天做了一次报告,总结pFind 2.0。花了很大功夫准备Google Docs幻灯,熬到凌晨3:00。

  05年下半年,接手生物信息组工作,顶住干扰静下心着手工作。这一年的最后一天,首次跑通流程

  06年1月,对算法模块展开大规模测试,这只是之后漫长的重构、测试、再重构、再测试循环的序幕。(小插曲:BLOG里提到的那个缺根弦的家伙,是在纠缠我当时的女友,之后居然等在我加班回去的路上,拿电棍袭击我,反而被我打倒在地……现在想想,俺真是什么人生体验都没错过)测试结束时给全组发邮件,希望建立直接透明的工程氛围。

  06年2月,着手M2版。虽然有心理准备,但之后事实证明,“第二赛季”还是比预想的要困难得多。

  06年4月,搜索引擎核心完成最初调试,界面也很快做出来了,那时以为Alpha阶段能很快结束。接下来几个月,陷入反复修改和测试。除了各种BUG,涉及更多的是科研问题。亲身体验了“小数点后五位数据不精确导致性能大大降低”这种传说中的科学故事。那时pFind的鉴定效果着实好不到哪儿去

  06年12月pFind 2.0论文投稿,这十几页纸,真把这辈子的英语都写完了,最终发表在RCMS时,已经修改过32稿。

  07年1月开始Beta测试,我扮演工兵。从用户那里回来,马上力排众议安排pBuild开发。在一线眼巴巴“护送”软件运行是件滴汗的事,但过后增加底气。现场值班逐渐成了日常工作。原来Mascot并非遥不可及,许下一个愿望

  07年8月,为解决系统在修饰问题上的缺陷,不得不展开大规模重构,但遇到挫折。不过现在看来,这是一笔财富,理清了思路。

  07年9月,有机会投入生物一线的实际科研,这时候的pFind 2.0还不完善,遇到很多麻烦。差点迈不过这道坎,但最终fy大侠带领我们创造了奇迹。之后几个月,继续推进。这是一段激情时光通过不断努力,再次重构后的系统性能获得成倍提高

  08年1月,滑单板时摔断了胳膊,打着石膏坚持去上海出差推广pFind。 南方雪灾,差点留在上海过年。到春节为止,组里申请了11项软件著作权。专利方面,获得第1项专利授权,还有4项等待授权,今年还有3项打算申请。商标也 在申请中,去年10月在人类蛋白质组会议以后,我们的域名遭到恶意抢注,经过戏剧性的争夺,我幸运地抢回了pfind.net这个重要URL。

  08年4月,pFind 2.0 final Relese,同时pFind 2.1展开,还有3天,29日下午6:00,就是2.1 Alpha1版的deadline。计划8月8日推出“奥运献礼版”。

  pFind 2.0历经3年终于完满,但可能没多久就会被更出色的2.1所取代。心情有些复杂。感谢所有的同事和朋友。

pFind新版开发启动

  三月份大部分时间在写材料和开会。甚至出现了一个meeting week,周一到周五全都用来赶场参加各种会,最夸张的一天开了三个会,一直弄到将近23:00才散,差点没赶上5号轻轨末班。

  上周终于着手2.1新版设计。鉴于大伙儿元气大伤,取消了setup会议,单独找每个人面对面交流再汇总Todo List。

  周三下午,把电脑和投影仪搬到会议室里,直接对着代码展开第一个模块的设计。双人编程,正确说,应该是四人编程,推敲所有细节,甚至明 确参数命名。一开始当然有点痛苦,各人都没有特别细致的思路,更别提大家的一致。不过几个回合重构下来,最终一版的空模块(只定义了接口和架构)编译通 过,每个人都很开心,团队的信心和士气提高了不少。这不仅因为完成了第一个里程碑,还因为统一明确了设计原则和质量底线,后续设计工作照方抓药就可以了。 磨刀不误砍柴工,设计阶段精耕细作从来都不会白费。

  上周的另一件事是继续调试2.0老版本。多谢chh支援,困扰两个多月的BUG总算有些眉目:第一组实验中,碰到一个变态的蛋白,修饰 位点组合爆炸,出现九千多万种可能性,把递归程序撑爆了;第二组实验中,为压力测试调大了参数,有个地方的vector容器装不下。把两个地方剪枝条件加 强就解决了。折腾这么久,真算职业生涯的奇耻大辱。搞到最后老板都不好意思问了;反而是老妈每晚的餐桌上都关心进展;去参加文献club,生物学家也问 “你的BUG怎么样了”。

  另一方面,由此看来,老版pFind的潜力也就仅限于此了,稍微上点数据量就开始这里那里到处漏水。这也正是彻底重新设计架构,开发2.1版的主要原因。

  我预计新版的C++代码可以从18万行降到10万行左右,速度提高一倍以上,而海量数据的处理上限,可以有不止一个数量级的提升。当然新版的一个重要变化是实现跨平台,为将接下来的分布式集群版打基础。

搜索引擎和非首页访问

  浏览访问日志是我的乐趣之一,有时控制不住,整天在那里病态地不断刷新,看过去10分钟有多少点击。做joyfire.net时甚至写了个小程序,每小时给我的email发统计报表。如果MSN Spaces推出报告站点流量的手机短信服务,估计我会忍不住去订。

  这个blog积累了一段时间,访问流量主要分为以下几种:

  1. 首页直接访问,由于MSN的特殊性,很大一部分都来自于MSN Messenger。
  2. 订阅RSS种子,这部分目前比重最大。
  3. 因为交换链接、发表评论或引用通告,反向链接过来的点击。
  4. 搜索引擎。

  前两种一般都访问最近更新的内容,第三种也有时效性,只有搜索引擎带来的流量比较稳定。分别看看5月份(因为考试没有怎么写BLOG)和去年11月(参加sohu的BLOG大赛)的访问日志,对比很明显。

  被频繁点击的是这几篇:

  关键字中,有关技术的很少。连2006年2月这篇关于MySQL的,搜索关键字也主要是“伍子婿”和“《孙子兵法》”这样的内容。