龙源期刊网 http://www.qikan.com.cn
系统发生网络构建算法综述
作者：王娟等
来源：《智能计算机与应用》2014年第01期
摘要：物种的进化史通常被描述成一棵有根系统树，但是当物种进化过程中发生网状进化事件（如，杂交、重组和水平基因转移）时，物种的进化史不再适合被描述成系统树。系统发生网络是系统树的一般化，也是被用来描述物种的进化史，并可以描述物种的网状进化事件。而且系统发生网络也可以可视化冲突数据集，如由不同的基因得到的物种树。因此，系统发生网络的研究是生物信息的一个重要领域。介绍了系统发生网络的概念、发展、研究现状，总结了现有的系统发生网络构建算法。
关键词：系统发生网络； 网状进化事件； 隐式网络； 显式网络
中图分类号：TP301 文献标识码：A文章编号：2095-2163（2014）01-0032-04 0引言
通常用系统树来表示一组分类单元的进化关系，这一模式有利于假设的讨论和检验。然而当描述更复杂的进化关系时，系统树的功能则略显不足。随着研究的逐渐深入，科学家们发现有些物种在进化过程中发生了网状进化事件，如反转（reversal）、移位（translocation）和转位（transposition）、重组（recombination）、水平基因转移（horizontal gene transfer，HGT）、杂交（hybridization）、基因转移或者基因重复和丢失[1-6]等，则此时生物的父代即不止一个，系统树不能描述各代之间的进化关系，因此促动了系统发生网络（phylogenetic network）的出现。系统发生网络构建方法及理论分析的研究是计算生物学的一个重要方向。系统发生网络是系统树的一般形式，又可译作系统演化网络、系统进化网络、进化网络。该种网络更适合那些发生了网状进化事件的数据，而且，对于树式进化模式（碱基的替代、插入、删除等）进化而来的数据，系统发生网络也可以实现数据中冲突信息的清晰表达，如由于不完全谱系分类机制或者是由于进化模型假设的不足引起的冲突信息[7]。系统发生网络是一个无环图，图中有些节点的父节点个数 ≥ 2（这种节点也被称为网络节点），如果图中没有网络节点，那么这时的系统发生网络就是一棵树。
系统发生网络根据拓扑结构分为无根（unrooted）网络和有根（rooted）网络；根据功能分为隐式（implicit）和显式（explicit）网络[8]。隐式网络（例如分割网络和准中位数网络）则可用来表示冲突信息，这些冲突信息可能来自各种原因，如模型误设（model misspecifi cation）；而显式网络则是尽力捕获生物进化过程中的网络进化事件，如杂交（hybridization）[9-10]、重组（recombination）[11-15]及水平基因转移（horizontal gene transfer， 简称HGT）[7，16-18]。显式网络中的内部节点表示祖先物种，且其中的网络节点对应所考虑的生物进化过程[14-16]，而隐式网络中网络节点没有任何生物解释。显式网络通常是有根的，因为生物进