Unlikelihood that minimal phylogenies for a realistic biological study can be constructed in reasonable computational time

The problem of determining a phylogeny of maximum parsimony from a given set of protein sequences is defined. It is shown that this problem is what is called, in computer science, NP-complete. The implication of this result is that it is equivalent in difficulty to a host of other problems in combinatorial optimization which are notorious for their intractability. This implies that it is more fruitful to attempt to develop heuristic techniques (which do not guarantee maximum parsimony but which do run in reasonable computer time) than to try to develop exact algorithms for phylogeny construction