刘清雪， 王 亮

(吉林建筑科技学院 计算机科学与工程学院， 吉林 长春 130111)

0 引 言

系统发生是指生物形成或进化的历史[1]。系统发生分析是在所有可以系统发生过程中寻找最能真实反映历史的发生树，研究物种之间的进化关系。系统发生树的构建是一个NP问题，现在最常用的构建进化树的方法有距离法、最大简约法和最大似然法。最大简约法是基于最优原则的建树方法之一，其前期基础是“多序列比对”，研究结果以树的形式进行描述，并根据有无共同的祖先将其分为有根树和无根树。

1 基础理论与算法分析

系统发生树也称进化树，一般以二叉树的形式表示，它是由一系列代表当前物种的叶子节点和代表推断的祖先或进化事件发生的位置内部节点组成。根据系统发生树能否推断出共同祖先和进化方向分为有根树和无根树。树的分支式样无论有根还是无根均被称为拓扑结构。系统发生树可能的个数随序列个数急剧增加。由N个物种建立系统发生树，则可能的有根树(NR)和无根树(NU)的数目为：

(1)

(2)

1.1 后缀法

二叉树的遍历是二叉树最基本的操作，一次完整的遍历可以产生树中所有结点的一个线性序列。设L,V,R分别表示在位于某个结点时移到左子女、访问结点数据和移到右子女的操作，按从左到右的顺序遍历，则存在三种遍历方式，即LVR、VLR、LRV。根据V与L和R的相对位置，分别称这三种为中序、前序和后序遍历。如果用二叉树表示表达式，则对其进行中序、前序和后序遍历产生的线性序列与表达式的中缀、前缀和后缀自然对应。……