Abstract

The estimation of the Tree of Life, a rooted binary tree representing how all extant species evolved from a common ancestor, is one of the grand challenges of modern biology. Research groups around the world are attempting to estimate evolutionary trees on particular sets of species (typically clades, or rooted subtrees), in the hope that a final "supertree" can be produced from these smaller estimated trees through the addition of a "scaffold" tree of randomly sampled taxa from the tree of life. However, supertree estimation is itself a computationally challenging problem, because the most accurate trees are produced by running heuristics for NP-hard problems. In this paper we report on a study in which we parallelize SuperFine, the currently most accurate and efficient supertree estimation method. We explore performance of these parallel implementations on simulated data-sets with 1000 taxa and biological data-sets with up to 2,228 taxa. Our study reveals aspects of SuperFine that limit the speed-ups that are possible through the type of outer-loop parallelism we exploit.

Original languageEnglish (US)
Title of host publication27th Annual ACM Symposium on Applied Computing, SAC 2012
Pages1361-1367
Number of pages7
DOIs
StatePublished - Jul 12 2012
Event27th Annual ACM Symposium on Applied Computing, SAC 2012 - Trento, Italy
Duration: Mar 26 2012Mar 30 2012

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Other

Other27th Annual ACM Symposium on Applied Computing, SAC 2012
CountryItaly
CityTrento
Period3/26/123/30/12

Keywords

  • irregular applications
  • parallelization
  • phylogeny estimation
  • polytomy
  • shared memory
  • supertree

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Parallelizing SuperFine'. Together they form a unique fingerprint.

  • Cite this

    Neves, D. T., Warnow, T., Sobral, J. L., & Pingali, K. (2012). Parallelizing SuperFine. In 27th Annual ACM Symposium on Applied Computing, SAC 2012 (pp. 1361-1367). (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/2245276.2231992