Parallelizing SuperFine

Diogo Telmo Neves, Tandy Warnow, João Luís Sobral, Keshav Pingali

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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
Number of pages7
StatePublished - 2012
Externally publishedYes
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


Other27th Annual ACM Symposium on Applied Computing, SAC 2012


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

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Parallelizing SuperFine'. Together they form a unique fingerprint.
  • Data for SuperFine, DACTAL, and BeeTLe

    Swenson, M. S. (Creator), Suri, R. (Creator), Linder, C. R. (Creator), Warnow, T. (Creator), Nguyen, N. (Creator), Mirarab, S. (Creator), Neves, D. T. (Creator), Sobral, J. L. (Creator), Pingali, K. (Creator), Nelesen, S. (Creator), Liu, K. (Creator) & Wang, L. (Creator), University of Illinois Urbana-Champaign, Sep 20 2011


Cite this