Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method Original Research Article

A combinatorial optimization problem regarding the assignments (called reconstructions) for a tree has been discussed in phylogenetic analysis. Farris, Swofford and Maddison have solved the problem of finding the most parsimonious reconstructions on a completely bifurcating phylogenetic tree. We formulate mathematically the problem with its generalization to the case of any tree and call it the MPR problem. We present a solution for the generalized problem by introducing the concept of median interval obtained from sorting the endpoints of some closed intervals. The state set operation which plays an important role in the Farris-Swofford-Mad-dison method, is clarified by the concept of median interval. And then, with an explicit recursive formulation we generalize smoothly their method. Also, the computational complexity of our method is discussed. In the discussion, the PICK algorithm by Blum-Floyd-Pratt-Rivest-Tarjan is essential.