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

MethodWe 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. Two
schemes 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)

ResultPerformances of the two parallel schemes for NHML were
evaluated 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).

Homogeneous model

Non-homogeneous modelFig. 2: Performance evaluation on COMA (PACS-IX)
30,00025,00020,00015,00010,0005,000

02x22x42x82x164x168x1616x16

32x16

MPI processes x OpenMP threads

Phylogenetic position of a microaerophilic eukaryotic microbe, strain PAP020, inferredfrom 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. Theresultant ‘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 in
the bootstrap analysis.

100
100100(a)

10 μm

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