Exhaustive tree searching

Gordon D.Pusch gdpusch at NO.xnet.SPAM.com
Sat Feb 22 15:25:26 EST 2003

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)
However, the number of tree topologies grows so rapidly with the
number of taxa that complete enumeration rapidly becomes impractical,
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

-- Gordon D. Pusch

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

More information about the Mol-evol mailing list