Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures
Identifieur interne : 000D71 ( Main/Exploration ); précédent : 000D70; suivant : 000D72Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures
Auteurs : Alexandros Stamatakis [Allemagne] ; Michael Ott [Allemagne]Source :
- Philosophical Transactions of the Royal Society B: Biological Sciences [ 0962-8436 ] ; 2008.
Abstract
The continuous accumulation of sequence data, for example, due to novel wet-laboratory techniques such as pyrosequencing, coupled with the increasing popularity of multi-gene phylogenies and emerging multi-core processor architectures that face problems of cache congestion, poses new challenges with respect to the efficient computation of the phylogenetic maximum-likelihood (ML) function. Here, we propose two approaches that can significantly speed up likelihood computations that typically represent over 95 per cent of the computational effort conducted by current ML or Bayesian inference programs. Initially, we present a method and an appropriate data structure to efficiently compute the likelihood score on ‘gappy’ multi-gene alignments. By ‘gappy’ we denote sampling-induced gaps owing to missing sequences in individual genes (partitions), i.e. not real alignment gaps. A first proof-of-concept implementation in
Url:
DOI: 10.1098/rstb.2008.0163
PubMed: 18852107
PubMed Central: 2607410
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: 000282
- to stream Pmc, to step Curation: 000282
- to stream Pmc, to step Checkpoint: 000674
- to stream Ncbi, to step Merge: 000066
- to stream Ncbi, to step Curation: 000066
- to stream Ncbi, to step Checkpoint: 000066
- to stream Main, to step Merge: 000D78
- to stream Main, to step Curation: 000D71
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures</title>
<author><name sortKey="Stamatakis, Alexandros" sort="Stamatakis, Alexandros" uniqKey="Stamatakis A" first="Alexandros" last="Stamatakis">Alexandros Stamatakis</name>
<affiliation wicri:level="3"><nlm:aff id="aff1"><institution>Department of Computer Science The Exelixis Lab, Ludwig-Maximilians-Universität München</institution>
<addr-line>Amalienstrasse 17, 80333 München, Germany</addr-line>
</nlm:aff>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Amalienstrasse 17, 80333 München</wicri:regionArea>
<placeName><region type="land" nuts="1">Bavière</region>
<region type="district" nuts="2">District de Haute-Bavière</region>
<settlement type="city">Munich</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Ott, Michael" sort="Ott, Michael" uniqKey="Ott M" first="Michael" last="Ott">Michael Ott</name>
<affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Department of Computer Science, Technische Universität München</institution>
<addr-line>Boltzmannstrasse 3, 85747 Garching b. München, Germany</addr-line>
</nlm:aff>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Boltzmannstrasse 3, 85747 Garching b. München</wicri:regionArea>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">18852107</idno>
<idno type="pmc">2607410</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2607410</idno>
<idno type="RBID">PMC:2607410</idno>
<idno type="doi">10.1098/rstb.2008.0163</idno>
<date when="2008">2008</date>
<idno type="wicri:Area/Pmc/Corpus">000282</idno>
<idno type="wicri:Area/Pmc/Curation">000282</idno>
<idno type="wicri:Area/Pmc/Checkpoint">000674</idno>
<idno type="wicri:Area/Ncbi/Merge">000066</idno>
<idno type="wicri:Area/Ncbi/Curation">000066</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">000066</idno>
<idno type="wicri:doubleKey">0962-8436:2008:Stamatakis A:efficient:computation:of</idno>
<idno type="wicri:Area/Main/Merge">000D78</idno>
<idno type="wicri:Area/Main/Curation">000D71</idno>
<idno type="wicri:Area/Main/Exploration">000D71</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures</title>
<author><name sortKey="Stamatakis, Alexandros" sort="Stamatakis, Alexandros" uniqKey="Stamatakis A" first="Alexandros" last="Stamatakis">Alexandros Stamatakis</name>
<affiliation wicri:level="3"><nlm:aff id="aff1"><institution>Department of Computer Science The Exelixis Lab, Ludwig-Maximilians-Universität München</institution>
<addr-line>Amalienstrasse 17, 80333 München, Germany</addr-line>
</nlm:aff>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Amalienstrasse 17, 80333 München</wicri:regionArea>
<placeName><region type="land" nuts="1">Bavière</region>
<region type="district" nuts="2">District de Haute-Bavière</region>
<settlement type="city">Munich</settlement>
</placeName>
</affiliation>
</author>
<author><name sortKey="Ott, Michael" sort="Ott, Michael" uniqKey="Ott M" first="Michael" last="Ott">Michael Ott</name>
<affiliation wicri:level="1"><nlm:aff id="aff2"><institution>Department of Computer Science, Technische Universität München</institution>
<addr-line>Boltzmannstrasse 3, 85747 Garching b. München, Germany</addr-line>
</nlm:aff>
<country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Boltzmannstrasse 3, 85747 Garching b. München</wicri:regionArea>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
<wicri:noRegion>85747 Garching b. München</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j">Philosophical Transactions of the Royal Society B: Biological Sciences</title>
<idno type="ISSN">0962-8436</idno>
<idno type="eISSN">1471-2970</idno>
<imprint><date when="2008">2008</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><p>The continuous accumulation of sequence data, for example, due to novel wet-laboratory techniques such as pyrosequencing, coupled with the increasing popularity of multi-gene phylogenies and emerging multi-core processor architectures that face problems of cache congestion, poses new challenges with respect to the efficient computation of the phylogenetic maximum-likelihood (ML) function. Here, we propose two approaches that can significantly speed up likelihood computations that typically represent over 95 per cent of the computational effort conducted by current ML or Bayesian inference programs. Initially, we present a method and an appropriate data structure to efficiently compute the likelihood score on ‘gappy’ multi-gene alignments. By ‘gappy’ we denote sampling-induced gaps owing to missing sequences in individual genes (partitions), i.e. not real alignment gaps. A first proof-of-concept implementation in <sc>RAxML</sc>
indicates that this approach can accelerate inferences on large and gappy alignments by approximately one order of magnitude. Moreover, we present insights and initial performance results on multi-core architectures obtained during the transition from an OpenMP-based to a Pthreads-based fine-grained parallelization of the ML function.</p>
</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
</country>
<region><li>Bavière</li>
<li>District de Haute-Bavière</li>
</region>
<settlement><li>Munich</li>
</settlement>
</list>
<tree><country name="Allemagne"><region name="Bavière"><name sortKey="Stamatakis, Alexandros" sort="Stamatakis, Alexandros" uniqKey="Stamatakis A" first="Alexandros" last="Stamatakis">Alexandros Stamatakis</name>
</region>
<name sortKey="Ott, Michael" sort="Ott, Michael" uniqKey="Ott M" first="Michael" last="Ott">Michael Ott</name>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000D71 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 000D71 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Ticri/CIDE |area= CyberinfraV1 |flux= Main |étape= Exploration |type= RBID |clé= PMC:2607410 |texte= Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i -Sk "pubmed:18852107" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd \ | NlmPubMed2Wicri -a CyberinfraV1
![]() | This area was generated with Dilib version V0.6.25. | ![]() |