Noname manusc ip No.
(will be inse ed by he edi o )
Building la ge phylogene ic ees on coa se-g ained
pa allel machines
Keane, T.M.1, Page, A.J.2, Naugh on, T.J.2, T a e s, S.A.A.1, McIne ney,
J.O.1
1Depa men o Biology, Na ional Uni e si y o I eland, Maynoo h, Co.Kilda e, I eland.
2Depa men o Compu e Science, Na ional Uni e si y o I eland, Maynoo h, Co.Kilda e,
I eland.
The da e o eceip and accep ance will be inse ed by he edi o
Abs ac Phylogene ic analysis is an a ea o compu a ional biology conce ned
wi h he econs uc ion o e olu iona y ela ionships be ween o ganisms, genes,
and gene amilies. Maximum likelihood e alua ion has p o en o be one o he
mos eliable me hods o cons uc ing phylogene ic ees. The huge compu a-
ional equi emen s associa ed wi h maximum likelihood analysis means ha i is
no easible o p oduce la ge phylogene ic ees using a single p ocesso . We ha e
comple ed a ully c oss pla o m coa se g ained dis ibu ed applica ion, DPRml,
which o e comes many o he limi a ions imposed by he cu en se o pa allel
phylogene ic p og ams. We ha e comple ed a se o e iciency es s ha show how
o maximise e iciency while using he p og am o build la ge phylogene ic ees.
The so wa e is publicly a ailable unde he e ms o he GNU gene al public li-
cence om he sys em webpage a h p://www.cs.nuim.ie/dis ibu ed
1 In oduc ion
Phylogene ic analysis is a b anch o molecula biology ha is conce ned wi h he
econs uc ion o e olu iona y ela ionships be ween o ganisms, genes, and gene
amilies. The knowledge gained om he cons uc ion o accu a e phylogenies
can be c ucial in unde s anding such hings as he o igins o biochemical pa h-
ways, egula o y mechanisms in cells as well as he de elopmen o complex sys-
ems. Gi en a se o axa (molecula sequences usually comp ising o genes o
gene p oduc s) and a DNA subs i u ion model, he ask is o ind he phyloge-
ne ic ee ha mos accu a ely desc ibes he e olu iona y ela ionships be ween
he axa. Howe e he decision p oblem associa ed wi h sea ching o he bes ee
om a gi en se o axa is NP-comple e [1]. Many au ho s ha e p oposed g eedy
Co espondence o: [email p o ec ed]
2 Keane, T.M. e al.
heu is ic solu ions in an a emp o educe he e ec i e sea ch space [2–7]. These
algo i hms ha e made he p ocess o p oducing la ge phylogene ic ees possible
using only a single p ocesso . Howe e hese g eedy heu is ic algo i hms o en
only ake he bes immedia e, o local, solu ion esul ing in a inal ee ha is a
om op imal. The s epwise inse ion app oach combined wi h maximum likeli-
hood (ML) e alua ion has p o ed o be especially accu a e o building molecula
phylogenies. Felsens ein was he i s o b ing his amewo k o nucleo ide-based
phylogene ic in e ence [8]. Nume ous compu e s udies [9–13] ha e shown ML
p og ams can eco e he co ec ee om simula ed da a se s mo e equen ly
han o he me hods. In a ecen s udy iming he e olu ion o he HIV-1 i us [14],
i was demons a ed ha ML echniques can be e ec i e in sol ing impo an bio-
logical p oblems. The single ac o ha is cu en ly limi ing he widesp ead use o
ML echniques is he compu a ional equi emen s [15]. The huge compu a ional
equi emen s associa ed wi h ML analysis means ha i is no easible o p oduce
phylogene ic ees o any mo e han a small numbe o axa using a single p oces-
so .
A numbe o specialised pa allel ML phylogene ic p og ams ha e been de el-
oped o add ess his issue [16–18]. These p og ams ha e been e y success ul in
speeding up he p ocess o cons uc ing la ge phylogene ic ees using ML. How-
e e he o e iding limi a ion associa ed wi h each o hese p og ams is he spe-
cialised ha dwa e and so wa e is o en equi ed o un hese p og ams. Fo mos
esea che s, his can make hese p og ams ei he p ohibi i ely expensi e o simply
oo complica ed o se -up. Fu he mo e hese p og ams a e o en implemen ed in
a pla o m dependen language which imposes a es ic i e limi on he numbe s
and ypes o machines ha can be used in a pa allel compu a ion. I should also be
no ed ha some o hese ea lie pa allel p og ams only allowed he use o choose
om a e y limi ed numbe o DNA subs i u ion models, which o en leads o a
poo model i esul ing in sub-op imal ees. The e o e, in ou opinion, he h ee
mos essen ial equi emen s o any gene ally usable pa allel ee building p og am
mus be: ha he p og am should no equi e any so o specialised o expensi e
pa allel ha dwa e, should only equi e he mos basic echnical abili ies o se -up
and use, and should allow he use o choose om an ex ensi e lis o molecula
e olu ion models. Cu en ly he e is no pa allel phylogene ic ee building p og am
ha ul ills all o hese equi emen s.
We ha e de eloped a ully c oss pla o m dis ibu ed applica ion, called Dis-
ibu ed Phylogeny Recons uc ion by Maximum Likelihood (DPRml), which we
belie e o be one o he mos gene al, while powe ul, likelihood-based phyloge-
ne ic ee building p og ams cu en ly a ailable. I sa is ies each o he h ee e-
qui emen s ou lined abo e. The gene ali y o ou p og am is demons a ed by he
ac ha DPRml, w i en in Ja a, can un on i ually any a chi ec u e and ope a -
ing sys em simul aneously while only using he spa e clock cycles o dono ma-
chines. No specialised compu e ha dwa e is equi ed, and no expense is incu ed
i idle compu ing esou ces a e ha nessed. This would no be as s aigh o wa d
o a dis ibu ed applica ion w i en in a na i e language because he applica ion
would ha e o be compiled o each pa icula a chi ec u e and ope a ing sys em.
We ha e demons a ed he ease o use and pla o m he e ogenei y o DPRml wi h
Building la ge phylogene ic ees on coa se-g ained pa allel machines 3
expe imen s ha u ilise he spa e compu ing esou ces o se e al di e en a chi-
ec u es and ope a ing sys ems simul aneously. The use has a e y s aigh o wa d
con igu a ion ile wi h which o ailo he compu a ion and can choose om one
o he mos ex ensi e anges o DNA subs i u ion models cu en ly a ailable. Ou
e iciency analysis shows how a use how o make he mos e iciency use o hei
spa e clock cycles o build la ge phylogene ic ees. DPRml implemen s an al eady
p o en ee building algo i hm [16,19] and uses he popula Phylogene ic Analy-
sis Lib a y (PAL) 1.4 [20] o all i s likelihood calcula ions. A mo e de ailed
desc ip ion o he bioin o ma ics elemen o DPRml is a ailable in [21].
The es o he pape is o ganized as ollows. In Sec ion 2 we in oduce he
DPRml algo i hm in de ail. Sec ion 3 desc ibes he Ja a dis ibu ed compu ing
pla o m used by DPRml. The esul s o ou expe imen al e alua ion a e p esen ed
in Sec ion 4 and we conclude in Sec ion 5.
2 Coa se G ained Algo i hm
One o he i s p og ams o use ML echniques o build phylogene ic ees was
DNAml [8]. This was imp o ed and ex ended in he popula phylogene ic p og am
as DNAml [19]. A pa allel e sion o his p og am was ecen ly comple ed [16].
We ha e aken he ee building algo i hm used by pa allel as DNAml and ha e
implemen ed a pla o m independen , dis ibu ed, and much mo e gene alised e -
sion o he p og am. Ou dis ibu ed algo i hm is clien -se e based (see Sec-
ion 3 o mo e de ails o he dis ibu ed sys em design) and ope a es in a numbe
o s ages jus like pa allel as DNAml. A e e y s age a numbe o new ees a e
gene a ed and sen o dono machines o ha e hei b anch leng hs op imised (op-
ional) and likelihood calcula ed. The DPRml dis ibu ed algo i hm is desc ibed in
Figu e 1.
The pa ame e s mand a e con ained in he pa ame e ile. S ep 1 o he algo-
i hm is a localised e sion o he o e all algo i hm ou lined in s eps 2-7. A single
dono machine builds an ini ial ee o mminu es (de aul alue is 30 minu es)
and e u ns his ee o he se e . The size o he ee buil by his ini ial s ep de-
pends on se e al ac o s such as he complexi y o he subs i u ion model, di e si y
o he sequences, he numbe o posi ions pe sequence, and he CPU speed o he
dono machine. Due o he ne wo k o e head, i is mo e e icien o build his ini ial
ee on a single dono machine han o dis ibu e his pa o he compu a ion. The
inpu s o he applica ion a e a MODELTEST [22] ou pu ile, a FASTA sequence
ile (DNA o RNA), and an inpu pa ame e ile. MODELTEST is a popula appli-
ca ion among molecula biologis s ha uses hie a chical hypo hesis es ing o ind
he DNA subs i u ion model ha mos accu a ely i s a gi en da ase .
The ou pu s o he p og am a e a New Hampshi e o ma ee ile, a PAL ee
objec ile, a human eadable ee ( ex ile), and he likelihood o he inal ee. We
ha e p o ided a emo e in e ace o he sys em ha makes i possible o moni o
he p og ess o he applica ion in eal- ime as i builds he phylogene ic ee. The
inpu pa ame e ile le s he use se a ious un- ime op ions o he compu a ion
such as he maximum numbe o e ices ha ea angemen s can span, whe he o
4 Keane, T.M. e al.
p ocedu e DPRml( MODELTEST ile, FASTA DNA o RNA ile,
pa ame e ile )
1. Cons uc an ini ial ee o mminu es on a single dono
machine
2. Take he cu en bes ee and add ano he axon o e e y
opologically dis inc place o he cu en bes ee
(gene a ing 2i−5 ees, o i h axon being added o he
ee - see Sec ion 2.1)
3. Send each o he gene a ed ees o dono machines
o ha e hei b anch leng hs op imised (op ional) and
likelihoods calcula ed
4. Take he bes ee om s ep 3 and pe o m local
ea angemen s c ossing up o e ices (see
Sec ion 2.2)
5. Send each o he gene a ed ees o dono machines
o ha e hei b anch leng hs op imised (op ional) and
likelihoods calcula ed
6. I he bes ee om s ep 5 has a g ea e likelihood
han he bes ee om s ep 3, hen ea ange again
and send each o he gene a ed ees o dono machines
o ha e hei b anch leng hs op imised (op ional) and
likelihoods calcula ed. Repea his s ep un il he e is
no imp o emen in he likelihood o he bes ee
7. I he e a e mo e axa le o add o he ee hen go o
s ep 2, else go o s ep 8
8. I he use chose no o op imise b anch leng hs
h oughou he compu a ion hen send he bes ee o a
dono machine o ha e i s b anch leng hs op imised, else
go o s ep 9
9. Ou pu he bes ee
end p ocedu e
Fig. 1 A pseudocode desc ip ion o he DPRml algo i hm
keep a copy o he bes ee om e e y s age o jus he bes ee om he p e ious
s age, whe he o no o add he axa in a andomly gene a ed o de , and whe he o
op imise he b anch leng hs o e e y ee ha is gene a ed o jus op imise he inal
ee. The inpu ile also gi es he use he op ion o con inue building a pa ially
comple e ee. Log iles included wi h each se o esul s make i possible o ully
examine and ack he en i e ee building p ocess.
2.1 Subs i u ion Models
P obabilis ic models o nucleo ide subs i u ion a e cen al o he accu a e econ-
s uc ion o complex e olu iona y ela ionships [23]. These models a e used in
phylogene ic analysis o desc ibe changes in cha ac e s a e, i.e., he a e o change
om one nucleo ide o ano he . The e olu iona y p ocess is modeled as an e olu-
iona y Ma ko p ocess [24], also known as a subs i u ion model. Ma ko models
Building la ge phylogene ic ees on coa se-g ained pa allel machines 5
assume ha he e is no “memo y” in he sys em, he e o e only he ins an aneous
s a e o a cha ac e is impo an . The p obabili y o change om s a e i o s a e j
depends upon he amoun o ime ha has passed and he subs i u ion a e. Well
de e mined ime poin s a e no usually a ailable o molecula da a so he p od-
uc o a e and ime (equi alen o a gene ic dis ance) is mo e commonly used.
C i ical o models o nucleo ide e olu ion is he ealiza ion ha because he e a e
only ou possible cha ac e s a es, i is expec ed ha as gene ic dis ance inc eases,
some si es will unde go mul iple supe imposed subs i u ions. Simple measu es o
dis ance ha do no ake mul iple subs i u ions in o accoun a e said o be unco -
ec ed.Co ec ed dis ances use one o se e al models o sequence e olu ion o
es ima e he numbe o si es ha ha e unde gone mul iple subs i u ions.
A ew o he mos popula DNA subs i u ion models cu en ly in use a e (lis ed
in ascending complexi y) JC69 [25], Kimu a-2-Pa ame e model [26], HKY85
[27], TN93 [28], and he Gene al Time Re e sible model [29]. All o he mod-
els men ioned assume ha each posi ion is e ol ing independen ly and iden ically.
Howe e his is a ely he case, he e o e each o he models abo e can inco po a e
a si e o si e a e a ia ion also. Two o he mos popula a e a ia ion models a e
he In a iable si es model [30] and he Gamma dis ibu ion model [31]. One o he
common limi a ions o he cu en se o pa allel phylogene ic ee building p o-
g ams is ha hey only suppo a e y limi ed numbe o subs i u ion models and
e y ew suppo si e o si e a e a ia ion. As men ioned abo e, MODELTEST
es s one o he mos ex ensi e lib a ies o DNA subs i u ion models (including
si e o si e a e a ia ion) agains a da ase in o de o ind he mos sui able sub-
s i u ion model. DPRml suppo s all o he subs i u ion models ha MODELTEST
3.06 p o ides.
2.2 Add Taxon S age
The ee building algo i hm desc ibed abo e is based on a s epwise inse ion ap-
p oach o adding new axa o he phylogene ic ee. Ini ially he algo i hm s a s
by cons uc ing an un oo ed bi u ca ing ee wi h h ee axa (only one opology is
possible - see Figu e 2). A new axon is hen added o e e y opologically dis inc
place o his ini ial ee. In he gene al case, his p ocess p oduces 2i−5 ees,
o he i h axon being added o he ee. All o he ees p oduced a e hen e al-
ua ed using maximum likelihood. The maximum likelihood me hod compu es he
likelihood o ob aining he obse ed sequence wi h a gi en ee opology, assigned
b anch leng hs, and a gi en e olu iona y model. Since he likelihood is ypically a
e y small alue, he ee wi h he g ea es log likelihood is kep .
2.3 Rea ange T ee S age
An impo an pa o he algo i hm is he in e nal ea angemen s ha a e made
o he bes (mos likely) ee du ing each i e a ion o he algo i hm. By epea -
edly ea anging he bes ee un il he e is no imp o emen in he likelihood, he
ho oughness o he sea ch o he o e all ee space is g ea ly inc eased. This is

