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

Fingerprint

Binary trees
Scaffolds
Computational complexity

Keywords

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

ASJC Scopus subject areas

  • Software

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

Parallelizing SuperFine. / Neves, Diogo Telmo; Warnow, Tandy; Sobral, João Luís; Pingali, Keshav.

27th Annual ACM Symposium on Applied Computing, SAC 2012. 2012. p. 1361-1367 (Proceedings of the ACM Symposium on Applied Computing).

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

Neves, DT, Warnow, T, Sobral, JL & Pingali, K 2012, Parallelizing SuperFine. in 27th Annual ACM Symposium on Applied Computing, SAC 2012. Proceedings of the ACM Symposium on Applied Computing, pp. 1361-1367, 27th Annual ACM Symposium on Applied Computing, SAC 2012, Trento, Italy, 3/26/12. https://doi.org/10.1145/2245276.2231992
Neves DT, Warnow T, Sobral JL, Pingali K. Parallelizing SuperFine. In 27th Annual ACM Symposium on Applied Computing, SAC 2012. 2012. p. 1361-1367. (Proceedings of the ACM Symposium on Applied Computing). https://doi.org/10.1145/2245276.2231992
Neves, Diogo Telmo ; Warnow, Tandy ; Sobral, João Luís ; Pingali, Keshav. / Parallelizing SuperFine. 27th Annual ACM Symposium on Applied Computing, SAC 2012. 2012. pp. 1361-1367 (Proceedings of the ACM Symposium on Applied Computing).
@inproceedings{ab46db871f5842a29355433ddf592940,
title = "Parallelizing SuperFine",
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.",
keywords = "irregular applications, parallelization, phylogeny estimation, polytomy, shared memory, supertree",
author = "Neves, {Diogo Telmo} and Tandy Warnow and Sobral, {Jo{\~a}o Lu{\'i}s} and Keshav Pingali",
year = "2012",
month = "7",
day = "12",
doi = "10.1145/2245276.2231992",
language = "English (US)",
isbn = "9781450308571",
series = "Proceedings of the ACM Symposium on Applied Computing",
pages = "1361--1367",
booktitle = "27th Annual ACM Symposium on Applied Computing, SAC 2012",

}

TY - GEN

T1 - Parallelizing SuperFine

AU - Neves, Diogo Telmo

AU - Warnow, Tandy

AU - Sobral, João Luís

AU - Pingali, Keshav

PY - 2012/7/12

Y1 - 2012/7/12

N2 - 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.

AB - 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.

KW - irregular applications

KW - parallelization

KW - phylogeny estimation

KW - polytomy

KW - shared memory

KW - supertree

UR - http://www.scopus.com/inward/record.url?scp=84863572075&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863572075&partnerID=8YFLogxK

U2 - 10.1145/2245276.2231992

DO - 10.1145/2245276.2231992

M3 - Conference contribution

AN - SCOPUS:84863572075

SN - 9781450308571

T3 - Proceedings of the ACM Symposium on Applied Computing

SP - 1361

EP - 1367

BT - 27th Annual ACM Symposium on Applied Computing, SAC 2012

ER -