Exhaustive tree searching

[Gordon D.Pusch]

James McInerney <james.o.mcinerney at may.ie> writes:

> Does anybody have pseudocode or a description of how to search all
> possible tree topologies?

P. Diaconis and S. Holmes found a "Gray Code" enumeration over
all unique tree topologies; see "Matchings and Phylogenies,"
Proc. Nat. Acad. Sciences, v.95, no.25, pp.14600--14602 (1998)
<http://www.pnas.org/cgi/content/abstract/95/25/14600>.
However, the number of tree topologies grows so rapidly with the
number of taxa that complete enumeration rapidly becomes impractical,
<http://taxonomy.zoology.gla.ac.uk/~mac/landscape/trees.html>;
hence, more emphasis is now placed on finding rapidly mixing
monte carlo algorithms to efficiently sample "tree space."

For more on algorithms on trees, see
<http://www-stat.stanford.edu/~susan/phylo/index/index.html>,
<http://www-stat.stanford.edu/~susan/papers/ima.ps>,
<http://www-stat.stanford.edu/~susan/papers/lap.pdf>,
<http://online.itp.ucsb.edu/online/infobio01/holmes/>.


-- Gordon D. Pusch

perl -e '$_ = "gdpusch\@NO.xnet.SPAM.com\n"; s/NO\.//; s/SPAM\.//; print;'
---