Document Actions
POY
Phylogenetic Analysis of DNA and other Data using Dynamic Homology
POY is a program for phylogenetic analysis of sequence and other data that implements a number of heuristic procedures to search for the tree or trees that have a minimum edit cost for the given data. For classic morphological data, the edit cost of character on a tree is the length of the character on the tree (see Farris 1970 and Fitch 1971). For optimization of unaligned sequence data on a tree, the basic algorithm to determine the edit cost is due to Sankoff (1975). This algorithm, however, is too computationally intensive to be of practical value, and it is known that the problem is NP-complete (Wang &Jiang 1994). The problem of finding, among all possible trees, those trees with a minimal edit cost for classic characters is in itself already NP-complete, so the problem that POY adresses consists of one NP-complete problem nested within another NP-complete problem.
Here is a link to POY's website:
http://research.amnh.org/scicomp/projects/poy.php#sample_files