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



More information about the Mol-evol mailing list