External Review on Center for Computational Sciences

Division of Global Environment andBiological Sciences
Biological Science Group
Hashimoto, T.
Collaborative member of CCS（Department of Structural Biosciences,Graduate School of Life and Environmental Sciences, Univ. of Tsukuba）

Foundation

Division of Global Environment andBiological Sciences
Biological Science Groupー Created at Apr. 2004
Hashimoto, T.
Collaborative member(Dept. Structural Biosci., Univ. of Tsukuba)

Members of Biological Science group

Since Aug. 2005
• Center for Computational Sciences- Ass. Prof.
Yuji Inagaki• Dept. Structural Biosciences- Prof.
Tetsuo Hashimoto(Collaborative member)- Res. Assoc.

Miako Sakaguchi

Research Area

• Molecular Evolution- Global phylogeny of eukaryotes- Methodological studies on molecularphylogenetic inferenceBeautiful creatures
Rhizaria

ChromalveolatesPlantae

Excavata

Opisthokonts

Amoebozoa

Main Projects• Inference on the phylogenetic relationshipamong large groups of eukaryotes• Inference on the root of the tree of eukaryotes• Inference on the mitochondrial evolution• Inference on the plastid evolution• Methodological studies on molecularphylogenetic inference• Establishment of the methodology for large
scale phylogenetic analysis based on themaximum likelihood (ML) approachCollaboration with other Group in CCS‘Mol-Evol’ group:・Biological Science Group
Yuji Inagaki / T. Hashimoto・High Performance Computing Group
Prof. Mitsuhisa Sato (Director of CCS)
(Graduate students)
Yoshihiro Nakajima
Akihiro Aida (~Mar. 2007)

Collaboration with other Institutions

Univ. of Tsukuba, Bio.-Dept.
Kyoto Univ. Dr. Y. Sako
Osaka Univ. Dr. K. Tanabe
BiologicalScience

Juntendo Univ. Dr. T. Nara

Group, CCS,

JAMSTEC Dr. K. Takishita

Tsukuba Univ.

Dalhousie Univ. Dr. A. Roger
British Colombia Univ. Dr. P. KeelingSequence sequence
Alignment andData for Phylogenetic Analysis
Multiplealignment
Ribosomal protein mS30
Homo sapiens
Schizosaccharomyces pombe
Encephalitozoon cuniculi
Entamoeba histolytica
Plasmodium falciparum
Giardia intestinalis
Trichomonas vaginalis

AlignedHs
SpEc
Eh
Pf
Gi
Tv

Selected sites

HsSp
Ec
Eh
Pf
Gi
Tv

・Physicochemically similar aa are marked with same color・Column is called position or site

Phylogenetic Tree

A

Internal node

A～F：extant species, groups, etc.

E→ one of the relationships between
6 species

InternalbranchBDExternalbranchC→ ((A,(B,C)),F,(D,E)): tree topology
Branch length: substitution rate

FUnit: substitutions/siteMaximum Likelihood (ML) method
・Based on explicit evolutionary models, the analysis uses probability
to find a tree that best accounts for the variation in a data set
f (θ｜data) = Pr (data ｜θ) → maximize=(tree topology, branch lengths, α, π, etc.)log{ f (θ｜data)} (log-likelihood) → maximize
・Calculation is performed on each column of an alignment
・All possible trees are exhaustively examined → Select the ML tree・Robust against the violation of evolutionary rate constancy
between species (sequences) ⇒ applicable for diverse sequences
・Computationally intenseNumber of Possible Treesspecies number of tree topologies
123
45678910n1113
15
105
945
10,395
135,135
2,027,025･･･(2n-5)!
2n-3(n-3)!

Combined analysis based on Concatenate Model
Gene 1

Gene 2

Gene 3Species 1
Species 2
Species 3
Species 4

