昆明动物所等发布超大规模进化树构建软件HPTree

近日，中国科学院昆明动物研究所马占山团队与天津大学教授邹权、厦门大学科研人员联合发布了为千兆(GB)级基因序列数据构建进化树的软件HPTree。该软件使用谷歌Hadoop并行技术和美国加利福尼亚大学伯克利分校Spark集群大数据技术作为并行处理平台，利用计算机集群对基因序列大数据进行分割处理和整合，相关的软件和网站服务发布在http://lab.malab.cn/soft/HPtree/上，软件可以安装在亚马逊（Amazon Cloud）等云计算平台。其技术报告发表在BMC System Biology上。

进化树，也称生物系统发育树或生命树。这一概念最早发源于19世纪中叶的古生物学研究，达尔文在《物种起源》中勾画了最早的进化树之一。对进化树广泛研究和构建则始于20世纪90年代，特别是在最近20年间，基因测序技术以及分子进化研究使得构建进化树成为进化生物学研究不可或缺的技术。达尔文进化论核心思想之一是地球上生命“同根”，即所有物种都有共同起源，并能在生命进化树上找到自己的位置。然而，与人类对宇宙探索类似，进化树构建并不能够一蹴而就，原因至少包括：

其一，我们不仅可能永远都难以获得地球上所有已灭绝物种的信息，而且地球上还存在大量未经发现的“暗物种”。例如，不到10年前才发起的人类微生物群系计划（HMP：Human Microbiome Project）揭示，人体体内（肠道、口腔、呼吸道、生殖道）和体表生活着大量先前未知的微生物（包括细菌、病毒、真菌、质粒、噬菌体等），这些微生物只有依赖最新的微生物宏基因测序技术才能发现。事实上，HMP研究发现，在宏基因测序技术发明之前，人类仅仅能够检测到不足10%的肠道细菌种类，而对其它90%的细菌几乎一无所知。地球上其它动植物体内或体表，乃至所有生命可能存在的生境（例如土壤、湖泊、森林、河流、海洋、冰川，包括呼吸的室内外空气中）都存在类似比例尚待鉴定发现的微生物。科学家发现，现代人诸多“文明、富贵病”（例如肥胖、糖尿病、痛风、过敏、抑郁、自闭症）都与肠道菌群有着不同程度的相关。原因之一可能是，现代饮食和生活方式的改变破坏了人类与其肠道菌群长期进化形成的互惠共生机制，而大幅度增加了现代人对于这些代谢、免疫、情绪相关疾病的易感性。因此，预计在不远的未来，对微生物群系的广泛研究会对现有进化树构建方法和技术带来全新挑战。

其二，进化树计算之所以会遇到终极挑战，是由于进化树构建在计算机科学属于所谓的“NP-Hard”问题，绝大多数计算机科学家认为，当所要解决的问题足够大时（例如所要构建的进化树足够大时），即使采用目前人类所发明的最快速计算机（或许包括未来所发明的）也无法完成计算过程。数学家则将证明NP-Hard问题不存在“简单”算法（当然包括人工智能）的问题列为千禧年期待证明、并被悬赏百万美元的七大难题之首。令人失望的是，NP-Hard类问题在科学、工程、生物信息计算、乃至日常生活中所抽象出来的计算问题中都占有相当比例；或许可以将其比喻为计算科学领域的“暗物质”。为此，目前所有进化树计算方法最终都会受到进化树大小的限制，进化树越大（物种越多），计算越复杂（耗费时间和计算机内存）。可以肯定的是，进化树构建问题的复杂性是不断增长的过程，科学家只有采用一些巧夺天工，但本质上仍是探索、启示性的算法才能获得问题的近似答案；而绝大多数科学家相信，理论上最优并且“可计算”的算法可能永远也无法获得。　　

马占山团队等此次发布的HPTree软件采用了目前最先进的并行计算技术，即支撑谷歌公司搜索引擎的Hadoop技术，以及由加州大学伯克利分校所研发的Spark大数据分析技术，从而将进化树构建推进到了千兆(GB)级基因序列数据的前沿。目前，绝大多数进化树构建软件在构建千兆级序列进化树时都需要依赖于超级计算机集群，或计算太慢而难以在普通服务器完成。HPTree软件可以在由普通工作站、甚至廉价PC搭建的Hadoop平台上运行，可大幅度降低其计算成本。

HPTree的研制和测试始于2015年，其技术日趋成熟。事实上，HPTree最大的优势是其强大的可扩展性，研发团队在普通学科组计算平台已能够处理千兆级别的进化树构建。随着硬件平台的升级（例如移植到云平台、或超级计算机集群平台），HPTree软件的优势会更显著。这是因为HPTree采用的计算框架正是像谷歌这些IT巨商用于支撑他们搜索引擎的Hadoop技术，以及先进的大数据分析技术(Spark)。如前所分析，随着全球在微生物群系研究领域所产生的宏基因大数据不断增长，对HPTree技术和软件的需求应随之大幅度增高。

显然，HPTree并不能一劳永逸地解决进化树计算、作为NP-Hard难题之一未来可能会遇到的终极计算挑战。HPTree软件的算法设计策略非常简单，或许类似《西游记》中孙悟空在需要时可以顷刻克隆出一大群猴孙，从而能够完成对超大规模基因序列数据的并行处理，快速高效地构建出相应的进化树。对于小规模数据，自然也没有必要变出一大堆猴子，因此HPTree优势在于能够处理大数据。　

HPTree软件技术的开发研制得到了中科院遗传资源与进化国家重点实验室开放课题、云岭产业技术领军人才等的资助，并与厦门大学副教授曾翔祥合作完成。