Computing the all-pairs quartet distance on a set of evolutionary trees.
We present two algorithms for calculating the quartet distance between all pairs of trees in a set of binary evolutionary trees on a common set of species. The algorithms exploit common substructure among the trees to speed up the pairwise distance calculations, thus performing significantly better on large sets of trees compared to performing distinct pairwise distance calculations, as we illustrate experimentally, where we see a speedup factor of around 130 in the best case.
Stissing
M
M
Bioinformatics Research Center and Department of Computer Science, University of Aarhus, Denmark.
Mailund
T
T
Pedersen
C N S
CN
Brodal
G S
GS
Fagerberg
R
R
D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D014644:Genetic Variation / Q000235:genetics*; D016013:Likelihood Functions; D015810:Linkage Disequilibrium / Q000235:genetics*; D008957:Models, Genetic; D015233:Models, Statistical; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D016008:Statistical Distributions