6 Keane, T.M. e al.
Fig. 2 Adding a ou h axon o a 3 axa ee p oduces 3 new ees.
Fig. 3 Rea angemen spanning one in e nal b anch.
done by mo ing each sub ee ac oss one o mo e in e nal b anches o he ee. The
use speci ies he maximum numbe o in e nal b anches ha ea angemen s can
span. Figu e 3 is an example o a ea angemen spanning one in e nal b anch o
he ee. A highe numbe o in e nal b anches being spanned by ea angemen s
will esul in mo e ees being gene a ed and will inc ease he o e all unning ime
o he p og am. Howe e a lowe numbe will esul in a lesse p opo ion o he
ee space being sea ched and will inc ease he chance o a sub-op imal ee being
p oduced.
Building la ge phylogene ic ees on coa se-g ained pa allel machines 7
2.4 Algo i hm Sui abili y o Dis ibu ed Compu ing
Ou ini ial wo k on his applica ion in ol ed pe o ming an in es iga ion on how
sui able ML based phylogene ic ee building is o dis ibu ed compu ing. We de-
cided on wo main c i e ia ha any p oblem had o i in o de o be sui able o
a dis ibu ed implemen a ion. Fi s ly he p oblem had o i he class o “coa se
g ained” pa allel p oblems. As can be seen om he algo i hm abo e, each s age
o he compu a ion p oduces a se o ees ha mus ha e hei b anch leng hs and
likelihood calcula ed. These asks can be done comple ely independen ly on di -
e en si es o e e y ee wi hou in e ac ion equi ed be ween any wo likelihood
compu a ions.
The second c i e ion o e alua ing he sui abili y o phylogene ic analysis o
dis ibu ed compu ing was ha he p oblem mus display a high “compu e- o-da a”
a io o make i wo hwhile sending he da a o e a ne wo k a he han compu ing
locally. In ou e iciency analysis (see Sec ion 4) he da ase ha we used consis ed
o 101 axa and was less han 200 KB in size. The small size o he da a iles in-
ol ed coupled wi h he long compu a ion imes o ML analysis make his p oblem
ideal o dis ibu ed compu ing.
3 Implemen a ion
DPRml is jus one o a numbe o applica ions [21,32] ha uns on ou gene al
pu pose dis ibu ed compu ing pla o m. Ou dis ibu ed compu ing pla o m is
loosely based on he design o he Ja a Dis ibu ed Compu ing Lib a y (JDCL) [33,
34] bu o e s much g ea e unc ionali y, lexibili y, and usabili y. The o e all de-
sign o he sys em is based on he clien -se e model [35]. This model desc ibes
a sys em consis ing o a single se e compu e and a numbe o clien compu e s.
The clien s can connec o e a ne wo k o he se e . The se e con ols a esou ce
(such as a da abase, algo i hm, o compu e ha dwa e) and he clien s ini ia e e-
ques s o he se e o access o he esou ce. Ou sys em is di ided in o h ee
sepa a e pieces o so wa e: se e , clien , and emo e in e ace. An o e iew o
he sys em is illus a ed in Figu e 4. The se e s o es he p oblem ( o example,
molecula da a and an algo i hm o p ocess i ) and b eaks he p oblem down in o
smalle p oblems, called da a uni s. The clien so wa e is ins alled on each dono
machine and i connec s o he se e o e he In e ne . A clien eques s a da a
uni , pe o ms he p ocessing, e u ns he esul o he se e , and eques s ano he
da a uni . Mul iple clien s can make such eques s o he se e . The se e colla es
he esul s o he da a uni s om he clien s and cons uc s he esul o he la ge ,
o iginal, p oblem. The emo e in e ace is used o access all unc ionali y on he
se e such as adding and emo ing p oblems, downloading esul iles, moni o -
ing p og ess o compu a ions, changing he p io i y o p oblems in he sys em, and
iewing se e s a is ics. He e a e a ew o he no el ea u es o ou sys em:
–Po abili y: The en i e sys em is comple ely ne wo k and pla o m independen
–Scalabili y: New clien s can be added and emo ed om he sys em dynami-
cally
8 Keane, T.M. e al.
Fig. 4 Diag am o comple e sys em. Al hough all communica ion is bi-di ec ional, he a -
ows indica e he di ec ion o ini ia ion o communica ion.
–Expandabili y: The se e has he abili y o un se e al di e en dis ibu ed
compu a ions simul aneously
–Longe i y: Remo e upda ing o clien so wa e is suppo ed
–Real Time Upda es: Remo e eal- ime p oblem p og ess upda es a e a ailable
o use s
–Secu e: The secu i y o he se e and dono machines om sub e si e dis-
ibu ed applica ions is gua an eed
–He e ogeneous: An adap i e scheduling algo i hm dynamically ma ches he
dono machines wi h wo k uni s ha ma ch hei compu a ional capaci y
–Remo e Con ol: Comple e con ol o all se e unc ionali y is possible e-
mo ely o e he In e ne
–Dynamic Job P io i ies: P io i y o jobs can be changed dynamically o allow
p oblems be alloca ed g ea e o lesse ac ions o he o e all a ailable p o-
cessing powe
–Ease o se -up: The en i e sys em comp ises o only h ee execu able Ja a JAR
iles
–Modula design: New scheduling algo i hms can be implemen ed wi hou any
changes equi ed o he es o he sys em o exis ing dis ibu ed applica ions
Building la ge phylogene ic ees on coa se-g ained pa allel machines 9
The se e , clien , and emo e in e ace consis o single execu able Ja a JAR
iles ha can be un om he command line. The e a e a ew di e en ways ha
he clien so wa e can be deployed. To maximise he usage o ou semi-idle desk-
op PC’s, we choose o un he clien as a low p io i y backg ound se ice. This
means ha e en i he e is nobody logged on a a dono machine, he clien so -
wa e can un in he backg ound 24 hou s a day using he spa e clock cycles. In
ou deploymen o he sys em, we ha e ou clien so wa e unning on 180 desk-
op PC’s ( a ious ha dwa e speci ica ions om Pen ium II’s up o Pen ium IV’s)
unning mul iple ope a ing sys ems (Windows 98/NT/2000/XP, Linux - Gen oo,
Debian, Fedo a). To illus a e he po abili y o ou sys em, we ha e also ins alled
ou clien on e e y node o an IBM Linux clus e (32 Dual P4 1 GHz nodes wi h
512 MB memo y pe node) wi h he desk ops and clus e nodes connec ing o a
single se e . We consis en ly pe o m app oxima ely 3 Pen ium yea s o p ocess-
ing each week.
3.1 Dis ibu ed P og amming Model
As pa o ou gene al pu pose dis ibu ed pla o m, we ha e designed a gene al
pu pose p og amming in e ace ha allows a use o dis ibu e a bi a y com-
pu a ions among a se o dono machines. To se -up a dis ibu ed compu a ion,
wo Ja a classes mus be ex ended. These a e he Algo i hm class and he
Da aManage class. Each o hese pa en classes a e pa o he sys em. The
de elope mus o e w i e and implemen ce ain me hods in o de o se -up a dis-
ibu ed compu a ion [36].
To implemen he phylogene ic ee building algo i hm, we pa i ioned he al-
go i hm ou lined in Sec ion 2 in o wo se s o unc ionali y, code ha uns on he
se e and code ha uns on he clien s. The Algo i hm class, which uns on he
dono machines, con ains ou sepa a e me hods. The i s me hod builds an ini ial
ee o mminu es using a localised e sion o he o e all ee building algo i hm
(de aul alue o mis 30 minu es). The second me hod akes a se o ees and a
subs i u ion model, op imises he b anch leng hs o each ee (op ional), compu es
he likelihood o each phylogene ic ee, and e u ns he ee wi h he g ea es like-
lihood o he se e . The hi d me hod akes he inal ee and op imises he b anch
leng hs o his ee. This me hod is only execu ed when he use chooses no o
op imise he b anch leng hs o e e y ee h oughou he compu a ion. The las
me hod akes a ee and pe o ms in e nal ea angemen s on he ee c ossing up
o a speci ied numbe o b anches, hus p oducing a numbe o new ees. Pa-
ame e s a e sen wi h each da a uni o iden i y which me hod o execu e on he
downloaded da a.
The Da aManage uns on he se e and manages he o e all compu a-
ion. The Cons uc o me hod eads in, pa ses, checks he alidi y o he
inpu s o he p og am, and sends he da a o one dono machine o c ea e he
ini ial ee. We di ided he ee building algo i hm up in o di e en s ages. The
gene a eDa aUni () me hod simply makes a call o he cu en s age objec
and eques s a da a uni o a dono machine o p ocess. I he e a e no mo e ees o
16 Keane, T.M. e al.
This esul i s well wi h he expec ed usage o he p og am. As he algo i hm
ou lined in Sec ion 2 is s ochas ic, i is possible o become apped in a local op-
imum, a he han a global one. Typically a biologis would epea he en i e ee
building p ocess wi h se e al di e en andomiza ions o he o de o axa and hen
compa e he bes o he esul ing ees o de e mine a consensus ee [37].
5 Conclusion
Due o he ecen explosion in he size o sequence da abases, he e is inc eased
in e es in p oducing e y la ge and accu a e phylogene ic ees using maximum
likelihood. Fo a la ge numbe o axa, i is no possible o pe o m an exhaus i e
sea ch o he ee space. Many au ho s ha e p oposed heu is ic algo i hms aimed
a speeding up he p ocess o cons uc ing phylogene ic ees. Howe e many o
hese algo i hms do no pe o m a su icien ly igo ous sea ch o he ee space
and o en esul in sub-op imal ees. The e o e a numbe o esea che s ha e de-
eloped specialised pa allel p og ams in an a emp o pe o m a mo e comple e
sea ch o he ee space and hus p oduce mo e accu a e phylogene ic ees. We
ha e exp essed a numbe o limi a ions o hese pa allel p og ams ha a e cu -
en ly se e ely limi ing he widesp ead use o pa allel compu ing in phylogene ic
analysis.
Dis ibu ed compu ing o e s inexpensi e access o la ge amoun s o compu -
ing powe . We ha e iden i ied he sui abili y o phylogene ic ee cons uc ion o
coa se g ained dis ibu ed compu ing. We ha e comple ed a dis ibu ed and ully
c oss pla o m phylogene ic ee building p og am called DPRml. DPRml uses an
al eady p o en ee building algo i hm and popula phylogene ic analysis lib a y.
The usabili y and gene ali y o ou p og am is demons a ed by he ease o use
and pla o m he e ogenei y o DPRml. The use can choose om one o he mos
ex ensi e anges o DNA subs i u ion models cu en ly a ailable. We ha e shown
how DPRml can be used o make he mos e icien use o a ailable spa e clock
cycles o build la ge phylogene ic ees. The inal ou pu s o he p og am a e in
s anda d o ma s ha allow he use o pe o m u he manipula ion and analysis
o esul s using o he phylogene ic packages.
This is he i s elease o DPRml and we ha e iden i ied a numbe o a eas
ha wa an u he esea ch and de elopmen . We would like o in es iga e possi-
ble ways o u he imp o ing speedup. Fo example, Ce on has de ised a scheme
whe eby he lis o ees o be issued is calcula ed in ad ance [38], hus educing
he limi ing in luence o he synch onisa ion ba ie . As new ea u es and algo i h-
mic imp o emen s appea in la e e sions o PAL [39], we will elease upda ed
e sions o DPRml on ou webpage o ake ad an age o he imp o emen s. Fi-
nally we would like o ex end DPRml o cons uc a numbe o ees using a single
da ase and hen ou pu he o e all consensus ee [37]. DPRml is eely a ailable
unde he e ms o he GNU Gene al Public Licence. The e is also a use manual
a ailable o download om he sys em webpage.