Species 1
Species 2
Species 3
Species 4Concatenate sequences of different genes⇒ regard as 1 gene
ML phylogenetic analysis＾⇒ a set of parameters： θCombined analysis based on Separate Model
S53

S52

S11 S12

Tree i

S51

S13

Gene 15 groups, 15 species
S41

S42 S43
S33
S56
S51

S32 S31

S11

Tree il2(i)(θ^2(i)|X2)

Gene 25 groups, 13 species

S22
S45 S44

S41

S31
S34
S32

lm(i)(θ^m(i)|Xm)

Gene m
5 groups, x species
The log-likelihood of the ML tree in total
mm m
^^ }]
max{Σ
l(θ|X}=max[Σ{Σlogf(X|θk(i)
k(i)
kk(i)
khk(i)
k=1i

For each of Tree i(i =1,…15)
calculate log-likelihoodof the gene k

S24S33S35(i=1,…,15)

S21
S22
S23

l1(i)(θ^1(i)|X1)

ki

k=1 h=1m^
Σl(θk(i)|Xk )k=1 k(i)+MPI-Puzzle – For exhaustive tree search• Calculated lnL by Tree-Puzzle
Sequential

T2

lnLT2T3

lnLT3···

TN

lnLTN

T945

lnLT945

lnLT2

T3

lnLT3TN+1

lnLTN+1Data

TN+2

lnLTN+2

TN+3

lnLTN+3T2N+1lnLT2N+1T2N+2lnLT2N+2

T2N+3lnLT2N+3······
lnLT944

T2······
T944

lnLT1···

lnLT1T1···

T1···

Data

MPI······

Phylogeny of Eukaryotes – Recent results
23-gene analyses – w/o α-tubulin ~10,000 positions< Separate model >(Exhaustive search for 945 trees)
Opisthokonta
Amoebozoa

4157
70
94

Stramenopiles/
Alveolates
Diplomonads/
Parabasalids
Euglenozoa/
Heterolobosea
Green plants
Red algae

・ Recovered three
eukaryotic “supergroups”– Unikont: Opisthokonta +Amoebozoa– Excavata: Dip/Par +Eug/Het– Plantae: G+RPhylogeny of Eukaryotes – Recent results
Multi-gene analyses – with ~8,500 positions< Separate model >(Exhaustive search for 10395 trees)
10036

Cryptomonad
Haptophytes
Red algae

754598

Guillardia

Pavlova

Glaucophytes

Multiple Gene Phylogenies

Green plants

Support the Monophyly ofAlveolates
Stramenopiles
Unikonts

Cryptomonad and Haptophyte
Host Lineages.
Patron, Inagaki, and Keeling:Curr. Biol. 2007

Summary of Research Activities 2005-2007
ー Biological Science Group ー

Publications

Total

Peer reviewed Review (In Jap.)

20424

Domestic Meetings
OralPosterInvited

1299International Meetings
OralPoster

Invited332Total
30
Total
8

Summary of Research Activities 2005-2007
ー Biological Science Group ーGrants: Grant-In-Aid for Scientific Research from JSPS
2005-2006 (B)¥14,200,000

2006-2007 (C)¥3,600,000

Grant-In-Aid for Young Scientists from JSPS
2006-2007 (B)¥2,600,000

Awards: Yuji Inagaki 2007
An award from the ministor of MEXT for young scientists

Short Term Future Plans• Phylogenetic relationship among large groupsof Eukaryotes- Excavata monophyly?
- Chromalveolates monophyly?
• Methodological studies on molecularphylogenetic inference- Imapct of the utilization of different models
for combining multiple genes(‘concatenate’ or ‘separate’)Short Term Future Plans

・ Establishment of the methodology for large
scale phylogenetic analysis based on themaximum likelihood (ML) approach- Exhaustive search up to 2,027,025 trees
for 10 lineages

Phylogenetic Analysis

Phylogenetic inference: estimation of :・Tree topology

・Branch length

Methods of phylogenetic reconstruction:
・Distance matrix method
・Maximum parsimony method
・Maximum likelihood method

Phylogenetic Analysis

Phylogenetic inference: estimation of :・Tree topology

・Branch length

Methods of phylogenetic reconstruction:
・Distance matrix method
・Maximum parsimony method
・Maximum likelihood method

Bootstrap analysis
PhylogeneticResampling

Original data set:Sample

inference
Pseudo sample 1
Pseudo sample 2
Pseudo sample 3→ Tree 1→ Tree 2→ Tree 3

Evaluation of theSampling error

Pseudo sample n→ Tree n

Phylogenetic inference
DM,MP,ML etc.

Bootstrap sample% of the trees thatreconstruct a given
intermal branch

Optimal treewith BP value at each internal branch⇒ Bootstrap (BP)valueMaximum likelihood method in brief
Example data set

S1 x1(4 species, n positions)
X = (Xij)(i=1,…4; j=1,…,n)h’th position
Xh=(X1h, X2h, X3h, X4h)

x3 S3

t1

i

j

t3

t2

t5

t4

S2 x2

T1x4 S4

S1,…, S4x1,…, x4i, jt1,…, t5

: Extant species: data of h’th position in extant species: data of h’th position in ancestral species: branch lengths

Assumption １. Xt : Continuous-time stationary Markov process with a transition probability Pij(t)transition probability k to l :Pkl(t) = P{Xt+s = l | Xs = k}
Evolution (substitutions) of each branch occurs independently.
Assumption ２．Each position evolves independently.

Under the Assumption 1.
Using Chapmann-Kolmogorov equation,← probability of having the data of h’th position,
given a tree topology, T1, and a transition matrix Pij (t)f (x1, x2, x3, x4|θ )=P{X0 = i}P{Xt = x , Xt = x , Xt = j | X0 = i}ΣΣi j11225x P{Xt5+t3 = x3, Xt5+t4 = x4 | Xt1 = x1, Xt2 = x2, Xt5 = j, X0 = i}=Σi {π Pix (t )Pix (t ) Σ Pij(t ) Pjx (t ) Pjx (t )}
i

1

1225

3

344j
πi : composition of nucleotide or amino acid i

S1 x1
t1x3 S3
i

j

t3

t2

t5

t4

S2 x2

T1x4 S4

S1,…, S4x1,…, x4i, jt1,…, t5

: Extant species: data of h’th position in extant species: data of h’th position in ancestral species: branch lengths

Under the Assumption 2.
Likelihood function of θgiven a data X can be written as:
nL (θ | X) =Π f (Xh | θ )h=1

Its log-likelihood:nl (θ | X) = Σ log f (Xh | θ )h=1

θ = ( t1, … , t5 ) : branch lengths

θ^ can be estimated by maximizing the log-likelihood function, ll (θ^ | X) = max {l (θ | X) : θ^ ∈ Θ }^By comparing the log-likelihood ( l (θ| X) ) values between the different tree
topologies, T1, T2, and T3, a tree with the highest log-likelihood value is selected
as the ML tree.

Evolutionary modelParameters-Tree topology, T

branch lengths (t1, …, t5)-Transition Probability

those included in Pij(t)-Composition

πi-Among site-rate heterogeneity α (shape parameter of Γ distribution)
Pij(t) : for nucleotide substitutions: for amino acid substitutions

Jukes-Cantor

PoissonKimura-2-parameter

PAM

HKY85

JTT

TN93

WAG

……..

……

Bootstrap resampling
Original data set： 4 × 10 matrix

Cryptosporidium

ACTAACTGAG

Toxoplasma

ACTATGAGAG

Theileria

GCTGTGAAAA

Plasmodium

GCTGTGATCA

Randomly resample 10 positions out of0123456789

10 positions in the original data set
CryptoCACTGAAGAAAACGTAATACGGCTAATGAG

.....

Toxo

CTGTGAAGTATACGAAATACGGGTATAGAG

.....

Theil

CTGTAAGATGTGCAAGATACAAGTGTAAAA.....

PlasmoCTGTACGTTG

TGCAAGCTCC

ATGTGTATCA.....

1452983740

4019608281

9752346789

Pseudo sample 1

Pseudo sample 2

Pseudo sample 3

ML tree of theoriginal data set

Cryptosporidium

Plasmodium
70

Theileria
Toxoplasma

Bootstrap sample 1
ML tree
PlasmoBootstrap sample 2
ML tree
PlasmoCryptoCryptoTheil

CryptoBootstrap sample 7
ML tree
PlasmoCryptoTheil

Bootstrap sample 5
ML tree

PlasmoPlasmoCryptoTheilToxo

Bootstrap sample 8
ML tree
PlasmoCryptoTheilToxo

Bootstrap sample 4
ML tree

TheilToxo

Bootstrap sample 6
ML tree
PlasmoCryptoToxo

Bootstrap sample 3
ML tree
Toxo
PlasmoCryptoTheilToxo

0.1substitutions／position

TheilToxo

TheilToxo

Bootstrap sample 9ML tree
PlasmoCryptoBootstrap sample 10
ML tree
PlasmoCrypto
Theil

TheilToxo

Toxo

Classical SSUrRNA tree Eukaryota＊(~mid 90’s)

Enatamoeba

Trypanosoma

Naegleria＊＊

Trichomonas＊Giardia＊Amitochondriate group

GlugeaSSUrRNA tree of Eukaryota(~mid 90’s）
Gruop

Presence of large
monophyletic groups

Metazoa
Fungi
Viridiplantae
LobosaRhodophyta

Endosymbiosis ofstramenopiles

proto-mitochondria

The branching order among
these groups was misleading!

Alveolata?

Pelobionta*

Because, long branch

Mycetozoa

Eukaryota

×Entamoebidae*

attraction (LBA) madeHeterolobosea

the SSUrRNA tree misleading.

Euglenozoa
Diplomonadida*Parabasalia*
Microsporidia*
Prokaryota (Outgroup)* Amitochondriate protist group

LBA― Most serious problemin phylogenetic analysis

Long Branch Attraction (LBA) artefact：the most serious problem in phylogenetic analyses

Outgroup

Real tree
Based on this tree, sequence data
at external nods are simulated.

Outgroup

Inferred tree based on thesimulated sequence data
Long branches are artificiallylocated at the base of the tree

SSUrRNA tree of Eukaryota(~mid 90’s）（late 90’s）

Gruop

Endosymbiosis ofproto-mitochondria?

Metazoa

Metazoa

Fungi

Fungi

Viridiplantae

Viridiplantae

LobosaLobosaRhodophyta

Rhodophyta

stramenopiles

Stramenopiles

Alveolata

AlveolataPelobionta*

Eukaryota

××？

Pelobionta*

Mycetozoa

Mycetozoa

Entamoebidae*

Entamoebidae*

Heterolobosea

Heterolobosea

Euglenozoa

Euglenozoa

Diplomonadida*

Diplomonadida*Parabasalia*

Parabasalia*

Microsporidia*

Microsporidia*

Prokaryota (Outgroup)* Amitochondriate protist group

No consensus on eukaryotic phylogeny !

Large group ⇒ Supergroup

Combined phylogeny

Metazoaof multi-genes (2000～）

Opisthokonta

Fungi
Microsporidia*

Mycetozoa

signals of individual genes

Entamoebidae*
Pelobionta*

×Amoebozoa

Viridiplantae
Rhodophyta
StramenopilesRobust inference

Alveolata
Euglenozoa
Heterolobosea

Large groups⇒

ConosaLobosea- To accumulate phylogenetic

Diplomonadida*

Supergroup

Parabasalia*

Outgroup* Amitochondriate groupPlantae・・・