evol. trees and Steiner trees?
joe at evolution.genetics.washington.edu
Sat Oct 28 00:34:51 EST 1995
In article <46qh92$eu at tiete.dcc.unicamp.br>,
Joao Carlos Setubal <setubal> wrote:
>Are there any works that present algorithms for tree reconstruction based on
>Steiner tree algorithms?
>All I know is that the Steiner problem was used to show the NP-completeness of
>tree reconstruction by parsimony (cf. Foulds and Graham, Adv. Appl. Math. 1982,
>and Day, Johnson, Sankoff, Math. Biosc. , 1986).
All parsimony methods try to find Steiner trees in a graph. The original
parsimony paper, which was by Edwards and Cavalli-Sforza in 1964, put
forward a Steiner tree in a space of gene frequencies (an n-dimensional
For references, try Swofford and Olsen's nice review in chapter 11 of
Hillis and Moritz's book (1990) "Molecular systematics".
Joe Felsenstein joe at genetics.washington.edu (IP No. 22.214.171.124)
Dept. of Genetics, Univ. of Washington, Box 357360, Seattle, WA 98195-7360 USA
More information about the Mol-evol