We now have a dynamic programming algorithm that's going to be able to reconstruct ancestral states in binary trees. But this algorithm assumes that the structure of the tree was given. For example, here was an optimal solution to the small parsimony problem for our toy multiple alignment of four species, if we're dealing with unrooted trees. But it assumes that chimp and human are neighbors and that seal and whale are neighbors. It seems unlikely, but there's nothing preventing chimp and seal from being neighbors instead. We need to find the smallest parsimonious score for this unrooted tree as well, which is 11. We also need to find the smallest parsimonious score for the tree in which chimp and whale are neighbors, where that score is also 11. Now I'll have you note that when applying our algorithm for small parsimony, we're going to allow an internal edge to have weight 0, as shown here. Because if we were to compress this edge, then we would no longer have a binary tree. So this brings us to the large parsimony problem in which we must find an assignment of ancestral states to internal nodes over all possible unrooted binary tree structures. As you might guess, this problem is NP-Complete. So, let's design a greedy heuristic for this problem. First, I want you to think about removing an internal edge of an unrooted binary tree, i.e., an edge that connects two internal nodes along with the nodes that it connects. So for example, if we delete the edge connecting a and b here along with the nodes a and b themselves, then we can see that we have disconnected this unrooted, binary tree into four, disjoint subtrees, that I'll denote W, X, Y, and Z. There are three ways to then rearrange these four subtrees around that internal edge that connected a and b. So the operation in which we move from one of these trees to the other is called a "nearest neighbor interchange" for this internal edge connecting a and b. To test your knowledge of this operation, you might like to implement a program that returns the two nearest neighbors of a given unrooted binary tree with respect to a given internal edge. This program will then be used for the "nearest neighbor interchange heuristic" for the large parsimony problem, which begins with an arbitrary unrooted binary tree, then performs all possible nearest neighbor interchanges over every possible internal edge of the tree, then solving the small parsimony problem for each such unrooted tree. Now, if we find a tree whose minimum parsimony score improves over the current tree that we have, then we set the current tree equal to this tree, and we iterate. Otherwise, we can't improve on the current tree via a nearest neighbor interchange, and we simply return the current tree. Try implementing this greedy heuristic yourself before we move on to the final section of this chapter.