Building la ge phylogene ic ees on coa se-g ained pa allel machines 17
Acknowledgemen s This esea ch has been unded by Emba k Ini ia i e om he I ish
Resea ch Council o Science, Enginee ing and Technology: unded by he Na ional De el-
opmen Plan. We would also like o hank Ma hew Goode o he PAL p ojec o help and
ad ice on how o use PAL 1.4.
Re e ences
1. H. Bodlaende , M. Fellows, and T. Wa now. Two s ikes agains pe ec phylogeny,
olume 623, pages 273–283. Sp inge -Ve lag, NY, USA, 1992.
2. K. S imme and A. on Haesele . Qua e Puzzling: A Qua e Maximum-Likelihood
Me hod o Recons uc ing T ee Topologies. Molecula Biology and E olu ion,
13(7):964–969, 1996.
3. J. Adachi and M. Hasegawa. MOLPHY e sion 2.3 p og ams o molecula phylo-
gene ics based on maximum likelihood. Compu e Science Monog aphs, 28:1–150,
1996.
4. J.P. Huelsenbeck and F. Ronquis . MRBAYES: Bayesian in e ence o phylogene ic
ees. Bioin o ma ics, 17(8):754–755, 2001.
5. P.O. Lewis. A gene ic algo i hm o maximum-likelihood phylogeny in e ence using
nucleo ide sequence da a. Molecula Biology and E olu ion, 15(3):277–283, 1998.
6. L.A. Sal e and D.K. Pea l. S ochas ic sea ch s a egy o es ima ion o maximum
likelihood phylogene ic ees. Sys ema ic Biology, 50(1):7–17, 2001.
7. B.M.E. Mo e , S. Wyman, D.A. Bade , T. Wa now, and M. Yan. A new implemen a ion
and de ailed s udy o b eakpoin analysis. In P oceedings o he 6 h Paci ic Symposium
on Biocompu ing, pages 583–594, Hawaii, 2001. Wo ld Scien i ic Publica ions.
8. J. Felsens ein. E olu iona y ees om DNA sequences: A maximum likelihood ap-
p oach. Jou nal o Molecula E olu ion, 17:368–376, 1981.
9. J.P. Huelsenbeck and D.M. Hillis. Success o phylogene ic me hods in he ou - axon
case. Sys ema ic Biology, 42:247–264, 1993.
10. M.K. Kuhne and J. Felsens ein. A simula ion compa ison o phylogeny algo i hms
unde equal and unequal e olu iona y a es [published e a um appea s in Molecu-
la Biology and E olu ion 1995 May;12(3):525]. Molecula Biology and E olu ion,
11(3):459–468, 1994.
11. J.P. Huelsenbeck. Pe o mance o phylogene ic me hods in simula ion. Sys ema ic
Biology, 44:17–48, 1995.
12. M.S. Rosenbe g and S. Kuma . T adi ional Phylogene ic Recons uc ion Me hods Re-
cons uc Shallow and Deep E olu iona y Rela ionships Equally Well. Molecula Bi-
ology and E olu ion, 18(9):1823–1827, 2001.
13. V. Ranwez and O. Gascuel. Imp o emen o Dis ance-Based Phylogene ic Me hods
by a Local Maximum Likelihood App oach Using T iple s. Molecula Biology and
E olu ion, 19(11):1952–1963, 2002.
14. B. Ko be , M. Muldoon, J. Theile , F. Gao, R. Gup a, A. Lapedes, B.H. Hahn, S. Wolin-
sky, and T. Bha acha ya. Timing he ances o o he HIV-1 pandemic s ains. Science,
288:1789–1796, 2000.
15. M.A. He shko i z and D.D. Leipe. Phylogene ic analysis. In A.D. Baxe anis and
B.F.F. Ouele e, edi o s, Bioin o ma ics: a p ac ical guide o he analysis o genes and
p o eins, pages 189–230. Wiley-Liss, New Yo k, USA, 1998.
16. C.A. S ewa , D. Ha , D.K. Be y, G.J. Olsen, E.A. We ne , and W. Fische . Pa allel
implemen a ion and pe o mance o as DNAml: a p og am o maximum likelihood
phylogene ic in e ence. In Supe compu ing ’01: P oceedings o he 2001 ACM/IEEE
con e ence on Supe compu ing, page 20, New Yo k, NY, USA, 2001. ACM P ess.
18 Keane, T.M. e al.
17. A.P. S ama akis and T. Ludwig. Phylogene ic T ee In e ence on PC A chi ec u es wi h
AxML/PAxML. In P oceedings o IPDPS2003 (High Pe o mance Compu a ional Bi-
ology wo kshop), Nice, F ance, 2003.
18. H.A. Schmid , K. S imme , M. Ving on, and A. on Haesele . TREE-PUZZLE: max-
imum likelihood phylogene ic analysis using qua e s and pa allel compu ing. Bioin-
o ma ics, 18(3):502–504, 2002.
19. G.J. Olsen, H. Ma suda, R. Hags om, and R. O e beek. Fas DNAml: A ool o con-
s uc ion o phylogene ic ees o DNA sequences using maximum likelihood. Com-
pu e Applica ions in he Biosciences, 10:41–48, 1994.
20. A. D ummond and K. S imme . PAL: An objec -o ien ed p og amming lib a y o
molecula e olu ion and phylogene ics. Bioin o ma ics, 17:662–663, 2001.
21. T.M. Keane, T.J. Naugh on, S.A.A. T a e s, J.O. McIne ney, and G.P. McCo mack.
DPRml: dis ibu ed phylogeny econs uc ion by maximum likelihood. Bioin o ma ics,
21(7):969–974, 2005.
22. D. Posada and K.A. C andall. MODELTEST: es ing he model o DNA subs i u ion.
Bioin o ma ics, 14(9):817–818, 1998.
23. J. Felsens ein. Models o DNA E olu ion. In In e ing Phylogenies, pages 196–221.
Sinaue Associa es, Sunde land, MA, 2004.
24. T. Mulle and M. Ving on. Modelling amino acid eplacemen . Jou nal o Compu a-
ional Biology, 7:761–776, 2000.
25. T.H. Jukes and C.R. Can o . E olu ion o p o ein molecules. In Mun o, edi o , Mam-
milian P o ein Me abolism, pages 240–252. Academic P ess, New Yo k, USA, 1969.
26. M. Kimu a. A simple me hod o es ima ing e olu iona y a e o base subs i u ions
h ough compa a i e s udies o nucleo ide sequences. Jou nal o Molecula E olu ion,
16:111–120, 1980.
27. M. Hasegawa, H. Kishino, and T. Yano. Da ing he human-age spli ing by a molecula
clock o mi ochond ial DNA. Jou nal o Molecula E olu ion, 22:160–174, 1985.
28. K. Tamu a and M. Nei. Es ima ion o he numbe o nucleo ide subs i u ions in he
con ol egion o mi ochond ial DNA in humans and chimpanzees. Molecula Biology
and E olu ion, 10:512–526, 1993.
29. F.J. Rod iguez, J.L. Oli e , A. Ma in, and J.R. Medina. The gene al s ochas ic model
o nucleo ide subs i u ion. Jou nal o Theo e ical Biology, 142:485–501, 1990.
30. M. S eel, D. Hudson, and P.J. Lockha . In a iable si es models and hei use in phy-
logeny econs uc ion. Sys ema ic Biology, 49:225–232, 2000.
31. Z. Yang. The among-si e a e a ia ion and i s impac on phylogene ic analyses. T ends
in Ecology and E olu ion, 11:367–372, 1996.
32. T.M. Keane and T.J. Naugh on. DSEARCH: sensi i e da abase sea ching using dis-
ibu ed compu ing. Bioin o ma ics, 21(8):1705–1706, 2005.
33. K. F i sche, J. Powe , and J. Wald on. A Ja a dis ibu ed compu a ion lib a y. In P o-
ceedings o he 2nd In e na ional Con e ence on Pa allel and Dis ibu ed Compu ing
Applica ions and Technologies, pages 236–243, Taipei, Taiwan, July 2001.
34. T. Keane, R. Allen, T. J. Naugh on, J. McIne ney, and J. Wald on. Dis ibu ed Ja a pla -
o m wi h p og ammable MIMD capabili ies. In N. Guel i, E. As esiano, and G. Reg-
gio, edi o s, Scien i ic Enginee ing o Dis ibu ed Ja a Applica ions, olume 2604,
pages 122–131, Be lin, Feb ua y 2003. Sp inge Lec u e No es in Compu e Science.
35. H. Edels ein. Un a eling clien /se e a chi ec u e. DBMS, 7(5):34–41, May 1994.
36. T. Keane. Ja a dis ibu ed sys em: De elope manual. Technical Repo NUIM-CS
TR-2003-03, Dep . o Compu e Science, Na ional Uni e si y o I eland, Maynoo h,
I eland, 2003.
37. L.S. Je miin, G.J. Olsen, and S. Eas eal. Majo i y ule consensus o maximum likeli-
hood ees. Molecula Biology and E olu ion, 14:1296–1302, 1997.
Building la ge phylogene ic ees on coa se-g ained pa allel machines 19
38. C. Ce on, J. Dopazo, E.L. Zapa a, J.M. Ca azo, and T elles O. Pa allel implemen a ion
o DNAml p og am on message-passing a chi ec u es. Pa allel Compu ing, 24:701–
716, 1998.
39. M. Goode, K. S imme , A. D ummond, E. Buckle , and A. Rod igo. A b ie in oduc-
ion o he Phylogene ic Analysis Lib a y e sion 1.5. In CRPIT ’29: P oceedings o
he second con e ence on Asia-Paci ic bioin o ma ics, pages 175–179, Dunedin, New
Zealand, 2004. Aus alian Compu e Socie y, Inc.