Format

Send to:

Choose Destination
See comment in PubMed Commons below
Philos Trans R Soc Lond B Biol Sci. 2008 Dec 27;363(1512):3977-84. doi: 10.1098/rstb.2008.0163.

Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures.

Author information

  • 1Department of Computer Science The Exelixis Lab, Ludwig-Maximilians-Universität München, Amalienstrasse 17, 80333 München, Germany. alexandros.stamatakis@gmail.com

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

PMID:
18852107
[PubMed - indexed for MEDLINE]
PMCID:
PMC2607410
Free PMC Article
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for HighWire Icon for PubMed Central
    Loading ...
    Write to the Help Desk