LayerScan: Simple heuristics for Phylogenetic Supertree Construction
Supertree methods estimate a single tree that contains all taxa from a collection of partially overlapped source trees. Nowadays, large-scale datasets still challenge existing and new methods to handle large datasets efficiently and accurately. In order to tackle the conflicts that naturally exist in the source trees for constructing a supertree, some matrix representation-based approaches try to identify a minimum cost and some other methods focus on reducing Robinson-Foulds distance explicitly while some "meta" methods combine existing supertree methods together. In our study, we expand a state-of-art display graph-based compatibility testing algorithm to explore a simple solution that combines several heuristics to achieve high efficiency and accuracy. From our preliminary experiments with a wide range of datasets, we find that our heuristic method performed well, especially on many real biological datasets.
Committee: David Fernandez-Baca (major professor), Oliver Eulenstein, Xiaoqiu Huang, Pavan Aduri and Ryan Martin.