University	  of	  Tsukuba	  	  | Center	  for	  Computational	  Sciences

HPC	  for	  Phylogenetic	  Tree	  Inference
MPI/OpenMP parallelization of	  the	  phylogenetic	  analyses	  based	  on	  non-­‐homogeneous	  substitution	  models
Introduction

The non-­‐homogeneous (NH) models, which allocate different
model parameters on each node of the tree to evaluate (Fig. 1), area realistic approach to reconstruct phylogenetic trees appropriatelyfrom real-­‐world sequence datasets, since the nucleotide and aminoacid sequences in distantly related species certainly evolve under
different evolutionary processes. However, the analyses with NH
models can be computationally intense as an enormous amount ofmodel parameters need to be optimized.

Fig.	  1:	  Substitution	  models	  used	  in	  phylogenetic	  analyses
R:	  root,	  t:	  branch	  length,	  Q:	  rate	  matrix,	  Θ:	  model	  parameters

Methods

Results

Performances of the two parallel schemes for NHML wereevaluated on COMA (PACS-­‐IX) system by analyzing simulated
nucleotide sequence data comprising 15 taxa and 10,000 bp. Bothtwo schemes showed good speed-­‐up up to 512 CPU cores (32computation nodes), especially the hybrid parallel scheme A) + B)
achieved ~78 times speed-­‐up compared to the serial code (Fig. 2).

Non-­‐homogeneous	  modelFig.	  2:	  Performance	  evaluation	  on	  COMA	  (PACS-­‐IX)
Total	  computational	  time	  (sec)

We applied two parallel computing methods, MPI and OpenMP, toaccelerate a phylogenetic program, NHML (Galtier and Gouy, Mol.
Bio. Evol., 1998), which implements a NH model for theheterogeneity of guanine and cytosine content across a tree. Twoschemes were applied to parallelize the maximum-­‐likelihood (ML)phylogenetic inference by NHML;
A) Parallel ML estimation of model parameters and branch lengthsof a fixed treeB) Parallel computation of likelihood scores for multiple trees,
where each likelihood can be calculated via A)

Homogeneous	  model

30,000	  25,000	  20,000	  15,000	  10,000	  5,000	  0	  2x2

2x4

2x8

2x16

4x16

8x16

16x16

32x16

MPI	  processes	  x	  OpenMP threads

Phylogenetic	  position	  of	  a	  microaerophilic	  eukaryotic	  microbe,	  strain	  PAP020,	  inferred	  from	  a	  large-­‐scale	  multigene	  dataset
We isolated a novel eukaryotic flagellate, strain PAP020 (Fig. 3a),from mangrove sediments. This strain has been maintained in (b)the laboratory under the microaerophilic condition. In thisstudy, we conducted RNA-­‐seq analysis on this strain, andassembled a alignment comprising 148 highly conserved
protein sequences shared among 83 diverse eukaryotes. The
resultant ‘148-­‐protein’ dataset was then subjected to themaximum-­‐likelihood (ML) phylogenetic analyses.
Strain PAP020 branched at the base of an assemblage ofanaerobic eukaryotes called Fornicata with high statisticalsupport (Fig. 3b). Thus, this strain most likely represents apreviously unnoticed lineage that is related intimately toFornicata, or is an ancestral member of Fornicata. Either way,
PAP020 is critical to understand the anaerobic metabolisms infornicates including giardiasis pathogen, Giardia intestinalis.
Fig.	  3:	  Phylogenetic	  position	  of	  strain	  PAP020(a) Strain PAP020. (b) ML tree inferred from a 148-­‐protein dataset. Only
bootstrap values greater than 80% are listed on the corresponding
bipartitions. Thick branches represent bipartitions with full support inthe bootstrap analysis.

contact	  address:	  yuji@ccs.tsukuba.ac.jp

100
100
100(a)

10	  μm

http://www.ccs.tsukuba.ac.jp/