进化树搜索

单一的进化树的数量会随着分类群数量的增长而呈指数增长,从而变为一个天文数字。由于计算能力的限制,现在一般只允许对很小一部分的可能的进化树进行搜索。具体的数目主要依赖于分类群的数量、优化标准、参数设定、数据结构、计算机硬件以及计算机软件。 有两种搜索方法保证可以找到最优化的进化树：穷举法和树枝 跳跃法(BB)。对于一个很大的数据集,这两种方法都很不实用。对分类群数量的限制主要取决于数据结构和计算机速度,但是对于超过20个分类群的数据集,BB方法很少会得到应用。穷举法要根据优化标准,对每一个可能的进化树进行评估。BB方法提供一个逻辑方法,以确定那些进化树值得评估,而另一些进化树可被简单屏蔽。因此BB方法通常要比穷举法快得多。绝大多数分析方法都使用“启发式”的搜索。启发式现搜索出相近的次优化的进化树家族(“岛屿”),然后从中得到优化解(“山顶”)。不同的算法用不同程度的精确性搜索这些岛屿和山顶。最彻底也是最慢的程序(TBR,tree bisection-reconnection,进化树对分重接)先把进化树在每一个内部树枝处劈开,然后以任意方式将劈开的碎片重新组合起来。最快的算法只是检查一下相邻终端的不太重要的重新组合,因此倾向于找到最近的岛屿的山顶。降低搜索代价的最好方法是对数据集进行剪除。影响优化搜索策略选择的因素(数据量,数据结构,时间量,硬件,分析目的)太复杂,无法推荐一个简单可行的处方。因此进行搜索的用户必须对数据非常熟悉且有明确的目标,了解各种各样的搜索程序及自己硬件设备和软件的能力。除上述当前应用最广的方法外,还有大量的建立和搜索进化树的其它方法。这些方法包括Wagner距离方法和亲近方法(距离转化方法)；Lake的不变式方法(一个基于特征符的方法,它选择的拓扑结构包含一个意义重大的正数以支持颠换)；Hadamard结合方法(一个精细的代数方阵方法,对距离数据或者观察到的特征符进行修正)；裂解方法(这个方法决定在数据中应该支持哪一个基于距离的可选的拓扑结构)；四重奏迷惑(Quartet puzzling)方法可以为ML建树方法所应用,这个算法相对而言是个较快的进化树搜索算法。