TurboTree：一种用于构建最小树的快速算法。

TurboTree: a fast algorithm for minimal trees.

作者信息

Penny D, Hendy M D

机构信息

Department of Botany and Zoology, Massey University, Palmerston North, New Zealand.

出版信息

Comput Appl Biosci. 1987 Sep;3(3):183-7.

PMID:3453227

Abstract

A branch and bound algorithm is described for searching rapidly for minimal length trees from biological data. The algorithm adds characters one at a time, rather than adding taxa, as in previous branch and bound methods. The algorithm has been programmed and is available from the authors. A worked example is given with 33 characters and 15 taxa. About 8 x 10(12) binary trees are possible with 15 taxa but the branch and bound program finds the minimal tree in less than 5 min on an IBM PC.

摘要

本文描述了一种分支定界算法，用于从生物学数据中快速搜索最小长度树。与以往的分支定界方法不同，该算法是一次添加一个字符，而不是添加分类单元。该算法已被编程，可从作者处获得。文中给出了一个包含33个字符和15个分类单元的实例。15个分类单元可能有大约8×10¹²个二叉树，但分支定界程序在一台IBM个人电脑上不到5分钟就能找到最小树。