Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method (Q1842656)

Let \(T= (V_ 0\cup V_ H, E, \sigma)\) be any tree where \(V_ 0\) is the set of leaves, \(V_ H\) is the set of internal nodes, \(E\) is the set of branches, and \(\sigma\) is a function over \(V_ 0\) with real or natural values. Such a tree is called an evaluated leaf tree, or briefly an el- tree. Let \(\lambda\) be an assignment for the vertices of an el-tree such that \(\lambda| V_ 0= \sigma\), called an reconstruction on \(T\). Set \[ L(\lambda)= \sum_{\{u, v\}\in E} | \lambda(u)- \lambda(v)|. \] The paper considers the following optimization problems: (1) Determine the minimum value for \(L(\lambda)\) over all reconstructions on \(T\). (2) Find a reconstruction which attains this value. The authors present a solution for the problems by introducing the concept of median interval. Also the computational complexity of this method is discussed.