evol. trees and Steiner trees?

Joe Felsenstein 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 
Euclidean space).

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.
 Dept. of Genetics, Univ. of Washington, Box 357360, Seattle, WA 98195-7360 USA

More information about the Mol-evol mailing list