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
