Generating most parsimonious reconstructions on a tree: A genralization of the Farris-Swofford-Maddison method

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. The authors formulate mathematically the problem with its generalization to the case of any tree and call it the MPR problem. They 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-Maddison method, is clarified by the concept of median interval. And then, with an explicit recursive formulation the authors generalize smoothly the Farris-Swofford-Maddison method. Also, the computational complexity of the present method is discussed. In the discussion, the PICK algorithm by Blum-Floyd-Pratt-Rivest-Tarjan is essential.