Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method (Q1842656)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method |
scientific article |
Statements
Generating most parsimonious reconstructions on a tree: A generalization of the Farris-Swofford-Maddison method (English)
0 references
5 October 1995
0 references
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.
0 references
Farris-Swofford-Maddison method
0 references
tree
0 references
evaluated leaf tree
0 references
reconstruction
0 references
median interval
0 references
computational complexity
0 references