Wheeler Ward C
Division of Invertebrate Zoology, American Museum of Natural History, New York, NY 10024-5192, USA.
Cladistics. 2003 Jun;19(3):254-60.
The problem of determining the minimum-cost hypothetical ancestral sequences for a given cladogram is known to be NP-complete. This "tree alignment" problem has motivated the considerable effort placed in multiple sequence alignment procedures. Wheeler in 1996 proposed a heuristic method, direct optimization, to calculate cladogram costs without the intervention of multiple sequence alignment. This method, though more efficient in time and more effective in cladogram length than many alignment-based procedures, greedily optimizes nodes based on descendent information only. In their proposal of an exact multiple alignment solution, Sankoff et al. in 1976 described a heuristic procedure--the iterative improvement method--to create alignments at internal nodes by solving a series of median problems. The combination of a three-sequence direct optimization with iterative improvement and a branch-length-based cladogram cost procedure, provides an algorithm that frequently results in superior (i.e., lower) cladogram costs. This iterative pass optimization is both computation and memory intensive, but economies can be made to reduce this burden. An example in arthropod systematics is discussed.
已知对于给定的系统发育树，确定最小成本的假设祖先序列的问题是NP完全问题。这个“树比对”问题推动了人们在多序列比对程序方面付出大量努力。1996年，惠勒提出了一种启发式方法——直接优化，用于在不进行多序列比对干预的情况下计算系统发育树的成本。这种方法虽然在时间上比许多基于比对的程序更高效，在系统发育树长度方面更有效，但它仅基于后代信息贪婪地优化节点。1976年，桑科夫等人在提出精确的多比对解决方案时，描述了一种启发式程序——迭代改进方法，通过解决一系列中位数问题在内部节点创建比对。将三序列直接优化与迭代改进以及基于分支长度的系统发育树成本程序相结合，提供了一种算法，该算法经常能得出更优（即更低）的系统发育树成本。这种迭代遍历优化在计算和内存方面都很密集，但可以采取一些节省措施来减轻这种负担。文中讨论了节肢动物系统学中的一个例子。
