Show simple item record

dc.contributor.author
Mitov, Venelin
dc.contributor.author
Stadler, Tanja
dc.date.accessioned
2019-04-08T06:43:43Z
dc.date.available
2019-04-07T11:34:08Z
dc.date.available
2019-04-08T06:43:43Z
dc.date.issued
2019-04
dc.identifier.issn
2041-210X
dc.identifier.issn
2041-2096
dc.identifier.other
10.1111/2041-210X.13136
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/336648
dc.identifier.doi
10.3929/ethz-b-000336648
dc.description.abstract
1. Phylogenetic comparative models (PCMs) have been used to study macroevolutionary patterns, to characterize adaptive phenotypic landscapes, to quantify rates of evolution, to measure trait heritability, and to test various evolutionary hypotheses. A major obstacle to applying these models has been the complexity of evaluating their likelihood function. Recent works have shown that for many PCMs, the likelihood can be obtained in time proportional to the size of the tree based on post‐order tree traversal, also known as pruning. Despite this progress, inferring complex multi‐trait PCMs on large trees remains a time‐intensive task. Here, we study parallelizing the pruning algorithm as a generic technique for speeding‐up PCM‐inference. 2. We implement several parallel traversal algorithms in the form of a generic C++ library for Serial and Parallel LIneage Traversal of Trees (SPLITT). Based on SPLITT, we provide examples of parallel likelihood evaluation for several popular PCMs, ranging from a single‐trait Brownian motion model to complex multi‐trait Ornstein‐Uhlenbeck and mixed Gaussian phylogenetic models. 3. Using the phylogenetic Ornstein–Uhlenbeck mixed model (POUMM) as a showcase, we run benchmarks on up to 24 CPU cores, reporting up to an order of magnitude parallel speed‐up for the likelihood calculation on simulated balanced and unbalanced trees of up to 100,000 tips with up to 16 traits. Noticing that the parallel speed‐up depends on multiple factors, the SPLITT library is capable to automatically select the fastest traversal strategy for a given hardware, tree‐topology, and data. Combining SPLITT likelihood calculation with adaptive Metropolis sampling on real data, we show that the time for Bayesian POUMM inference on a tree of 10,000 tips can be reduced from several days to less than an hour. 4. We conclude that parallel pruning effectively accelerates the likelihood calculation and, thus, the statistical inference of Gaussian phylogenetic models. For time‐intensive Bayesian inferences, we recommend combining this technique with adaptive Metropolis sampling. Beyond Gaussian models, the parallel tree traversal can be applied to numerous other models, including discrete trait and birth–death population dynamics models. Currently, SPLITT supports multi‐core shared memory architectures, but can be extended to distributed memory architectures as well as graphical processing units.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Wiley
en_US
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
dc.subject
continuous time Markov process
en_US
dc.subject
continuous trait
en_US
dc.subject
discrete character
en_US
dc.subject
pre‐order traversal
en_US
dc.title
Parallel likelihood calculation for phylogenetic comparative models: The SPLITT C++ library
en_US
dc.type
Journal Article
dc.rights.license
Creative Commons Attribution 4.0 International
dc.date.published
2018-12-13
ethz.journal.title
Methods in Ecology and Evolution
ethz.journal.volume
10
en_US
ethz.journal.issue
4
en_US
ethz.journal.abbreviated
Methods Ecol. Evol.
ethz.pages.start
493
en_US
ethz.pages.end
506
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
Oxford
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02060 - Dep. Biosysteme / Dep. of Biosystems Science and Eng.::09490 - Stadler, Tanja / Stadler, Tanja
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02060 - Dep. Biosysteme / Dep. of Biosystems Science and Eng.::09490 - Stadler, Tanja / Stadler, Tanja
ethz.date.deposited
2019-04-07T11:34:10Z
ethz.source
SCOPUS
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-04-08T06:43:49Z
ethz.rosetta.lastUpdated
2020-02-15T18:20:40Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Parallel%20likelihood%20calculation%20for%20phylogenetic%20comparative%20models:%20The%20SPLITT%20C++%20library&rft.jtitle=Methods%20in%20Ecology%20and%20Evolution&rft.date=2019-04&rft.volume=10&rft.issue=4&rft.spage=493&rft.epage=506&rft.issn=2041-210X&2041-2096&rft.au=Mitov,%20Venelin&Stadler,%20Tanja&rft.genre=article&rft_id=info:doi/10.1111/2041-210X.13136&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record