source: branches/items/GDE/AxML/axml.ps

%!PS-Adobe-2.0
%%Creator: dvips(k) 5.86 Copyright 1999 Radical Eye Software
%%Title: latex8.dvi
%%Pages: 8
%%PageOrder: Ascend
%%BoundingBox: 0 0 612 792
%%DocumentFonts: Times-Bold Times-Roman Times-Italic Helvetica-Bold
%%+ Courier Helvetica
%%EndComments
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips -t letter -o latex8.ps latex8.dvi
%DVIPSParameters: dpi=600, compressed
%DVIPSSource:  TeX output 2002.06.13:1035
%%BeginProcSet: texc.pro
%!
/TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S
N}B/A{dup}B/TR{translate}N/isls false N/vsize 11 72 mul N/hsize 8.5 72
mul N/landplus90{false}def/@rigin{isls{[0 landplus90{1 -1}{-1 1}ifelse 0
0 0]concat}if 72 Resolution div 72 VResolution div neg scale isls{
landplus90{VResolution 72 div vsize mul 0 exch}{Resolution -72 div hsize
mul 0}ifelse TR}if Resolution VResolution vsize -72 div 1 add mul TR[
matrix currentmatrix{A A round sub abs 0.00001 lt{round}if}forall round
exch round exch]setmatrix}N/@landscape{/isls true N}B/@manualfeed{
statusdict/manualfeed true put}B/@copies{/#copies X}B/FMat[1 0 0 -1 0 0]
N/FBB[0 0 0 0]N/nn 0 N/IEn 0 N/ctr 0 N/df-tail{/nn 8 dict N nn begin
/FontType 3 N/FontMatrix fntrx N/FontBBox FBB N string/base X array
/BitMaps X/BuildChar{CharBuilder}N/Encoding IEn N end A{/foo setfont}2
array copy cvx N load 0 nn put/ctr 0 N[}B/sf 0 N/df{/sf 1 N/fntrx FMat N
df-tail}B/dfs{div/sf X/fntrx[sf 0 0 sf neg 0 0]N df-tail}B/E{pop nn A
definefont setfont}B/Cw{Cd A length 5 sub get}B/Ch{Cd A length 4 sub get
}B/Cx{128 Cd A length 3 sub get sub}B/Cy{Cd A length 2 sub get 127 sub}
B/Cdx{Cd A length 1 sub get}B/Ci{Cd A type/stringtype ne{ctr get/ctr ctr
1 add N}if}B/id 0 N/rw 0 N/rc 0 N/gp 0 N/cp 0 N/G 0 N/CharBuilder{save 3
1 roll S A/base get 2 index get S/BitMaps get S get/Cd X pop/ctr 0 N Cdx
0 Cx Cy Ch sub Cx Cw add Cy setcachedevice Cw Ch true[1 0 0 -1 -.1 Cx
sub Cy .1 sub]/id Ci N/rw Cw 7 add 8 idiv string N/rc 0 N/gp 0 N/cp 0 N{
rc 0 ne{rc 1 sub/rc X rw}{G}ifelse}imagemask restore}B/G{{id gp get/gp
gp 1 add N A 18 mod S 18 idiv pl S get exec}loop}B/adv{cp add/cp X}B
/chg{rw cp id gp 4 index getinterval putinterval A gp add/gp X adv}B/nd{
/cp 0 N rw exit}B/lsh{rw cp 2 copy get A 0 eq{pop 1}{A 255 eq{pop 254}{
A A add 255 and S 1 and or}ifelse}ifelse put 1 adv}B/rsh{rw cp 2 copy
get A 0 eq{pop 128}{A 255 eq{pop 127}{A 2 idiv S 128 and or}ifelse}
ifelse put 1 adv}B/clr{rw cp 2 index string putinterval adv}B/set{rw cp
fillstr 0 4 index getinterval putinterval adv}B/fillstr 18 string 0 1 17
{2 copy 255 put pop}for N/pl[{adv 1 chg}{adv 1 chg nd}{1 add chg}{1 add
chg nd}{adv lsh}{adv lsh nd}{adv rsh}{adv rsh nd}{1 add adv}{/rc X nd}{
1 add set}{1 add clr}{adv 2 chg}{adv 2 chg nd}{pop nd}]A{bind pop}
forall N/D{/cc X A type/stringtype ne{]}if nn/base get cc ctr put nn
/BitMaps get S ctr S sf 1 ne{A A length 1 sub A 2 index S get sf div put
}if put/ctr ctr 1 add N}B/I{cc 1 add D}B/bop{userdict/bop-hook known{
bop-hook}if/SI save N @rigin 0 0 moveto/V matrix currentmatrix A 1 get A
mul exch 0 get A mul add .99 lt{/QV}{/RV}ifelse load def pop pop}N/eop{
SI restore userdict/eop-hook known{eop-hook}if showpage}N/@start{
userdict/start-hook known{start-hook}if pop/VResolution X/Resolution X
1000 div/DVImag X/IEn 256 array N 2 string 0 1 255{IEn S A 360 add 36 4
index cvrs cvn put}for pop 65781.76 div/vsize X 65781.76 div/hsize X}N
/p{show}N/RMat[1 0 0 -1 0 0]N/BDot 260 string N/Rx 0 N/Ry 0 N/V{}B/RV/v{
/Ry X/Rx X V}B statusdict begin/product where{pop false[(Display)(NeXT)
(LaserWriter 16/600)]{A length product length le{A length product exch 0
exch getinterval eq{pop true exit}if}{pop}ifelse}forall}{false}ifelse
end{{gsave TR -.1 .1 TR 1 1 scale Rx Ry false RMat{BDot}imagemask
grestore}}{{gsave TR -.1 .1 TR Rx Ry scale 1 1 false RMat{BDot}
imagemask grestore}}ifelse B/QV{gsave newpath transform round exch round
exch itransform moveto Rx 0 rlineto 0 Ry neg rlineto Rx neg 0 rlineto
fill grestore}B/a{moveto}B/delta 0 N/tail{A/delta X 0 rmoveto}B/M{S p
delta add tail}B/b{S p tail}B/c{-4 M}B/d{-3 M}B/e{-2 M}B/f{-1 M}B/g{0 M}
B/h{1 M}B/i{2 M}B/j{3 M}B/k{4 M}B/w{0 rmoveto}B/l{p -4 w}B/m{p -3 w}B/n{
p -2 w}B/o{p -1 w}B/q{p 1 w}B/r{p 2 w}B/s{p 3 w}B/t{p 4 w}B/x{0 S
rmoveto}B/y{3 2 roll p a}B/bos{/SS save N}B/eos{SS restore}B end

%%EndProcSet
%%BeginProcSet: 8r.enc
% @@psencodingfile@{
%   author = "S. Rahtz, P. MacKay, Alan Jeffrey, B. Horn, K. Berry",
%   version = "0.6",
%   date = "1 July 1998",
%   filename = "8r.enc",
%   email = "tex-fonts@@tug.org",
%   docstring = "Encoding for TrueType or Type 1 fonts
%                to be used with TeX."
% @}
% 
% Idea is to have all the characters normally included in Type 1 fonts
% available for typesetting. This is effectively the characters in Adobe
% Standard Encoding + ISO Latin 1 + extra characters from Lucida.
% 
% Character code assignments were made as follows:
% 
% (1) the Windows ANSI characters are almost all in their Windows ANSI
% positions, because some Windows users cannot easily reencode the
% fonts, and it makes no difference on other systems. The only Windows
% ANSI characters not available are those that make no sense for
% typesetting -- rubout (127 decimal), nobreakspace (160), softhyphen
% (173). quotesingle and grave are moved just because it's such an
% irritation not having them in TeX positions.
% 
% (2) Remaining characters are assigned arbitrarily to the lower part
% of the range, avoiding 0, 10 and 13 in case we meet dumb software.
% 
% (3) Y&Y Lucida Bright includes some extra text characters; in the
% hopes that other PostScript fonts, perhaps created for public
% consumption, will include them, they are included starting at 0x12.
% 
% (4) Remaining positions left undefined are for use in (hopefully)
% upward-compatible revisions, if someday more characters are generally
% available.
% 
% (5) hyphen appears twice for compatibility with both 
% ASCII and Windows.
% 
/TeXBase1Encoding [
% 0x00 (encoded characters from Adobe Standard not in Windows 3.1)
  /.notdef /dotaccent /fi /fl
  /fraction /hungarumlaut /Lslash /lslash
  /ogonek /ring /.notdef
  /breve /minus /.notdef 
% These are the only two remaining unencoded characters, so may as
% well include them.
  /Zcaron /zcaron 
% 0x10
 /caron /dotlessi 
% (unusual TeX characters available in, e.g., Lucida Bright)
 /dotlessj /ff /ffi /ffl 
 /.notdef /.notdef /.notdef /.notdef
 /.notdef /.notdef /.notdef /.notdef
 % very contentious; it's so painful not having quoteleft and quoteright
 % at 96 and 145 that we move the things normally found there to here.
 /grave /quotesingle 
% 0x20 (ASCII begins)
 /space /exclam /quotedbl /numbersign
 /dollar /percent /ampersand /quoteright
 /parenleft /parenright /asterisk /plus /comma /hyphen /period /slash
% 0x30
 /zero /one /two /three /four /five /six /seven
 /eight /nine /colon /semicolon /less /equal /greater /question
% 0x40
 /at /A /B /C /D /E /F /G /H /I /J /K /L /M /N /O
% 0x50
 /P /Q /R /S /T /U /V /W
 /X /Y /Z /bracketleft /backslash /bracketright /asciicircum /underscore
% 0x60
 /quoteleft /a /b /c /d /e /f /g /h /i /j /k /l /m /n /o
% 0x70
 /p /q /r /s /t /u /v /w
 /x /y /z /braceleft /bar /braceright /asciitilde
 /.notdef % rubout; ASCII ends
% 0x80
 /.notdef /.notdef /quotesinglbase /florin
 /quotedblbase /ellipsis /dagger /daggerdbl
 /circumflex /perthousand /Scaron /guilsinglleft
 /OE /.notdef /.notdef /.notdef
% 0x90
 /.notdef /.notdef /.notdef /quotedblleft
 /quotedblright /bullet /endash /emdash
 /tilde /trademark /scaron /guilsinglright
 /oe /.notdef /.notdef /Ydieresis
% 0xA0
 /.notdef % nobreakspace
 /exclamdown /cent /sterling
 /currency /yen /brokenbar /section
 /dieresis /copyright /ordfeminine /guillemotleft
 /logicalnot
 /hyphen % Y&Y (also at 45); Windows' softhyphen
 /registered
 /macron
% 0xD0
 /degree /plusminus /twosuperior /threesuperior
 /acute /mu /paragraph /periodcentered
 /cedilla /onesuperior /ordmasculine /guillemotright
 /onequarter /onehalf /threequarters /questiondown
% 0xC0
 /Agrave /Aacute /Acircumflex /Atilde /Adieresis /Aring /AE /Ccedilla
 /Egrave /Eacute /Ecircumflex /Edieresis
 /Igrave /Iacute /Icircumflex /Idieresis
% 0xD0
 /Eth /Ntilde /Ograve /Oacute
 /Ocircumflex /Otilde /Odieresis /multiply
 /Oslash /Ugrave /Uacute /Ucircumflex
 /Udieresis /Yacute /Thorn /germandbls
% 0xE0
 /agrave /aacute /acircumflex /atilde
 /adieresis /aring /ae /ccedilla
 /egrave /eacute /ecircumflex /edieresis
 /igrave /iacute /icircumflex /idieresis
% 0xF0
 /eth /ntilde /ograve /oacute
 /ocircumflex /otilde /odieresis /divide
 /oslash /ugrave /uacute /ucircumflex
 /udieresis /yacute /thorn /ydieresis
] def

%%EndProcSet
%%BeginProcSet: texps.pro
%!
TeXDict begin/rf{findfont dup length 1 add dict begin{1 index/FID ne 2
index/UniqueID ne and{def}{pop pop}ifelse}forall[1 index 0 6 -1 roll
exec 0 exch 5 -1 roll VResolution Resolution div mul neg 0 0]/Metrics
exch def dict begin Encoding{exch dup type/integertype ne{pop pop 1 sub
dup 0 le{pop}{[}ifelse}{FontMatrix 0 get div Metrics 0 get div def}
ifelse}forall Metrics/Metrics currentdict end def[2 index currentdict
end definefont 3 -1 roll makefont/setfont cvx]cvx def}def/ObliqueSlant{
dup sin S cos div neg}B/SlantFont{4 index mul add}def/ExtendFont{3 -1
roll mul exch}def/ReEncodeFont{CharStrings rcheck{/Encoding false def
dup[exch{dup CharStrings exch known not{pop/.notdef/Encoding true def}
if}forall Encoding{]exch pop}{cleartomark}ifelse}if/Encoding exch def}
def end

%%EndProcSet
%%BeginProcSet: special.pro
%!
TeXDict begin/SDict 200 dict N SDict begin/@SpecialDefaults{/hs 612 N
/vs 792 N/ho 0 N/vo 0 N/hsc 1 N/vsc 1 N/ang 0 N/CLIP 0 N/rwiSeen false N
/rhiSeen false N/letter{}N/note{}N/a4{}N/legal{}N}B/@scaleunit 100 N
/@hscale{@scaleunit div/hsc X}B/@vscale{@scaleunit div/vsc X}B/@hsize{
/hs X/CLIP 1 N}B/@vsize{/vs X/CLIP 1 N}B/@clip{/CLIP 2 N}B/@hoffset{/ho
X}B/@voffset{/vo X}B/@angle{/ang X}B/@rwi{10 div/rwi X/rwiSeen true N}B
/@rhi{10 div/rhi X/rhiSeen true N}B/@llx{/llx X}B/@lly{/lly X}B/@urx{
/urx X}B/@ury{/ury X}B/magscale true def end/@MacSetUp{userdict/md known
{userdict/md get type/dicttype eq{userdict begin md length 10 add md
maxlength ge{/md md dup length 20 add dict copy def}if end md begin
/letter{}N/note{}N/legal{}N/od{txpose 1 0 mtx defaultmatrix dtransform S
atan/pa X newpath clippath mark{transform{itransform moveto}}{transform{
itransform lineto}}{6 -2 roll transform 6 -2 roll transform 6 -2 roll
transform{itransform 6 2 roll itransform 6 2 roll itransform 6 2 roll
curveto}}{{closepath}}pathforall newpath counttomark array astore/gc xdf
pop ct 39 0 put 10 fz 0 fs 2 F/|______Courier fnt invertflag{PaintBlack}
if}N/txpose{pxs pys scale ppr aload pop por{noflips{pop S neg S TR pop 1
-1 scale}if xflip yflip and{pop S neg S TR 180 rotate 1 -1 scale ppr 3
get ppr 1 get neg sub neg ppr 2 get ppr 0 get neg sub neg TR}if xflip
yflip not and{pop S neg S TR pop 180 rotate ppr 3 get ppr 1 get neg sub
neg 0 TR}if yflip xflip not and{ppr 1 get neg ppr 0 get neg TR}if}{
noflips{TR pop pop 270 rotate 1 -1 scale}if xflip yflip and{TR pop pop
90 rotate 1 -1 scale ppr 3 get ppr 1 get neg sub neg ppr 2 get ppr 0 get
neg sub neg TR}if xflip yflip not and{TR pop pop 90 rotate ppr 3 get ppr
1 get neg sub neg 0 TR}if yflip xflip not and{TR pop pop 270 rotate ppr
2 get ppr 0 get neg sub neg 0 S TR}if}ifelse scaleby96{ppr aload pop 4
-1 roll add 2 div 3 1 roll add 2 div 2 copy TR .96 dup scale neg S neg S
TR}if}N/cp{pop pop showpage pm restore}N end}if}if}N/normalscale{
Resolution 72 div VResolution 72 div neg scale magscale{DVImag dup scale
}if 0 setgray}N/psfts{S 65781.76 div N}N/startTexFig{/psf$SavedState
save N userdict maxlength dict begin/magscale true def normalscale
currentpoint TR/psf$ury psfts/psf$urx psfts/psf$lly psfts/psf$llx psfts
/psf$y psfts/psf$x psfts currentpoint/psf$cy X/psf$cx X/psf$sx psf$x
psf$urx psf$llx sub div N/psf$sy psf$y psf$ury psf$lly sub div N psf$sx
psf$sy scale psf$cx psf$sx div psf$llx sub psf$cy psf$sy div psf$ury sub
TR/showpage{}N/erasepage{}N/copypage{}N/p 3 def @MacSetUp}N/doclip{
psf$llx psf$lly psf$urx psf$ury currentpoint 6 2 roll newpath 4 copy 4 2
roll moveto 6 -1 roll S lineto S lineto S lineto closepath clip newpath
moveto}N/endTexFig{end psf$SavedState restore}N/@beginspecial{SDict
begin/SpecialSave save N gsave normalscale currentpoint TR
@SpecialDefaults count/ocount X/dcount countdictstack N}N/@setspecial{
CLIP 1 eq{newpath 0 0 moveto hs 0 rlineto 0 vs rlineto hs neg 0 rlineto
closepath clip}if ho vo TR hsc vsc scale ang rotate rwiSeen{rwi urx llx
sub div rhiSeen{rhi ury lly sub div}{dup}ifelse scale llx neg lly neg TR
}{rhiSeen{rhi ury lly sub div dup scale llx neg lly neg TR}if}ifelse
CLIP 2 eq{newpath llx lly moveto urx lly lineto urx ury lineto llx ury
lineto closepath clip}if/showpage{}N/erasepage{}N/copypage{}N newpath}N
/@endspecial{count ocount sub{pop}repeat countdictstack dcount sub{end}
repeat grestore SpecialSave restore end}N/@defspecial{SDict begin}N
/@fedspecial{end}B/li{lineto}B/rl{rlineto}B/rc{rcurveto}B/np{/SaveX
currentpoint/SaveY X N 1 setlinecap newpath}N/st{stroke SaveX SaveY
moveto}N/fil{fill SaveX SaveY moveto}N/ellipse{/endangle X/startangle X
/yrad X/xrad X/savematrix matrix currentmatrix N TR xrad yrad scale 0 0
1 startangle endangle arc savematrix setmatrix}N end

%%EndProcSet
TeXDict begin 40258431 52099146 1000 600 600 (latex8.dvi)
@start /Fa 166[43 1[56 43 43 37 33 40 1[33 43 43 53 37
43 1[20 43 43 33 37 43 40 40 43 65[{TeXBase1Encoding ReEncodeFont}22
59.7758 /Times-Roman rf /Fb 134[33 2[33 37 21 29 29 1[37
37 37 54 21 1[21 21 1[37 21 33 37 33 37 37 13[37 2[46
54 50 62 42 1[33 25 3[46 54 50 46 46 14[37 37 37 1[19
25 3[25 25 25 39[{TeXBase1Encoding ReEncodeFont}41 74.7198
/Times-Italic rf /Fc 103[25 1[37 27[33 37 37 54 37 37
21 29 25 37 37 37 37 58 21 37 21 21 37 37 25 33 37 33
37 33 3[25 1[25 46 2[71 1[54 46 42 50 1[42 54 54 66 46
54 29 25 54 54 42 46 54 50 50 54 6[21 37 37 37 37 37
37 37 37 37 37 21 19 25 19 2[25 25 40[{TeXBase1Encoding ReEncodeFont}69
74.7198 /Times-Roman rf /Fd 133[50 2[50 50 50 50 50 50
1[50 50 50 50 50 50 1[50 1[50 50 50 50 50 1[50 11[50
1[50 2[50 50 50 1[50 5[50 1[50 50 50 50 3[50 7[50 1[50
50 50 50 50 1[50 3[50 50 40[{TeXBase1Encoding ReEncodeFont}41
83.022 /Courier rf
%DVIPSBitmapFont: Fe cmbx10 10 2
/Fe 2 106 df<EC1FF0903801FFFC010713FF90391FF87F8090383FE0FFD9FFC113C0A2
481381A24813016E1380A2ED3E0092C7FCA8B6FCA4000390C8FCB3ABB512FEA4223A7DB9
1D>102 D<EA01F0EA07FC487EA2487EA56C5AA26C5AEA01F0C8FCA913FF127FA412077E
B3A9B512F8A4153B7DBA1B>105 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Ff cmex10 10 5
/Ff 5 63 df<161E167EED01FE1507ED0FF8ED3FE0ED7FC0EDFF80913801FE004A5A4A5A
5D140F4A5A5D143F5D147F92C7FCA25C5CB3B3B3A313015CA3495AA213075C495AA2495A
495A137F49C8FC485A485AEA07F0EA1FE0485AB4C9FC12FCA2B4FCEA3FC06C7EEA07F0EA
03FC6C7E6C7E6D7E133F6D7E6D7EA26D7E801303A26D7EA3801300B3B3B3A38080A28114
3F81141F816E7E1407816E7E6E7E913800FF80ED7FC0ED3FE0ED0FF8ED07FE1501ED007E
161E27C675823E>26 D<EC01F01407140F143F147F903801FFC0491380491300495A495A
495A495A5C495A485B5A91C7FC485AA2485AA2485AA2123F5BA2127F5BA412FF5BB3B3A7
1C4B607E4A>56 D<EAFFC0B3B3A77F127FA47F123FA27F121FA26C7EA26C7EA26C7E807E
6C7F6D7E806D7E6D7E6D7E6D7E6D13806D13C09038007FF0143F140F140714011C4B6080
4A>58 D<EC1FF8B3B3A7143F15F0A4EC7FE0A315C014FFA2491380A215005B5C1307495A
5C131F495A5C495A495A4890C7FC485A485A485A485AEA7FE0EAFF8090C8FC12FCB4FC7F
EA7FE0EA1FF06C7E6C7E6C7E6C7E6C7F6D7E6D7E806D7E130F806D7E1303807F1580A26D
13C0A2147F15E0A3EC3FF0A415F8141FB3B3A71D9773804A>60 D<EAFFC0B3A90A1B6080
4A>62 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fg cmsy7 7 1
/Fg 1 49 df<13E0EA01F0EA03F8A3EA07F0A313E0A2120F13C0A3EA1F80A21300A25A12
3EA35AA3127812F8A25A12100D1E7D9F13>48 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fh cmr10 10 6
/Fh 6 62 df<146014E0EB01C0EB0380EB0700130E131E5B5BA25B485AA2485AA212075B
120F90C7FCA25A121EA2123EA35AA65AB2127CA67EA3121EA2121F7EA27F12077F1203A2
6C7EA26C7E1378A27F7F130E7FEB0380EB01C0EB00E01460135278BD20>40
D<12C07E12707E7E7E120F6C7E6C7EA26C7E6C7EA21378A2137C133C133E131EA2131F7F
A21480A3EB07C0A6EB03E0B2EB07C0A6EB0F80A31400A25B131EA2133E133C137C1378A2
5BA2485A485AA2485A48C7FC120E5A5A5A5A5A13527CBD20>I<EB03F8EB1FFF90387E0F
C09038F803E03901E000F0484813780007147C48487FA248C77EA2481580A3007EEC0FC0
A600FE15E0B3007E15C0A4007F141F6C1580A36C15006D5B000F143EA26C6C5B6C6C5B6C
6C485A6C6C485A90387E0FC0D91FFFC7FCEB03F8233A7DB72A>48
D<EB01C013031307131F13FFB5FCA2131F1200B3B3A8497E007FB512F0A31C3879B72A>
I<121C127FEAFF80A5EA7F00121CC7FCB2121C127FEAFF80A5EA7F00121C092479A317>
58 D<007FB812F8B912FCA26C17F8CCFCAE007FB812F8B912FCA26C17F836167B9F41>
61 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fi cmmi7 7 4
/Fi 4 111 df<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA187C1230A212
605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A131CEA07F0
6C5A11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7EB03E0EB07F8EB0C3C
1318EB303E136013C0A248485AA2C7FCA25CA4495AA4495AA4495AA4495AA21238D87C1F
C7FC12FC133E485AEA70F8EA7FE0EA1F80193380A61B>I<133EEA07FEA2EA007CA213FC
A25BA21201A25BA21203EC07809038E01FC0EC38600007EB61E014C3EBC187EBC307D80F
C613C09038CC038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E1303003E1460A2127E
ECC0C0127CECC18012FC903801E30038F800FE0070137C1B297CA723>I<3907801FC039
0FE07FF03918F0E0F83930F1807CEBFB00D860FE133C5B5B00C1147C5B1201A248485BA3
4A5AEA07C01660EC03E0A23A0F8007C0C0A2EDC180913803C300D81F0013C7EC01FE000E
EB00F8231B7D9929>110 D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fj cmr7 7 1
/Fj 1 50 df<13381378EA01F8121F12FE12E01200B3AB487EB512F8A215267BA521>49
D E
%EndDVIPSBitmapFont
%DVIPSBitmapFont: Fk cmmi10 10 27
/Fk 27 123 df<121C127FEAFF80A5EA7F00121C0909798817>58
D<121C127FEAFF80A213C0A3127F121C1200A412011380A2120313005A1206120E5A5A5A
12600A19798817>I<EF0380EF0FC0173FEFFF80933803FE00EE0FF8EE3FE0EEFF80DB03
FEC7FCED0FF8ED3FE0EDFF80DA03FEC8FCEC0FF8EC3FE0ECFF80D903FEC9FCEB0FF8EB3F
E0EBFF80D803FECAFCEA0FF8EA3FE0EA7F8000FECBFCA2EA7F80EA3FE0EA0FF8EA03FEC6
6C7EEB3FE0EB0FF8EB03FE903800FF80EC3FE0EC0FF8EC03FE913800FF80ED3FE0ED0FF8
ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FC0170FEF0380323279AD41>
I<126012FCB4FCEA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007F
C0EC1FF0EC07FCEC01FF9138007FC0ED1FF0ED07FCED01FF9238007FC0EE1FF0EE07FCEE
01FF9338007F80EF1FC0A2EF7F80933801FF00EE07FCEE1FF0EE7FC04B48C7FCED07FCED
1FF0ED7FC04A48C8FCEC07FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA
07FCEA3FF0EA7FC048CBFC12FC1270323279AD41>62 D<0103B6FC5B5E90260007FCC8FC
5D5D140FA25DA2141FA25DA2143FA25DA2147FA292C9FCA25CA25CA21301A25CA21303A2
5CA2130718404A15C0A2010F150118804A1403A2011F16005F4A1406170E013F151E171C
4A143C177C017F5D160391C7120F49EC7FF0B8FCA25F32397DB839>76
D<902603FFF891381FFFF8496D5CA2D90007030113006FEC007C02061678DA0EFF157081
020C6D1460A2DA1C3F15E0705CEC181F82023815016F6C5C1430150702706D1303030392
C7FC02607FA2DAE0015C701306ECC0008201016E130EEF800C5C163F0103EDC01C041F13
1891C713E0160F49EDF03818300106140717F8010E02031370EFFC60130CEE01FE011C16
E004005B011815FF177F1338600130153FA20170151F95C8FC01F081EA07FCB512E01706
A245397DB843>78 D<4BB4FC031F13F09238FE01FC913903F0007EDA07C0EB1F80DA1F80
EB0FC0023EC7EA07E002FCEC03F0495A4948EC01F8495A4948EC00FC495A49C912FE4916
7E13FE49167F1201485AA2485AA2120F5B001F17FFA2485AA34848ED01FEA400FFEE03FC
90C9FCA2EF07F8A2EF0FF0A218E0171F18C0EF3F806C167F180017FE4C5A6C6C5D160300
1F4B5A6D4A5A000FED1F806C6C4AC7FC6D147E0003EC01F8D801FC495AD8007EEB0FC090
263F807FC8FC903807FFF801001380383D7CBA3F>I<003FB56C48B51280485DA226007F
80C7381FF00091C8EA07C0604993C7FCA2491506A20001160E170C5BA20003161C17185B
A20007163817305BA2000F167017605BA2001F16E05F5BA2003F15015F5BA2007F150394
C8FC90C8FCA25E4815065A160E160C161C161816385E127E5E4B5A6C4A5A4BC9FC6C6C13
1E6C6C5B6C6C13F83903F807E06CB55A6C6C48CAFCEB0FF0393B7BB839>85
D<147E903803FF8090390FC1C38090391F00EFC0017E137F49133F485A4848EB1F801207
5B000F143F48481400A2485A5D007F147E90C7FCA215FE485C5AA214015D48150CA21403
EDF01C16181407007C1538007E010F1330003E131F027B13706C01E113E03A0F83C0F9C0
3A03FF007F80D800FCEB1F0026267DA42C>97 D<EC3FC0903801FFF0903807E03C90380F
800E90383F0007017E131F49137F484813FF485A485A120F4913FE001F143848481300A2
127F90C8FCA35A5AA45AA315031507007E1406150E003E143C003F14706C14E0390F8007
C03907C03F003801FFF838003FC020267DA424>99 D<163FED1FFFA3ED007F167EA216FE
A216FCA21501A216F8A21503A216F0A21507A2027E13E0903803FF8790380FC1CF90381F
00EF017EEB7FC049133F485A4848131F000715805B000F143F485A1600485A5D127F90C7
127EA215FE5A485CA21401A248ECF80CA21403161CEDF0181407007C1538007E010F1330
003E131F027B13706C01E113E03A0F83C0F9C03A03FF007F80D800FCEB1F00283B7DB92B
>I<EC3FC0903801FFF0903807E07890381F801C90387E001E49130E485A485A1207485A
49131E001F141C153C484813F8EC03E0007FEB3FC09038FFFE0014E090C8FC5A5AA7007E
140315071506003E140E153C6C14706C6C13E0EC07C03903E03F003801FFF838003FC020
267DA427>I<16F8ED03FEED0F8792381F0F80ED3E3F167F157CA215FC1700161C4A48C7
FCA414035DA414075DA20107B512F0A39026000FE0C7FC5DA4141F5DA4143F92C8FCA45C
147EA514FE5CA413015CA4495AA45C1307A25C121E123F387F8F80A200FF90C9FC131E12
FEEA7C3CEA7878EA1FF0EA07C0294C7CBA29>I<EC07E0EC1FF891387C1C38903901F80E
FC903803F007903807E003EB0FC090381F8001D93F0013F85B017E130313FE16F0485A15
0712034914E0A2150F12074914C0A2151FA2491480A2153FA2160000035C6D5B00015B4A
5A3900F8077E90387C1EFEEB1FF8903807E0FC90C7FC1401A25DA21403001E5C123F387F
80075D00FF495A49485A4849C7FC007C137E383C01F8381FFFE0000390C8FC26367FA428
>I<14E0EB03F8A21307A314F0EB01C090C7FCAB13F8EA03FEEA070F000E1380121C1218
12381230EA701F1260133F00E0130012C05BEA007EA213FE5B1201A25B12035BA2000713
1813E01438000F133013C01470EB806014E014C01381EB838038078700EA03FEEA00F815
397EB71D>105 D<150FED3F80A2157FA31600151C92C7FCABEC0F80EC3FE0ECF0F09038
01C0F849487E14005B130E130C131CEB1801133801305BA2EB0003A25DA21407A25DA214
0FA25DA2141FA25DA2143FA292C7FCA25CA2147EA214FEA25CA21301001E5B123F387F83
F0A238FF87E0495A00FE5BD87C1FC8FCEA707EEA3FF8EA0FC0214981B722>I<EB03F0EA
01FFA3EA00075CA3130F5CA3131F5CA3133F91C8FCA35B017EEB07C0ED1FF0ED783801FE
EBE0F89039FC01C1FCEC0383EC07070001130ED9F81C13F891383803F091387001E00003
49C7FCEBF1C0EBF38001F7C8FCEA07FEA2EBFFE0EBE7F8380FE0FEEBC07F6E7E141F001F
80D9800F1330A21670003F011F136001001380A216E04815C0007E1481020F1380158300
FE903807870048EB03FE0038EB00F8263B7CB92B>I<EB0FC0EA03FF5AA2EA001F1480A2
133FA21400A25BA2137EA213FEA25BA21201A25BA21203A25BA21207A25BA2120FA25BA2
121FA25BA2123FA290C7FCA25AA2EA7E03A2EAFE07130612FCA2130E130C131C1318EA7C
38EA3C70EA1FE0EA0780123B7DB919>I<D803E0017F14FE3D07F801FFE003FFC03D0E3C
0781F00F03E03D1C3E1E00F83C01F026383F38D9FC707F00304914E04A90387DC0000070
49EB7F8000604991C7FCA200E090C700FE1301485A017E5CA200000201140301FE5F495C
A203031407000160495C180F03075D1203494A011F13601980030F023F13E00007F000C0
495C1901031F023E1380000F1803494A150061033F150E001FEF1E1C4991C7EA0FF80007
C7000EEC03E043267EA449>I<D803E0137F3A07F801FFE03A0E3C0781F03A1C3E1E00F8
26383F387F00305B4A137C00705B00605BA200E090C712FC485A137EA20000140101FE5C
5BA2150300015D5B15075E120349010F133016C0031F13700007ED80605B17E0EE00C000
0F15014915801603EE0700001FEC0F0E49EB07FC0007C7EA01F02C267EA432>I<90390F
8003F090391FE00FFC903939F03C1F903A70F8700F80903AE0FDE007C09038C0FF800300
13E00001491303018015F05CEA038113015CA2D800031407A25CA20107140FA24A14E0A2
010F141F17C05CEE3F80131FEE7F004A137E16FE013F5C6E485A4B5A6E485A90397F700F
80DA383FC7FC90387E1FFCEC07E001FEC9FCA25BA21201A25BA21203A25B1207B512C0A3
2C3583A42A>112 D<02FC13C0903803FF0190380F838390383F01C790397E00EF804913
7F485A4848133F000715005B485A001F5C157E485AA2007F14FE90C75AA3481301485CA3
1403485CA314075D140F127C141F007E495A003E137F381F01EF380F839F3903FF1F80EA
00FC1300143F92C7FCA35C147EA314FE5C130190387FFFF0A322357DA425>I<3903E001
F83907F807FE390E3C1E07391C3E381F3A183F703F800038EBE07F0030EBC0FF00705B00
601500EC007E153CD8E07F90C7FCEAC07EA2120013FE5BA312015BA312035BA312075BA3
120F5BA3121F5B0007C9FC21267EA425>I<14FF010313C090380F80F090383E00380178
131C153C4913FC0001130113E0A33903F000F06D13007F3801FFE014FC14FF6C14806D13
C0011F13E013039038003FF014071403001E1301127FA24814E0A348EB03C012F800E0EB
07800070EB0F006C133E001E13F83807FFE0000190C7FC1E267CA427>I<13F8D803FE14
38D8070F147C000E6D13FC121C1218003814011230D8701F5C12601503EAE03F00C00100
5B5BD8007E1307A201FE5C5B150F1201495CA2151F120349EC80C0A2153F1681EE0180A2
ED7F0303FF130012014A5B3A00F8079F0E90397C0E0F1C90393FFC07F8903907F001F02A
267EA430>117 D<01F8EB03C0D803FEEB07E0D8070F130F000E018013F0121C12180038
140700301403D8701F130112601500D8E03F14E000C090C7FC5BEA007E16C013FE5B1501
000115805B150316001203495B1506150E150C151C151815385D00015C6D485A6C6C485A
D97E0FC7FCEB1FFEEB07F024267EA428>I<D901E01360D90FF813E0496C13C090383FFE
0190397FFF038090B5EA07009038F81FFF3901E003FE9038C0001C495B5DC85A4A5A4A5A
4AC7FC140E5C5C14F0495AEB038049C8FC130E5B4913035B495B484813064848130E48C7
5AD80FFC137C391FFF81F8381E0FFFD838075B486C5B00605CD8E00190C7FC38C0007C23
267DA427>122 D E
%EndDVIPSBitmapFont
/Fl 82[28 51[46 46 65 46 51 28 46 32 51 51 51 51 74 23
46 1[23 51 51 28 46 51 46 51 46 12[51 55 60 1[55 65 60
69 51 3[60 65 51 55 60 2[60 8[46 3[46 46 46 46 46 23
23 1[23 2[28 28 36[51 3[{TeXBase1Encoding ReEncodeFont}51
83.022 /Helvetica-Bold rf /Fm 87[28 19[37 37 24[37 42
42 60 42 42 23 32 28 42 42 42 42 65 23 42 23 23 42 42
28 37 42 37 42 37 3[28 1[28 51 2[78 60 60 51 46 55 60
46 60 60 74 51 2[28 60 60 46 51 60 55 55 60 76 5[23 42
42 42 42 42 42 42 42 42 42 23 21 28 21 2[28 28 28 1[69
33[46 46 2[{TeXBase1Encoding ReEncodeFont}75 83.022 /Times-Roman
rf /Fn 138[37 2[29 4[55 11[33 16[41 13[44 66[{
TeXBase1Encoding ReEncodeFont}6 66.4176 /Times-Bold rf
/Fo 87[22 19[29 29 24[29 33 1[48 33 33 18 26 22 1[33
33 33 52 18 33 18 18 33 33 22 29 33 29 33 29 9[63 2[41
37 44 1[37 48 48 2[48 1[22 48 3[48 44 44 7[18 11[17 22
17 2[22 22 37[37 2[{TeXBase1Encoding ReEncodeFont}47
66.4176 /Times-Roman rf
%DVIPSBitmapFont: Fp cmsy6 6 1
/Fp 1 4 df<136013701360A20040132000E0137038F861F0387E67E0381FFF803807FE
00EA00F0EA07FE381FFF80387E67E038F861F038E060700040132000001300A213701360
14157B9620>3 D E
%EndDVIPSBitmapFont
/Fq 134[42 42 2[46 28 32 37 1[46 2[69 23 2[23 46 1[28
4[42 12[55 3[51 1[60 78 55 4[65 1[55 60 60 55 60 17[23
1[28 45[{TeXBase1Encoding ReEncodeFont}26 83.022 /Times-Bold
rf /Fr 133[32 37 37 55 37 42 23 32 32 42 42 42 42 60
23 37 1[23 42 42 23 37 42 37 42 42 12[46 42 51 1[51 1[55
4[28 60 1[51 51 3[51 9[42 1[42 42 42 4[21 28 21 6[69
37[{TeXBase1Encoding ReEncodeFont}43 83.022 /Times-Italic
rf /Fs 134[50 2[50 55 33 39 44 55 55 50 55 83 28 55 1[28
55 1[33 44 55 44 55 50 9[100 3[55 72 8[39 78 1[61 66
1[72 1[72 8[50 50 50 50 50 50 50 50 50 1[25 33 45[{
TeXBase1Encoding ReEncodeFont}41 99.6264 /Times-Bold
rf /Ft 87[33 46[50 50 72 50 50 28 39 33 1[50 50 50 78
28 50 28 28 50 50 33 44 50 44 50 44 9[94 1[72 61 55 66
1[55 1[72 89 61 72 39 33 72 72 55 1[72 66 66 72 92 6[50
50 50 50 50 50 50 50 50 50 28 25 33 25 44[{
TeXBase1Encoding ReEncodeFont}59 99.6264 /Times-Roman
rf
%DVIPSBitmapFont: Fu cmsy10 10 5
/Fu 5 57 df<007FB81280B912C0A26C17803204799641>0 D<EB0380497EA739780380
3C00FC147E00FE14FE397F8383FC393FC387F8390FE38FE03903FBBF803900FFFE00EB3F
F8EB0FE0A2EB3FF8EBFFFE3903FBBF80390FE38FE0393FC387F8397F8383FC39FE0380FE
00FC147E0078143C390007C000A76D5A1F247BA62A>3 D<D93F801508D9FFF0151C0003
13FC487F486D7E4880273FC07FF0143C9026000FF81438007CD903FE147800786D6C14F8
0070903A007FC003F000F091383FF80F48020FB512E06F14C0030114806F1400EE3FFC00
40ED07F0CCFCA2D93F801508D9FFF0151C000313FC487F486D7E4880273FC07FF0143C90
26000FF81438007CD903FE147800786D6C14F80070903A007FC003F000F091383FF80F48
020FB512E06F14C0030114806F1400EE3FFC0040ED07F036267BA741>25
D<EE0180EE03C01607A2EE0F80A2EE1F00A2163EA25EA25EA24B5AA24B5AA24B5A150F5E
4BC7FCA2153EA25DA25DA24A5AA24A5AA24A5AA24A5AA24AC8FCA2143EA25CA25CA2495A
A2495AA2495AA2495AA249C9FCA2133EA25B13FC5B485AA2485AA2485AA2485AA248CAFC
A2123EA25AA25AA25A12602A4E75BB00>54 D<0060161800F0163C6C167CA20078167800
7C16F8A2003C16F0003E1501A26CED03E0A26C16C06D1407A2000716806D140FA26C6CEC
1F00A26CB612FEA36C5D01F8C7127CA2017C5CA2013C5C013E1301A2011E5C011F1303A2
6D6C485AA201075CECC00FA2010391C7FC6E5AA2903801F03EA20100133CECF87CA2EC78
78EC7CF8A2EC3FF0A26E5AA36E5AA36E5A6EC8FC2E3C80B92F>56
D E
%EndDVIPSBitmapFont
/Fv 134[60 60 2[66 40 47 53 66 1[60 66 100 33 66 1[33
66 60 40 53 66 53 1[60 12[80 66 2[73 2[113 80 5[73 2[86
80 86 6[40 58[{TeXBase1Encoding ReEncodeFont}30 119.552
/Times-Bold rf end
%%EndProlog
%%BeginSetup
%%Feature: *Resolution 600dpi
TeXDict begin
%%BeginPaperSize: Letter
letter
%%EndPaperSize

%%EndSetup
%%Page: 1 1
1 0 bop 100 374 a Fv(AxML:)29 b(A)h(F)m(ast)f(Pr)n(ogram)g(f)m(or)h
(Sequential)i(and)e(P)o(arallel)h(Ph)n(ylogenetic)f(T)-9
b(r)n(ee)436 524 y(Calculations)31 b(Based)e(on)h(the)g(Maximum)g(Lik)o
(elihood)h(Method)3324 480 y Fu(\003)1373 839 y Ft(Ale)o(xandros)24
b(P)-11 b(.)25 b(Stamatakis)552 956 y(T)-7 b(echnical)25
b(Uni)n(v)o(ersity)d(of)j(Munich,)f(Department)g(of)h(Computer)f
(Science)441 1072 y(Institut)f(f)8 b(\250)-41 b(ur)25
b(Informatik/SAB)f(TU)h(M)8 b(\250)-41 b(unchen,)24 b(D-80290)g(M)8
b(\250)-41 b(unchen,)24 b(German)o(y)1469 1188 y(stamatak@in.tum.de)
1552 1354 y(Thomas)g(Ludwig)658 1470 y(Ruprecht-Karls-Uni)n(v)o(ersity)
-6 b(,)23 b(Department)h(of)h(Computer)f(Science)711
1587 y(Im)h(Neuenheimer)g(Feld)g(348,)f(D-69120)g(Heidelber)n(g,)h
(German)o(y)1406 1703 y(t.ludwig@computer)-5 b(.or)n(g)1613
1869 y(Harald)25 b(Meier)552 1985 y(T)-7 b(echnical)25
b(Uni)n(v)o(ersity)d(of)j(Munich,)f(Department)g(of)h(Computer)f
(Science)428 2101 y(Institut)f(f)8 b(\250)-41 b(ur)25
b(Informatik/SAB,)g(TU)g(M)8 b(\250)-41 b(unchen,)24
b(D-80290)g(M)8 b(\250)-41 b(unchen,)24 b(German)o(y)1508
2218 y(meierh@in.tum.de)1603 2384 y(Marty)h(J.)f(W)-8
b(olf)343 2500 y(Bemidji)24 b(State)h(Uni)n(v)o(ersity)-6
b(,)22 b(Department)i(of)h(Mathematics)f(and)g(Computer)h(Science)425
2616 y(Hagg-Sauer)h(367,)e(1500)g(Birchmont)g(Dri)n(v)o(e,)g(Bemidji,)g
(MN)g(56601-2699)g(USA)1363 2732 y(mjw)o(olf@bemidjistate.edu)617
3083 y Fs(Abstract)-83 3287 y Fr(Heuristics)31 b(for)g(the)f
(NP-complete)g(pr)l(oblem)f(of)i(calculating)-182 3386
y(the)23 b(optimal)f(phylo)o(g)o(enetic)f(tr)m(ee)j(for)g(a)f(set)h(of)
f(aligned)f(rRN)n(A)i(se-)-182 3486 y(quences)17 b(based)g(on)h(the)h
(maximum)e(lik)o(elihood)h(method)f(ar)m(e)h(com-)-182
3586 y(putationally)g(e)n(xpensive)o(.)27 b(In)21 b(most)g(e)n(xisting)
g(algorithms)f(the)h(tr)m(ee)-182 3685 y(e)o(valuation)15
b(and)h(br)o(anc)o(h)f(length)h(optimization)g(functions,)h(calcu-)-182
3785 y(lating)k(the)g(lik)o(elihood)g(value)g(for)h(eac)o(h)f(tr)m(ee)h
(topolo)o(gy)e(e)n(xamined)-182 3885 y(in)27 b(the)f(sear)m(c)o(h)h
(space)o(,)h(account)d(for)i(the)g(gr)m(eatest)g(part)g(of)g(o)o(ver)n
(-)-182 3984 y(all)21 b(computation)e(time)o(.)29 b(This)22
b(paper)f(intr)l(oduces)g Fq(AxML)p Fr(,)h(a)f(pr)l(o-)-182
4084 y(gr)o(am)f(derived)h(fr)l(om)h Fq(fastDN)n(Aml)p
Fr(,)f(incorpor)o(ating)e(a)i(fast)h(topol-)-182 4183
y(o)o(gy)h(e)o(valuation)e(function.)34 b(The)23 b(algorithmic)g
(optimizations)f(in-)-182 4283 y(tr)l(oduced,)15 b(r)m(epr)m(esent)g(a)
g(g)o(ener)o(al)g(appr)l(oac)o(h)e(for)j(acceler)o(ating)d(this)-182
4383 y(function)26 b(and)i(ar)m(e)g(applicable)e(to)i(both)g
(sequential)f(and)g(par)o(al-)-182 4482 y(lel)g(phylo)o(g)o(eny)e(pr)l
(o)o(gr)o(ams,)i(irr)m(espective)g(of)g(their)g(sear)m(c)o(h)f(space)
-182 4582 y(str)o(ate)m(gy)-5 b(.)23 b(Ther)m(efor)m(e)o(,)17
b(their)g(inte)m(gr)o(ation)d(into)i(thr)m(ee)g(e)n(xisting)h(phy-)-182
4682 y(lo)o(g)o(eny)f(pr)l(o)o(gr)o(ams)g(r)m(ender)m(ed)g(encour)o(a)o
(ging)e(r)m(esults.)25 b(Experimen-)-182 4781 y(tal)h(r)m(esults)h(on)f
(con)m(ventional)d(pr)l(ocessor)k(ar)m(c)o(hitectur)m(es)e(show)i(a)p
-182 4854 788 4 v -99 4907 a Fp(\003)-63 4931 y Fo(This)32
b(w)o(ork)g(is)g(partially)j(sponsored)e(under)g(the)g(project)h(ID)d
Fn(P)o(arBaum)p Fo(,)-182 5010 y(within)d(the)f(frame)n(w)o(ork)i(of)e
(the)g(\223Competence)j(Netw)o(ork)f(for)e(T)-5 b(echnical,)31
b(Sci-)-182 5088 y(enti\002c)e(High)g(Performance)h(Computing)f(in)g
(Ba)o(v)n(aria\224:)46 b(K)n(ompetenznetzwerk)-182 5167
y(f)6 b(\250)-28 b(ur)29 b(T)-5 b(echnisch-W)m(issenschaftliche)q(s)34
b(Hoch-)29 b(und)h(H)6 b(\250)-28 b(ochstleistungsrechnen)34
b(in)-182 5246 y(Bayern)29 b(\(K)n(ONWIHR\).)f(K)n(ONWIHR)g(is)g
(funded)h(by)g(means)f(of)h(\223High-T)-5 b(ech-)-182
5325 y(Of)n(fensi)n(v)o(e)19 b(Bayern\224.)1974 3083
y Fr(global)f(run)h(time)h(impr)l(o)o(vement)e(of)i(35\045)f(up)g(to)g
(47\045)g(for)h(the)f(var)n(-)1974 3182 y(ious)h(test)h(sets)g(and)f
(pr)l(o)o(gr)o(am)f(ver)o(sions)i(we)g(used.)1974 3515
y Fs(1.)j(Intr)n(oduction)2073 3731 y Fm(At)31 b(the)f
Fq(P)o(arBaum)g Fm(project)f(at)i(the)f(T)-6 b(echnische)29
b(Uni)n(v)o(ersit)5 b(\250)-33 b(at)1974 3830 y(M)7 b(\250)-35
b(unchen)41 b(\(TUM\))h(w)o(ork)g(is)h(conducted)e(to)i(f)o(acilitate)f
(lar)o(ge-)1974 3930 y(scale)35 b(parallel)f(phylogenetic)d(tree)j
(computations)f(on)h(trees)g(of)1974 4030 y(at)i(least)g(1000)f(taxa)g
(on)h(the)f(Hitachi)h(SR8000-F1)e(supercom-)1974 4129
y(puter)18 b(installed)g(at)h(the)f(Leibniz-Rechenzentrum)d(\(LRZ\))j
(in)h(Mu-)1974 4229 y(nich.)60 b(Our)32 b(w)o(ork)f(relies)h(on)g
(sequence)f(data)h(pro)o(vided)e(by)h(the)1974 4329 y(ARB)37
b([9])f(rRN)m(A-sequence)f(database,)k(de)n(v)o(eloped)34
b(jointly)i(by)1974 4428 y(the)24 b(Lehrstuhl)e(f)7 b(\250)-35
b(ur)23 b(Rechnertechnik)f(und)g(Rechneror)o(ganisation)1974
4528 y(\(LRR\))29 b(and)g(the)g(Department)e(of)i(Microbiology)d(of)j
(the)g(TUM.)1974 4628 y(The)34 b(ARB)h(database)f(pro)o(vides)e(a)j
(huge)e(amount)f(of)i(sequence)1974 4727 y(data)20 b(with)g(e)o
(xcellent)g(alignment)e(quality)-5 b(.)2073 4827 y(Lik)o(e)31
b(man)o(y)e(problems)g(associated)h(with)h(genome)d(analysis,)1974
4926 y(the)e(perfect)g(phylogen)o(y)d(problem)i(is)i(NP-complete.)43
b(Thus,)27 b(the)1974 5026 y(introduction)e(of)i(heuristics)h(for)f
(reducing)e(the)j(search)f(space)h(in)1974 5126 y(terms)36
b(of)g(potential)f(tree)i(topologies)d(e)n(v)n(aluated)h(becomes)g(in-)
1974 5225 y(e)n(vitable.)43 b(Heuristics)27 b(for)e(phylogenetic)f
(tree)i(calculations)g(still)1974 5325 y(remain)f(computationally)e(e)o
(xpensi)n(v)o(e,)i(mainly)g(due)g(to)h(the)g(high)p eop
%%Page: 2 2
2 1 bop -182 83 a Fm(cost)17 b(of)f(the)h(tree)f(lik)o(elihood)g
(function,)f(which)h(is)i(in)m(v)n(ok)o(ed)d(repeat-)-182
183 y(edly)k(for)h(each)g(tree)g(topology)e(analyzed.)-83
282 y(Thus,)34 b(only)c(relati)n(v)o(ely)h(small)h(trees)f(\()p
Fu(\031)h Fm(500)e(taxa)h([7])g([8)o(]\),)-182 382 y(compared)26
b(to)j(the)f(huge)g(amount)f(of)h(data)g(a)n(v)n(ailable)g(\()p
Fu(\031)h Fm(20000)-182 482 y(sequences)f(in)h(the)g(ARB)i(database\),)
f(ha)n(v)o(e)f(been)f(calculated)h(so)-182 581 y(f)o(ar)-5
b(.)-83 681 y(W)e(e)20 b(focus)e(on)g Fr(thr)m(ee)h Fm(k)o(e)o(y)f
(areas)h(to)g(attain)g(our)f(goal)g(of)g(produc-)-182
780 y(ing)h(lar)o(ge,)g(high)h(quality)f(e)n(v)n(olutionary)f(trees:)
-120 933 y(1.)41 b Fr(Impr)l(o)o(vement)14 b(of)i(the)g(e)n(xisting)g
(algorithms)f Fm(by)g(introduction)-16 1032 y(of)20 b(ne)n(w)g
(heuristics)g(and)f(algorithmic)g(optimizations.)-120
1192 y(2.)41 b(Adaptation)20 b(of)h(the)g(e)o(xisting)g(algorithms)f
(to)i Fr(hybrid)f(super)n(-)-16 1291 y(computer)e(ar)m(c)o(hitectur)m
(es)p Fm(.)-120 1450 y(3.)41 b(Inte)o(gration)21 b(of)i
Fr(empirical)h(biolo)o(gical)e(knowledg)o(e)g Fm(into)i(al-)-16
1550 y(gorithms.)-83 1702 y(This)j(paper)f(mainly)f(presents)i(results)
f(concerning)e(algorith-)-182 1802 y(mic)29 b(optimizations)e(for)i
(accelerating)e(the)i(computation)e(of)i(the)-182 1902
y(topology)21 b(e)n(v)n(aluation)h(function)g(and)h(describes)g(an)h
(initial)g(adap-)-182 2001 y(tation)19 b(of)h(the)g(parallel)f(program)
f(to)i(the)g(Hitachi)g(SR8000-F1)e(su-)-182 2101 y(percomputer)m(,)e
(i.e.)21 b(co)o(v)o(ers)e(points)g(1)i(and)e(2.)-83 2200
y(The)37 b(optimizations)e(are)i(applicable)e(to)i(most)g(e)o(xisting)f
(se-)-182 2300 y(quential)22 b(and)g(parallel)h(programs,)e(for)i
(phylogenetic)d(tree)j(infer)n(-)-182 2400 y(ence)g(based)g(on)g(the)g
(maximum)f(lik)o(elihood)g(method,)g(especially)-182
2499 y(deri)n(v)n(ati)n(v)o(es)h(of)h Fq(fastDN)n(Aml)h
Fm([6)o(])g([11)n(])g(and)f(the)h Fq(ph)o(ylip)g Fm([12)o(])g([4)o(])
-182 2599 y(package)17 b(and)i(are)g(independent)d(from)i(the)h
(speci\002c)g(search)g(space)-182 2699 y(strate)o(gy)-5
b(.)-83 2798 y(W)e(e)26 b(implemented)d(the)i(optimizations)f(proposed)
f(in)i(this)g(pa-)-182 2898 y(per)g(in)h Fq(AxML)g Fm
(\(A\(x\)cce-lerated)d(Maximum)h(Lik)o(elihood\))f(and)-182
2997 y Fq(P)-6 b(AxML)18 b Fm(\(P)o(arallel)g(AxML\))f(based)h(on)g
(the)g(latest)h(sequential)e(and)-182 3097 y(parallel)i(releases)i(of)f
Fq(fastDN)n(Aml)g Fm(\(v)-5 b(.1.2.2\).)-83 3197 y(Our)20
b(initial)g(e)o(xperiments)e(on)h(con)m(v)o(entional)e(processor)i
(archi-)-182 3296 y(tectures)36 b(obtained)e(total)j(run)e(time)i
(reductions)d(ranging)h(from)-182 3396 y(35\045)21 b(to)h(47\045,)f
(both)g(for)g(the)g(sequential,)g(as)h(well)h(as)f(the)f(parallel)-182
3496 y(program.)i(Furthermore,)17 b Fq(P)-6 b(AxML)21
b Fm(has)g(already)e(been)g(appropri-)-182 3595 y(atly)29
b(adapted)f(to)h(the)h(Hitachi)f(SR8000-F1)f(supercomputer)e(ar)n(-)
-182 3695 y(chitecture)d(and)h(rendered)f(30\045)h(to)h(35\045)f
(performance)e(impro)o(v-)-182 3794 y(ment)d(for)h(suf)n(\002ciently)f
(lar)o(ge)g(data)i(sets.)-83 3894 y(These)31 b(results)h(are)f
(promising)f(\002rst)i(steps)g(to)n(w)o(ard)e(ef)n(\002cient)-182
3994 y(determination)25 b(of)j(lar)o(ge,)g(high)f(quality)g(e)n(v)n
(olutionary)f(trees)i(us-)-182 4093 y(ing)20 b(supercomputers.)k(In)c
(addition,)f(we)i(ha)n(v)o(e)f(demonstrated)f(the)-182
4193 y(generality)25 b(of)i(our)f(approach)f(by)i(incorporating)d(our)i
(optimiza-)-182 4293 y(tion)i(into)h Fq(T)-6 b(rExML)p
Fm(,)30 b(a)g(program)c(with)k(a)f(more)f(e)o(xtensi)n(v)o(e)g(tree)
-182 4392 y(space)18 b(e)o(xploration)f(strate)o(gy)g(than)i
Fq(fastDN)n(Aml)p Fm(.)24 b(W)-7 b(e)20 b(call)f(the)g(re-)-182
4492 y(sulting)h(program)e Fq(A)p Fm(ccelerated)h Fq(T)-6
b(rExML)22 b Fm(\()p Fq(A)-8 b(T)i(rExML)p Fm(\).)21
b(Initial)-182 4592 y(e)o(xperiments)32 b(with)j Fq(A)-8
b(T)i(rExML)36 b Fm(ha)n(v)o(e)e(sho)n(wn)g(analogous)e(per)n(-)-182
4691 y(formance)19 b(impro)o(v)o(ements)f(o)o(v)o(er)i
Fq(T)-6 b(rExML)22 b Fm(to)g(those)f(mentioned)-182 4791
y(abo)o(v)o(e.)-182 5016 y Fs(2)o(.)k(Subtr)n(ee)i(Column)f(Equalities)
-83 5225 y Fm(In)34 b(general)g(the)g(cost)h(of)g(the)f(lik)o(elihood)f
(function)g(and)h(the)-182 5325 y(branch)15 b(length)i(optimization)f
(function,)g(which)h(accounts)f(for)h(the)1974 83 y(greatest)30
b(portion)g(of)g(e)o(x)o(ecution)f(time)i(\(95\045)f(in)h(the)g
(sequential)1974 183 y(v)o(ersion)19 b(of)h Fq(fastDN)n(Aml)p
Fm(\),)f(can)h(be)g(reduced)f(in)h(tw)o(o)h(w)o(ays:)2073
282 y Fr(F)l(ir)o(stly)p Fm(,)35 b(by)29 b(reducing)g(the)h(size)h(of)f
(the)g(search)g(space)h(using)1974 382 y(some)37 b(additional)e
(heuristics,)41 b(i.e.)76 b(reducing)35 b(the)i(number)e(of)1974
482 y(topologies)21 b(e)n(v)n(aluated)g(and)h(thus)g(reducing)f(the)h
(number)f(of)h(lik)o(e-)1974 581 y(lihood)16 b(function)g(in)m(v)n
(ocations.)23 b(This)18 b(approach)d(might,)j(ho)n(we)n(v)o(er)m(,)1974
681 y(o)o(v)o(er)h(look)g(high)g(quality)h(trees.)2073
780 y Fr(Secondly)p Fm(,)f(by)h(reducing)e(the)j(number)d(of)i
(sequence)g(positions)1974 880 y(tak)o(en)31 b(into)f(account)g(during)
g(computation)e(and)j(thus)g(reducing)1974 980 y(the)20
b(number)e(of)h(computations)f(at)j(each)e(inner)g(node)g(during)g
(each)1974 1079 y(tree')-5 b(s)20 b(e)n(v)n(aluation.)1974
2573 y @beginspecial 0 @llx 0 @lly 238 @urx 169 @ury
2362 @rwi @setspecial
%%BeginDocument: matrix.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: matrix.eps
%%Creator: /usr/local/dist/DIR/xfig-3.2.3c/bin/fig2dev Version 3.2 Patchlevel 3c
%%CreationDate: Mon Jun 10 14:10:48 2002
%%For: stamatak@sunbode13 (Alexandros Stamatakis)
%%BoundingBox: 0 0 238 169
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
newpath 0 169 moveto 0 0 lineto 238 0 lineto 238 169 lineto closepath clip newpath
-25.0 186.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
%%Page: 1 1
10 setmiterlimit
 0.06299 0.06299 sc
%
% Fig objects follow
%
% Polyline
7.500 slw
n 900 450 m 4050 450 l 4050 1575 l 900 1575 l
 cp gs col0 s gr 
% Polyline
n 1575 450 m 1710 450 l 1710 1575 l 1575 1575 l
 cp gs col7 0.75 shd ef gr gs col0 s gr 
% Polyline
n 2032 457 m 2175 457 l 2175 1567 l 2032 1567 l
 cp gs col7 0.75 shd ef gr gs col0 s gr 
% Polyline
n 2902 457 m 3397 457 l 3397 1575 l 2902 1575 l
 cp gs col7 0.90 shd ef gr gs col0 s gr 
% Polyline
gs  clippath
1692 1555 m 1633 1564 l 1655 1714 l 1667 1591 l 1714 1705 l cp
eoclip
n 1665 1575 m
 1800 2475 l gs col0 s gr gr

% arrowhead
n 1714 1705 m 1667 1591 l 1655 1714 l  col0 s
% Polyline
gs  clippath
2148 1570 m 2091 1550 l 2042 1694 l 2110 1591 l 2098 1714 l cp
eoclip
n 1800 2475 m
 2115 1575 l gs col0 s gr gr

% arrowhead
n 2098 1714 m 2110 1591 l 2042 1694 l  col0 s
% Polyline
gs  clippath
3171 1549 m 3116 1573 l 3178 1711 l 3157 1590 l 3233 1687 l cp
eoclip
n 3150 1575 m
 3555 2475 l gs col0 s gr gr

% arrowhead
n 3233 1687 m 3157 1590 l 3178 1711 l  col0 s
/Times-Roman ff 180.00 scf sf
405 630 m
gs 1 -1 sc (S1) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 900 m
gs 1 -1 sc (S2) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1125 m
gs 1 -1 sc (S3) col0 sh gr
/Times-Roman ff 180.00 scf sf
900 405 m
gs 1 -1 sc (1) col0 sh gr
/Times-Roman ff 180.00 scf sf
3870 405 m
gs 1 -1 sc (m) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 675 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 900 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1125 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1350 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1575 m
gs 1 -1 sc (ACGTTCTTTCTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1350 m
gs 1 -1 sc (S4) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1575 m
gs 1 -1 sc (S5) col0 sh gr
/Times-Roman ff 180.00 scf sf
1215 2655 m
gs 1 -1 sc (heterogeneous ) col0 sh gr
/Times-Roman ff 180.00 scf sf
1215 2895 m
gs 1 -1 sc (column equality) col0 sh gr
/Times-Roman ff 180.00 scf sf
3015 2655 m
gs 1 -1 sc (homogeneous ) col0 sh gr
/Times-Roman ff 180.00 scf sf
3015 2895 m
gs 1 -1 sc (column equality) col0 sh gr
$F2psEnd
rs

%%EndDocument
 @endspecial 2073 2756 a Fl(Figure)32 b(1.)g(Heter)n(og)q(eneous)f(and)
h(homog)q(eneous)2073 2856 y(columns)2073 3133 y Fm(W)-7
b(e)36 b(consider)d(the)h(second)f(possibility)h(through)e(a)j
(detailed)1974 3233 y(analysis)c(of)g(column)f(equalities.)58
b(T)-7 b(w)o(o)31 b(columns)f(in)i(an)f(align-)1974 3332
y(ment)24 b(are)g(equal)g(and)f(belong)g(to)h(the)h(same)f
Fr(column)f(class)i Fm(if,)h(on)1974 3432 y(a)e(sequence)f(by)h
(sequence)f(basis,)j(the)e(base)g(is)h(the)f(same.)37
b(A)25 b(ho-)1974 3532 y(mogeneous)k(column)h(consists)j(of)e(the)g
(same)h(base,)j(whereas)c(a)1974 3631 y(heterogeneous)24
b(column)i(consists)i(of)f(dif)n(ferent)f(bases)i(\(see)f(\002g-)1974
3731 y(ure)20 b(1\).)2073 3831 y(More)26 b(formally)-5
b(,)26 b(let)h Fk(s)2759 3843 y Fj(1)2797 3831 y Fk(;)14
b(:::;)g(s)2979 3843 y Fi(n)3051 3831 y Fm(be)26 b(the)h(set)g(of)f
(aligned)g(input)1974 3930 y(sequences)19 b(as)i(depicted)e(in)h(the)h
(upper)d(matrix)i(of)g(\002gure)f(2.)2073 4030 y(Let)j
Fk(m)f Fm(be)g(the)g(number)e(of)h(sequence)g(positions)g(of)h(the)g
(align-)1974 4129 y(ment.)34 b(W)-7 b(e)24 b(say)-5 b(,)23
b(that)h(tw)o(o)f(columns)f(of)h(the)h(input)e(data)h(set)h
Fk(i)g Fm(and)1974 4229 y Fk(j)32 b Fm(are)26 b(equal)g(if)h
Fu(8)p Fk(s)2539 4241 y Fi(k)2579 4229 y Fk(;)14 b(k)37
b Fh(=)e(1)p Fk(;)14 b(:::;)g(n)34 b Fh(:)g Fk(s)3161
4241 y Fi(k)q(i)3260 4229 y Fh(=)h Fk(s)3399 4241 y Fi(k)q(j)3470
4229 y Fm(,)29 b(where)d Fk(s)3789 4241 y Fi(k)q(j)3887
4229 y Fm(is)1974 4329 y(the)c Fk(j)5 b Fm(-th)22 b(position)g(of)g
(sequence)f Fk(k)s Fm(.)31 b(One)22 b(can)h(no)n(w)e(calculate)h(the)
1974 4428 y(number)d(of)i(equi)n(v)n(alent)e(columns)g(for)i(each)f
(column)g(class)i(of)e(the)1974 4528 y(input)f(data)h(set.)2073
4628 y(After)25 b(calculating)f(column)f(classes,)k(one)d(can)h
(compress)f(the)1974 4727 y(input)33 b(data)h(set)h(by)e(k)o(eeping)g
(a)h(single)g(representati)n(v)o(e)e(column)1974 4827
y(for)21 b(each)g(column)f(class,)j(remo)o(ving)c(the)j(equi)n(v)n
(alent)e(columns)g(of)1974 4926 y(the)30 b(speci\002c)g(class)h(and)e
(assigning)g(a)h(count)f(of)h(the)f(number)f(of)1974
5026 y(columns)21 b(the)h(selected)g(column)f(represents,)g(as)i
(depicted)e(in)h(\002g-)1974 5126 y(ure)e(2.)2073 5225
y(Since)35 b(a)g(necessary)f(prerequisite)f(for)h(a)h(phylogenetic)d
(tree)1974 5325 y(calculation)18 b(is)i(a)f(high-quality)d(multiple)j
(alignment)e(of)i(the)g(input)p eop
%%Page: 3 3
3 2 bop -182 1953 a @beginspecial 0 @llx 0 @lly 244 @urx
242 @ury 2362 @rwi @setspecial
%%BeginDocument: matrix2.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: matrix2.eps
%%Creator: /usr/local/dist/DIR/xfig-3.2.3c/bin/fig2dev Version 3.2 Patchlevel 3c
%%CreationDate: Thu Jun  6 15:56:16 2002
%%For: stamatak@sunbode13 (Alexandros Stamatakis)
%%BoundingBox: 0 0 244 242
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
newpath 0 242 moveto 0 0 lineto 244 0 lineto 244 242 lineto closepath clip newpath
-22.0 259.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
%%Page: 1 1
10 setmiterlimit
 0.06299 0.06299 sc
%
% Fig objects follow
%
% Polyline
7.500 slw
n 900 450 m 4050 450 l 4050 1575 l 900 1575 l
 cp gs col0 s gr 
% Polyline
n 900 2700 m 1665 2700 l 1665 3825 l 900 3825 l
 cp gs col0 s gr 
% Polyline
2 slj
gs  clippath
1226 2704 m 1283 2723 l 1332 2580 l 1265 2684 l 1275 2560 l cp
eoclip
n 2295 1575 m 2293 1577 l 2288 1583 l 2280 1593 l 2268 1607 l 2252 1626 l
 2232 1648 l 2210 1674 l 2186 1701 l 2161 1729 l 2136 1757 l
 2111 1783 l 2088 1808 l 2065 1830 l 2044 1851 l 2025 1869 l
 2006 1885 l 1988 1900 l 1971 1912 l 1954 1924 l 1937 1934 l
 1920 1943 l 1901 1951 l 1882 1959 l 1863 1966 l 1843 1973 l
 1822 1979 l 1801 1985 l 1779 1991 l 1757 1997 l 1735 2003 l
 1713 2009 l 1691 2015 l 1670 2022 l 1649 2030 l 1628 2038 l
 1609 2047 l 1590 2057 l 1572 2068 l 1555 2080 l 1538 2093 l
 1523 2108 l 1510 2121 l 1497 2136 l 1485 2152 l 1473 2171 l
 1461 2191 l 1448 2214 l 1435 2240 l 1422 2268 l 1409 2299 l
 1394 2333 l 1380 2369 l 1365 2408 l 1349 2449 l 1334 2490 l
 1319 2530 l 1305 2569 l 1293 2604 l 1282 2635 l 1274 2659 l

 1260 2700 l gs col0 s gr gr

% arrowhead
0 slj
n 1275 2560 m 1265 2684 l 1332 2580 l  col0 s
/Times-Roman ff 180.00 scf sf
405 630 m
gs 1 -1 sc (S1) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 900 m
gs 1 -1 sc (S2) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1125 m
gs 1 -1 sc (S3) col0 sh gr
/Times-Roman ff 180.00 scf sf
900 405 m
gs 1 -1 sc (1) col0 sh gr
/Times-Roman ff 180.00 scf sf
3870 405 m
gs 1 -1 sc (m) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 675 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 900 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1125 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1350 m
gs 1 -1 sc (ACGTTTTTTTTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 1575 m
gs 1 -1 sc (ACGTTCTTTCTGGGGGCCCCTTTTTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1350 m
gs 1 -1 sc (S4) col0 sh gr
/Times-Roman ff 180.00 scf sf
405 1575 m
gs 1 -1 sc (S5) col0 sh gr
/Times-Roman ff 180.00 scf sf
945 4050 m
gs 1 -1 sc (1,5,6,12,2) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 3825 m
gs 1 -1 sc (ACGTC) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 3600 m
gs 1 -1 sc (ACGTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 3375 m
gs 1 -1 sc (ACGTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 3150 m
gs 1 -1 sc (ACGTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 2925 m
gs 1 -1 sc (ACGTT) col0 sh gr
/Times-Roman ff 180.00 scf sf
360 3825 m
gs 1 -1 sc (S5) col0 sh gr
/Times-Roman ff 180.00 scf sf
360 3600 m
gs 1 -1 sc (S4) col0 sh gr
/Times-Roman ff 180.00 scf sf
360 3375 m
gs 1 -1 sc (S3) col0 sh gr
/Times-Roman ff 180.00 scf sf
360 3150 m
gs 1 -1 sc (S2) col0 sh gr
/Times-Roman ff 180.00 scf sf
360 2925 m
gs 1 -1 sc (S1) col0 sh gr
/Times-Roman ff 180.00 scf sf
990 2655 m
gs 1 -1 sc (1) col0 sh gr
/Times-Roman ff 180.00 scf sf
1530 2655 m
gs 1 -1 sc (5) col0 sh gr
/Times-Roman ff 180.00 scf sf
2070 4050 m
gs 1 -1 sc (column weights) col0 sh gr
/Times-Roman ff 180.00 scf sf
2205 2025 m
gs 1 -1 sc (compressing equal columns) col0 sh gr
$F2psEnd
rs

%%EndDocument
 @endspecial -83 2135 a Fl(Figure)75 b(2.)h(Global)e(compression)h(of)g
(equal)-83 2235 y(columns,)27 b(all)f(column)g(weights)f(are)i(1)f(in)g
(the)g(un\255)-83 2335 y(compressed)d(matrix)-182 2701
y Fm(sequences)30 b(one)g(might)g(e)o(xpect)g(quite)h(a)g(lar)o(ge)f
(number)g(of)g(col-)-182 2801 y(umn)19 b(equalities)i(on)f(a)h(global)f
(le)n(v)o(el.)26 b(In)20 b(f)o(act,)h(this)g(kind)e(of)i(global)-182
2900 y(data)26 b(compression)e(is)j(already)e(performed)e(by)j(most)g
(programs.)-182 3000 y(Unfortunately)-5 b(,)24 b(as)k(the)e(number)f
(of)h(aligned)g(sequences)g(gro)n(ws,)-182 3099 y(the)i(probability)f
(of)i(\002nding)f(tw)o(o)h(globally)e(equal)i(columns)e(de-)-182
3199 y(creases.)e(Ho)n(we)n(v)o(er)m(,)17 b(it)j(is)h(reasonable)d(to)i
(e)o(xpect)e(more)h(equalities)-182 3299 y(on)g(the)i(subtree,)e(or)h
(local,)g(le)n(v)o(el.)-83 3407 y(The)e(fundamental)d(idea)i(of)h(this)
g(paper)f(is)h(to)g(e)o(xtend)f(this)h(com-)-182 3506
y(pression)h(mechanism)f(to)i(the)f(subtree)g(le)n(v)o(el,)h(since)f(a)
h(lar)o(ge)f(num-)-182 3606 y(ber)25 b(of)g(column)g(equalities)g
(might)g(be)h(e)o(xpected)e(on)h(the)h(subtree)-182 3706
y(le)n(v)o(el.)d(Depending)14 b(on)h(the)h(size)h(of)e(the)h(subtree,)g
(fe)n(wer)g(sequences)-182 3805 y(ha)n(v)o(e)34 b(to)i(be)f(compared)e
(for)i(column)f(equality)g(and,)k(thus,)h(the)-182 3905
y(probability)18 b(of)i(\002nding)f(equal)g(columns)g(is)j(higher)-5
b(.)-83 4013 y(None)18 b(the)g(less,)i(we)e(restrain)g(the)g(analysis)h
(of)f(subtree)f(column)-182 4113 y(equality)g(to)i(homogeneous)d
(columns)i(for)g(the)g(follo)n(wing)g(reason:)-83 4221
y(The)25 b(calculation)g(of)g(heterogeneous)e(equality)h(v)o(ectors)h
(at)h(an)-182 4320 y(inner)c(node)g Fk(p)h Fm(is)i(comple)o(x)c(and)h
(requires)h(the)g(search)f(for)h Fk(c)1602 4290 y Fi(k)1666
4320 y Fm(dif-)-182 4420 y(ferent)29 b(column)g(equality)g(classes,)k
(where)d Fk(k)k Fm(is)d(the)f(number)e(of)-182 4520 y(tips)34
b(\(sequences\))d(in)j(the)f(subtree)g(of)g Fk(p)h Fm(and)f
Fk(c)h Fm(is)g(the)g(number)-182 4619 y(of)24 b(distinct)g(v)n(alues)g
(the)h(characters)e(of)i(the)f(sequence)f(alignment)-182
4719 y(are)32 b(mapped)g(to.)63 b(\(E.g.,)34 b Fq(fastDN)n(Aml)f
Fm(uses)h(15)e(dif)n(ferent)f(v)n(al-)-182 4818 y(ues.\))26
b(This)21 b(o)o(v)o(erhead)d(w)o(ould)i(not)g(amortize)g(well)h(o)o(v)o
(er)e(the)i(addi-)-182 4918 y(tional)i(column)f(equalities)h(we)h(w)o
(ould)e(obtain,)i(especially)f(when)-182 5018 y Fk(c)-146
4988 y Fi(k)-83 5018 y Fk(>)g(m)78 4988 y Fg(0)101 5018
y Fm(.)-83 5126 y(W)-7 b(e)34 b(no)n(w)e(describe)f(an)h(ef)n
(\002cient)g(and)g(easy)h(w)o(ay)f(for)g(recur)n(-)-182
5225 y(si)n(v)o(ely)27 b(calculating)f(subtree)h(column)f(equalities)i
(using)f(Subtree)-182 5325 y(Equality)19 b(V)-9 b(ectors)19
b(\(SEVs\).)2073 83 y(Let)29 b Fk(s)f Fm(be)g(the)g(virtual)f(root)g
(placed)g(in)h(an)g(unrooted)e(tree)i(for)1974 183 y(the)20
b(calculation)e(of)i(its)g(lik)o(elihood)f(v)n(alue.)24
b(Let)c Fk(p)g Fm(be)f(the)h(root)f(of)h(a)1974 282 y(subtree)h(with)h
(children)e Fk(q)26 b Fm(and)21 b Fk(r)r Fm(,)i(relati)n(v)o(e)e(to)h
Fk(s)p Fm(.)30 b(Let)22 b Fk(ev)p 3653 282 25 4 v 33
w(p)g Fm(\()p Fk(ev)p 3857 282 V 33 w(q)s Fm(,)1974 382
y Fk(ev)p 2061 382 V 33 w(r)r Fm(\))28 b(be)f(the)g(equality)f(v)o
(ector)g(of)h Fk(p)g Fm(\()p Fk(q)s Fm(,)i Fk(r)r Fm(,)h(respecti)n(v)o
(ely\),)d(with)1974 482 y(size)i Fk(m)2205 451 y Fg(0)2228
482 y Fm(,)h(where)e Fk(m)2584 451 y Fg(0)2636 482 y
Fm(is)h(the)f(length)f(of)h(the)g(compressed)f(global)1974
581 y(sequences.)46 b(The)27 b(v)n(alue)g(of)g(the)h(equality)e(v)o
(ector)g(for)h(node)g Fk(p)h Fm(at)1974 681 y(position)k
Fk(i)p Fm(,)j(where)d Fk(i)46 b Fh(=)f(1)p Fk(;)14 b(:::;)g(m)3039
651 y Fg(0)3095 681 y Fm(can)33 b(be)f(calculated)g(by)g(the)1974
780 y(follo)n(wing)18 b(function)h(\(see)h(e)o(xample)f(in)h(\002gure)g
(3\):)2076 1096 y Fk(ev)p 2163 1096 V 33 w(p)p Fh(\()p
Fk(i)p Fh(\))j(=)2434 979 y Ff(\032)2538 1045 y Fk(ev)p
2625 1045 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))84 b Fk(if)155
b(ev)p 3178 1045 V 33 w(q)s Fh(\()p Fk(i)p Fh(\))23 b(=)g
Fk(ev)p 3534 1045 V 33 w(r)r Fh(\()p Fk(i)p Fh(\))2538
1145 y Fu(\000)p Fh(1)221 b Fk(el)r(se)3846 1096 y Fm(\(1\))2073
1333 y(If)28 b Fk(p)g Fm(is)h(a)f(leaf,)h(we)g(set)f
Fk(ev)p 2884 1333 V 33 w(p)p Fh(\()p Fk(i)p Fh(\))37
b(:=)g Fk(map)p Fh(\()p Fk(seq)s(uence)p 3732 1333 V
28 w(p)p Fh(\()p Fk(i)p Fh(\)\))p Fm(,)1974 1432 y(where,)28
b Fk(map)p Fh(\(\))f Fm(is)h(a)g(function)d(that)i(maps)g(the)g
(character)e(repre-)1974 1532 y(sentation)e(of)g(the)h(aligned)f(input)
g(sequence)g Fk(seq)s(uence)p 3645 1532 V 28 w(p)h Fm(at)g(leaf)1974
1632 y Fk(p)32 b Fm(to)h(v)n(alues)f Fh(0)p Fk(;)14 b
Fh(1)p Fk(;)g(:::;)g(c)p Fm(.)60 b(Thus,)34 b(the)f(v)n(alues)e(of)h
(an)g(inner)g(SEV)1974 1731 y Fk(ev)p 2061 1731 V 33
w(p)p Fm(,)d(at)e(position)f Fk(i)p Fm(,)j(range)d(from)g
Fu(\000)p Fh(1)p Fk(;)14 b Fh(0)p Fk(;)g(:::;)g(c)p Fm(,)28
b(i.e.)45 b Fu(\000)p Fh(1)27 b Fm(if)h(col-)1974 1831
y(umn)e Fk(i)h Fm(is)g(heterogeneous)d(and)i(from)g Fh(0)p
Fk(;)14 b(:::;)g(c)26 b Fm(in)h(the)g(case)g(of)f(an)1974
1931 y(homogeneous)17 b(column.)2073 2032 y(F)o(or)i(SEV)g(v)n(alues)g
Fh(0)p Fk(;)14 b(:::;)g(c)19 b Fm(a)g(pointer)f(array)g
Fk(r)r(ef)p 3487 2032 V 39 w(p)p Fh(\()p Fk(c)p Fh(\))i
Fm(is)g(main-)1974 2131 y(tained,)c(which)g(is)h(initialized)f(with)h
Fk(N)9 b(U)g(LL)15 b Fm(pointers,)h(for)g(storing)1974
2231 y(the)25 b(references)f(to)i(the)f(\002rst)i(occurrence)c(of)i
(the)g(respecti)n(v)o(e)g(col-)1974 2330 y(umn)k(equality)h(class)h(in)
g(the)f(lik)o(elihood)f(v)o(ector)g(of)h(the)g(current)1974
2430 y(node)19 b Fk(p)p Fm(.)2073 2531 y(Thus,)27 b(if)f(the)g(v)n
(alue)f(of)h(the)g(equality)f(v)o(ector)g Fk(ev)p 3535
2531 V 32 w(p)p Fh(\()p Fk(j)5 b Fh(\))34 b Fk(>)g Fu(\000)p
Fh(1)1974 2631 y Fm(and)22 b Fk(r)r(ef)p 2250 2631 V
39 w(p)p Fh(\()p Fk(ev)p 2436 2631 V 33 w(p)p Fh(\()p
Fk(j)5 b Fh(\)\))28 b Fu(6)p Fh(=)g Fk(N)9 b(U)g(LL)22
b Fm(for)g(an)h(inde)o(x)e Fk(j)29 b Fm(of)22 b(the)h(lik)o(eli-)1974
2730 y(hood)17 b(v)o(ector)h Fk(l)r(v)p 2460 2730 V 32
w(p)p Fh(\()p Fk(j)5 b Fh(\))20 b Fm(of)e Fk(p)p Fm(,)i(the)e(v)n(alue)
h(for)f(the)g(speci\002c)h(homoge-)1974 2830 y(neous)24
b(column)g(equality)g(class)h Fk(ev)p 3034 2830 V 33
w(p)p Fh(\()p Fk(j)5 b Fh(\))26 b Fm(has)f(already)f(been)g(cal-)1974
2930 y(culated)16 b(for)h(an)f(inde)o(x)g Fk(i)23 b(<)g(j)f
Fm(and)16 b(a)i(lar)o(ge)e(block)g(of)h(\003oating)f(point)1974
3029 y(operations)30 b(can)h(be)g(replaced)f(by)h(a)h(simple)f(v)n
(alue)g(assignment)1974 3129 y Fk(l)r(v)p 2049 3129 V
32 w(p)p Fh(\()p Fk(j)5 b Fh(\))24 b(:=)e Fk(l)r(v)p
2427 3129 V 33 w(p)p Fh(\()p Fk(i)p Fh(\))p Fm(.)i(If)17
b Fk(ev)p 2792 3129 V 33 w(p)p Fh(\()p Fk(j)5 b Fh(\))23
b Fk(>)g Fu(\000)p Fh(1)16 b Fm(and)h Fk(r)r(ef)p 3467
3129 V 39 w(p)p Fh(\()p Fk(ev)p 3653 3129 V 32 w(p)p
Fh(\()p Fk(j)5 b Fh(\)\))24 b(=)1974 3229 y Fk(N)9 b(U)g(LL)p
Fm(,)60 b(we)53 b(assign)h Fk(r)r(ef)p 2856 3229 V 38
w(p)p Fh(\()p Fk(ev)p 3041 3229 V 33 w(p)p Fh(\()p Fk(j)5
b Fh(\)\))55 b Fm(to)e(the)g(address)f(of)1974 3328 y
Fk(l)r(v)p 2049 3328 V 32 w(p)p Fh(\()p Fk(j)5 b Fh(\))p
Fm(,)21 b(i.e.)k Fk(r)r(ef)p 2520 3328 V 39 w(p)p Fh(\()p
Fk(ev)p 2706 3328 V 33 w(p)p Fh(\()p Fk(j)5 b Fh(\)\))24
b(:=)e Fk(adr)r Fh(\()p Fk(l)r(v)p 3275 3328 V 34 w(p)p
Fh(\()p Fk(j)5 b Fh(\)\))p Fm(.)2073 3429 y(The)28 b(additional)e
(memory)g(required)f(for)i(equality)g(v)o(ectors)f(is)1974
3529 y Fk(O)r Fh(\()p Fk(n)18 b Fu(\003)e Fk(m)2270 3499
y Fg(0)2294 3529 y Fh(\))p Fm(.)25 b(The)20 b(additional)e(time)i
(required)e(for)h(calculating)g(the)1974 3628 y(equality)g(v)o(ectors)g
(is)j Fk(O)r Fh(\()p Fk(m)2768 3598 y Fg(0)2792 3628
y Fh(\))f Fm(at)f(e)n(v)o(ery)f(node.)2073 3730 y(The)32
b(initial)h(approach)d(renders)h(global)h(run)f(time)i(impro)o(v)o(e-)
1974 3829 y(ments)20 b(of)h(12\045)f(to)h(15\045.)26
b(These)21 b(result)g(from)e(an)i(acceleration)e(of)1974
3929 y(the)27 b(lik)o(elihood)e(e)n(v)n(aluation)g(function)g(between)h
(19\045)g(and)h(22\045,)1974 4028 y(which)f(in)h(turn)e(is)j(achie)n(v)
o(ed)d(by)h(a)h(reduction)d(in)j(the)g(number)d(of)1974
4128 y(\003oating)c(point)g(operations)g(between)g(23\045)g(and)h
(26\045)f(in)h(the)g(spe-)1974 4228 y(ci\002c)g(function.)2073
4329 y(It)e(is)h(important)c(to)j(note)f(that)h(the)f(initial)h
(optimization)e(is)i(only)1974 4428 y(applicable)j(to)i(the)g(lik)o
(elihood)e(e)n(v)n(aluation)g(function,)g(and)h Fr(not)i
Fm(to)1974 4528 y(the)g(branch)e(length)g(optimization)g(function.)37
b(This)25 b(limitation)f(is)1974 4628 y(due)h(to)g(the)h(f)o(act)g
(that)f(the)h(SEV)f(calculated)g(for)g(the)g Fr(virtual)h
Fm(root)1974 4727 y(placed)f(into)g(the)h(topology)d(under)h(e)n(v)n
(aluation,)h(at)h(either)f(end)g(of)1974 4827 y(the)d(branch)e(being)h
(optimized,)g(is)i(v)o(ery)d(sparse,)i(i.e.)31 b(has)22
b(fe)n(w)g(en-)1974 4926 y(tries)h Fk(>)28 b Fu(\000)p
Fh(1)p Fm(.)34 b(Therefore,)21 b(the)i(additional)f(o)o(v)o(erhead)e
(induced)i(by)1974 5026 y(SEV)i(calculation)f(does)h(not)g(amortize)f
(well)h(with)g(the)g(relati)n(v)o(ely)1974 5126 y(small)j(reduction)d
(in)j(the)f(number)f(of)h(\003oating)g(point)g(operations)1974
5225 y(\(2\045)d(-)h(7\045\).)34 b(Note)23 b(ho)n(we)n(v)o(er)m(,)e
(that)j(the)f(SEVs)h(of)f(the)g Fr(r)m(eal)h Fm(nodes)1974
5325 y(at)19 b(either)g(end)f(of)g(the)h(speci\002c)g(branch)f(do)g
(not)g(need)h(to)g(be)f(sparse,)p eop
%%Page: 4 4
4 3 bop -182 1812 a @beginspecial 0 @llx 0 @lly 415 @urx
382 @ury 2362 @rwi @setspecial
%%BeginDocument: sevadv.eps
%!PS-Adobe-2.0 EPSF-2.0
%%Title: sevadv.eps
%%Creator: /usr/local/dist/DIR/xfig-3.2.3c/bin/fig2dev Version 3.2 Patchlevel 3c
%%CreationDate: Mon Jun 10 14:24:30 2002
%%For: stamatak@sunbode13 (Alexandros Stamatakis)
%%BoundingBox: 0 0 415 382
%%Magnification: 1.0000
%%EndComments
/$F2psDict 200 dict def
$F2psDict begin
$F2psDict /mtrx matrix put
/col-1 {0 setgray} bind def
/col0 {0.000 0.000 0.000 srgb} bind def
/col1 {0.000 0.000 1.000 srgb} bind def
/col2 {0.000 1.000 0.000 srgb} bind def
/col3 {0.000 1.000 1.000 srgb} bind def
/col4 {1.000 0.000 0.000 srgb} bind def
/col5 {1.000 0.000 1.000 srgb} bind def
/col6 {1.000 1.000 0.000 srgb} bind def
/col7 {1.000 1.000 1.000 srgb} bind def
/col8 {0.000 0.000 0.560 srgb} bind def
/col9 {0.000 0.000 0.690 srgb} bind def
/col10 {0.000 0.000 0.820 srgb} bind def
/col11 {0.530 0.810 1.000 srgb} bind def
/col12 {0.000 0.560 0.000 srgb} bind def
/col13 {0.000 0.690 0.000 srgb} bind def
/col14 {0.000 0.820 0.000 srgb} bind def
/col15 {0.000 0.560 0.560 srgb} bind def
/col16 {0.000 0.690 0.690 srgb} bind def
/col17 {0.000 0.820 0.820 srgb} bind def
/col18 {0.560 0.000 0.000 srgb} bind def
/col19 {0.690 0.000 0.000 srgb} bind def
/col20 {0.820 0.000 0.000 srgb} bind def
/col21 {0.560 0.000 0.560 srgb} bind def
/col22 {0.690 0.000 0.690 srgb} bind def
/col23 {0.820 0.000 0.820 srgb} bind def
/col24 {0.500 0.190 0.000 srgb} bind def
/col25 {0.630 0.250 0.000 srgb} bind def
/col26 {0.750 0.380 0.000 srgb} bind def
/col27 {1.000 0.500 0.500 srgb} bind def
/col28 {1.000 0.630 0.630 srgb} bind def
/col29 {1.000 0.750 0.750 srgb} bind def
/col30 {1.000 0.880 0.880 srgb} bind def
/col31 {1.000 0.840 0.000 srgb} bind def

end
save
newpath 0 382 moveto 0 0 lineto 415 0 lineto 415 382 lineto closepath clip newpath
-36.0 415.0 translate
1 -1 scale

/cp {closepath} bind def
/ef {eofill} bind def
/gr {grestore} bind def
/gs {gsave} bind def
/sa {save} bind def
/rs {restore} bind def
/l {lineto} bind def
/m {moveto} bind def
/rm {rmoveto} bind def
/n {newpath} bind def
/s {stroke} bind def
/sh {show} bind def
/slc {setlinecap} bind def
/slj {setlinejoin} bind def
/slw {setlinewidth} bind def
/srgb {setrgbcolor} bind def
/rot {rotate} bind def
/sc {scale} bind def
/sd {setdash} bind def
/ff {findfont} bind def
/sf {setfont} bind def
/scf {scalefont} bind def
/sw {stringwidth} bind def
/tr {translate} bind def
/tnt {dup dup currentrgbcolor
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add
  4 -2 roll dup 1 exch sub 3 -1 roll mul add srgb}
  bind def
/shd {dup dup currentrgbcolor 4 -2 roll mul 4 -2 roll mul
  4 -2 roll mul srgb} bind def
/reencdict 12 dict def /ReEncode { reencdict begin
/newcodesandnames exch def /newfontname exch def /basefontname exch def
/basefontdict basefontname findfont def /newfont basefontdict maxlength dict def
basefontdict { exch dup /FID ne { dup /Encoding eq
{ exch dup length array copy newfont 3 1 roll put }
{ exch newfont 3 1 roll put } ifelse } { pop pop } ifelse } forall
newfont /FontName newfontname put newcodesandnames aload pop
128 1 255 { newfont /Encoding get exch /.notdef put } for
newcodesandnames length 2 idiv { newfont /Encoding get 3 1 roll put } repeat
newfontname newfont definefont pop end } def
/isovec [
8#055 /minus 8#200 /grave 8#201 /acute 8#202 /circumflex 8#203 /tilde
8#204 /macron 8#205 /breve 8#206 /dotaccent 8#207 /dieresis
8#210 /ring 8#211 /cedilla 8#212 /hungarumlaut 8#213 /ogonek 8#214 /caron
8#220 /dotlessi 8#230 /oe 8#231 /OE
8#240 /space 8#241 /exclamdown 8#242 /cent 8#243 /sterling
8#244 /currency 8#245 /yen 8#246 /brokenbar 8#247 /section 8#250 /dieresis
8#251 /copyright 8#252 /ordfeminine 8#253 /guillemotleft 8#254 /logicalnot
8#255 /hyphen 8#256 /registered 8#257 /macron 8#260 /degree 8#261 /plusminus
8#262 /twosuperior 8#263 /threesuperior 8#264 /acute 8#265 /mu 8#266 /paragraph
8#267 /periodcentered 8#270 /cedilla 8#271 /onesuperior 8#272 /ordmasculine
8#273 /guillemotright 8#274 /onequarter 8#275 /onehalf
8#276 /threequarters 8#277 /questiondown 8#300 /Agrave 8#301 /Aacute
8#302 /Acircumflex 8#303 /Atilde 8#304 /Adieresis 8#305 /Aring
8#306 /AE 8#307 /Ccedilla 8#310 /Egrave 8#311 /Eacute
8#312 /Ecircumflex 8#313 /Edieresis 8#314 /Igrave 8#315 /Iacute
8#316 /Icircumflex 8#317 /Idieresis 8#320 /Eth 8#321 /Ntilde 8#322 /Ograve
8#323 /Oacute 8#324 /Ocircumflex 8#325 /Otilde 8#326 /Odieresis 8#327 /multiply
8#330 /Oslash 8#331 /Ugrave 8#332 /Uacute 8#333 /Ucircumflex
8#334 /Udieresis 8#335 /Yacute 8#336 /Thorn 8#337 /germandbls 8#340 /agrave
8#341 /aacute 8#342 /acircumflex 8#343 /atilde 8#344 /adieresis 8#345 /aring
8#346 /ae 8#347 /ccedilla 8#350 /egrave 8#351 /eacute
8#352 /ecircumflex 8#353 /edieresis 8#354 /igrave 8#355 /iacute
8#356 /icircumflex 8#357 /idieresis 8#360 /eth 8#361 /ntilde 8#362 /ograve
8#363 /oacute 8#364 /ocircumflex 8#365 /otilde 8#366 /odieresis 8#367 /divide
8#370 /oslash 8#371 /ugrave 8#372 /uacute 8#373 /ucircumflex
8#374 /udieresis 8#375 /yacute 8#376 /thorn 8#377 /ydieresis] def
/Times-Roman /Times-Roman-iso isovec ReEncode
 /DrawEllipse {
        /endangle exch def
        /startangle exch def
        /yrad exch def
        /xrad exch def
        /y exch def
        /x exch def
        /savematrix mtrx currentmatrix def
        x y tr xrad yrad sc 0 0 1 startangle endangle arc
        closepath
        savematrix setmatrix
        } def

/$F2psBegin {$F2psDict begin /$F2psEnteredState save def} def
/$F2psEnd {$F2psEnteredState restore end} def

$F2psBegin
%%Page: 1 1
10 setmiterlimit
 0.06000 0.06000 sc
%
% Fig objects follow
%
7.500 slw
% Ellipse
n 3600 1800 106 106 0 360 DrawEllipse gs col7 0.00 shd ef gr gs col0 s gr

% Ellipse
n 5100 3600 106 106 0 360 DrawEllipse gs col7 0.00 shd ef gr gs col0 s gr

% Ellipse
n 2100 3600 106 106 0 360 DrawEllipse gs col7 0.00 shd ef gr gs col0 s gr

% Polyline
n 3600 1800 m
 5100 3600 l gs col0 s gr 
% Polyline
n 3600 1800 m
 2100 3600 l gs col0 s gr 
% Polyline
 [60] 0 sd
gs  clippath
2940 870 m 2892 906 l 2983 1027 l 2935 913 l 3031 991 l cp
eoclip
n 3600 1800 m
 2925 900 l gs col7 0.00 shd ef gr gs col0 s gr gr
 [] 0 sd
% arrowhead
n 3031 991 m 2935 913 l 2983 1027 l  col0 s
% Polyline
n 4800 1200 m 6600 1200 l 6600 1800 l 4800 1800 l
 cp gs col0 s gr 
% Polyline
n 1200 5400 m 2400 5400 l 2400 5700 l 1200 5700 l
 cp gs col0 s gr 
% Polyline
n 4200 5400 m 5400 5400 l 5400 5700 l 4200 5700 l
 cp gs col0 s gr 
% Polyline
gs  clippath
1380 4785 m 1320 4785 l 1320 4937 l 1350 4817 l 1380 4937 l cp
eoclip
n 1350 4800 m
 1350 5400 l gs col0 s gr gr

% arrowhead
n 1380 4937 m 1350 4817 l 1320 4937 l  col0 s
% Polyline
gs  clippath
2281 4810 m 2239 4768 l 2131 4875 l 2238 4812 l 2174 4918 l cp
eoclip
n 2250 4800 m
 1650 5400 l gs col0 s gr gr

% arrowhead
n 2174 4918 m 2238 4812 l 2131 4875 l  col0 s
% Polyline
gs  clippath
4380 4785 m 4320 4785 l 4320 4937 l 4350 4817 l 4380 4937 l cp
eoclip
n 4350 4800 m
 4350 5400 l gs col0 s gr gr

% arrowhead
n 4380 4937 m 4350 4817 l 4320 4937 l  col0 s
% Polyline
gs  clippath
4680 4785 m 4620 4785 l 4620 4937 l 4650 4817 l 4680 4937 l cp
eoclip
n 4650 4800 m
 4650 5400 l gs col0 s gr gr

% arrowhead
n 4680 4937 m 4650 4817 l 4620 4937 l  col0 s
% Polyline
n 4800 2400 m 6000 2400 l 6000 2700 l 4800 2700 l
 cp gs col0 s gr 
% Polyline
gs  clippath
4980 1785 m 4920 1785 l 4920 1937 l 4950 1817 l 4980 1937 l cp
eoclip
n 4950 1800 m
 4950 2400 l gs col0 s gr gr

% arrowhead
n 4980 1937 m 4950 1817 l 4920 1937 l  col0 s
% Polyline
gs  clippath
6179 1816 m 6145 1766 l 6019 1850 l 6136 1809 l 6052 1900 l cp
eoclip
n 6150 1800 m
 5250 2400 l gs col0 s gr gr

% arrowhead
n 6052 1900 m 6136 1809 l 6019 1850 l  col0 s
% Polyline
n 1200 4200 m 3000 4200 l 3000 4800 l 1200 4800 l
 cp gs col0 s gr 
% Polyline
n 4200 4200 m 6000 4200 l 6000 4800 l 4200 4800 l
 cp gs col0 s gr 
% Polyline
 [60] 0 sd
n 2100 3600 m
 1800 3975 l gs col0 s gr  [] 0 sd
% Polyline
 [60] 0 sd
n 2100 3600 m
 2400 3975 l gs col0 s gr  [] 0 sd
% Polyline
 [60] 0 sd
n 5100 3600 m
 4800 3975 l gs col0 s gr  [] 0 sd
% Polyline
 [60] 0 sd
n 5100 3600 m
 5400 3975 l gs col0 s gr  [] 0 sd
% Polyline
n 2805 6300 m 2700 6300 2700 6795 105 arcto 4 {pop} repeat
  2700 6900 3795 6900 105 arcto 4 {pop} repeat
  3900 6900 3900 6405 105 arcto 4 {pop} repeat
  3900 6300 2805 6300 105 arcto 4 {pop} repeat
 cp gs col0 s gr 
% Polyline
gs  clippath
2686 6630 m 2732 6592 l 2635 6475 l 2689 6587 l 2589 6514 l cp
eoclip
n 1950 5700 m
 2700 6600 l gs col0 s gr gr

% arrowhead
n 2589 6514 m 2689 6587 l 2635 6475 l  col0 s
% Polyline
gs  clippath
2762 6331 m 2807 6291 l 2707 6177 l 2764 6288 l 2662 6217 l cp
eoclip
n 2250 5700 m
 2775 6300 l gs col0 s gr gr

% arrowhead
n 2662 6217 m 2764 6288 l 2707 6177 l  col0 s
% Polyline
gs  clippath
3872 6281 m 3901 6333 l 4033 6258 l 3914 6292 l 4003 6206 l cp
eoclip
n 4950 5700 m
 3900 6300 l gs col0 s gr gr

% arrowhead
n 4003 6206 m 3914 6292 l 4033 6258 l  col0 s
% Polyline
gs  clippath
3870 6583 m 3904 6633 l 4030 6549 l 3914 6591 l 3997 6499 l cp
eoclip
n 5250 5700 m
 3900 6600 l gs col0 s gr gr

% arrowhead
n 3997 6499 m 3914 6591 l 4030 6549 l  col0 s
% Polyline
n 6405 3000 m 6300 3000 6300 3495 105 arcto 4 {pop} repeat
  6300 3600 7395 3600 105 arcto 4 {pop} repeat
  7500 3600 7500 3105 105 arcto 4 {pop} repeat
  7500 3000 6405 3000 105 arcto 4 {pop} repeat
 cp gs col0 s gr 
% Polyline
gs  clippath
6292 3332 m 6330 3285 l 6212 3191 l 6287 3290 l 6174 3238 l cp
eoclip
n 5550 2700 m
 6300 3300 l gs col0 s gr gr

% arrowhead
n 6174 3238 m 6287 3290 l 6212 3191 l  col0 s
% Polyline
gs  clippath
6602 3033 m 6625 2977 l 6484 2921 l 6585 2994 l 6462 2977 l cp
eoclip
n 5850 2700 m
 6600 3000 l gs col0 s gr gr

% arrowhead
n 6462 2977 m 6585 2994 l 6484 2921 l  col0 s
/Times-Roman-iso ff 240.00 scf sf
1275 4725 m
gs 1 -1 sc (v0           v1) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4275 4725 m
gs 1 -1 sc (v0 v1) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4275 4425 m
gs 1 -1 sc (0   1   0   0   1   1   ) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
1275 4425 m
gs 1 -1 sc (0   0   0   1   1   1) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4875 1425 m
gs 1 -1 sc (0  -1  0  -1  1   1) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
1275 5625 m
gs 1 -1 sc (0   1   2   3) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4275 5625 m
gs 1 -1 sc (0   1   2   3) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4875 2625 m
gs 1 -1 sc (0   1   2   3) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
2550 750 m
gs 1 -1 sc (towards root) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
675 4425 m
gs 1 -1 sc (ev_q) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6150 4425 m
gs 1 -1 sc (ev_r) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6150 4725 m
gs 1 -1 sc (lv_r) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6750 1425 m
gs 1 -1 sc (ev_p) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6750 1725 m
gs 1 -1 sc (lv_p) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
3000 6675 m
gs 1 -1 sc (NULL) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6525 3375 m
gs 1 -1 sc (NULL) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
3825 1875 m
gs 1 -1 sc (p) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
2325 3675 m
gs 1 -1 sc (q) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
5325 3675 m
gs 1 -1 sc (r) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
5550 5625 m
gs 1 -1 sc (ref_r) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
6150 2625 m
gs 1 -1 sc (ref_p) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
600 5625 m
gs 1 -1 sc (ref_q) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
675 4725 m
gs 1 -1 sc (lv_q) col0 sh gr
/Times-Roman-iso ff 240.00 scf sf
4800 1725 m
gs 1 -1 sc (v0  v1     v2  v3) col0 sh gr
/Times-Roman-iso ff 270.00 scf sf
3525 2625 m
gs 1 -1 sc (z\(p,r\)) col0 sh gr
/Times-Roman-iso ff 270.00 scf sf
2250 2625 m
gs 1 -1 sc (z\(p,q\)) col0 sh gr
$F2psEnd
rs

%%EndDocument
 @endspecial -83 1995 a Fl(Figure)35 b(3.)g(Example)h(likelihood\255,)h
(equality\255)d(and)-83 2094 y(ref)o(erence\255vector)23
b(computation)d(f)n(or)i(the)g(subtree)-83 2194 y(at)h(p)-182
2549 y Fm(this)30 b(depends)f(on)h(the)g(number)e(of)i(tips)h(in)f(the)
g(respecti)n(v)o(e)f(sub-)-182 2649 y(trees.)-83 2751
y(W)-7 b(e)24 b(no)n(w)e(sho)n(w)g(ho)n(w)g(to)g(ef)n(\002ciently)g(e)o
(xploit)f(the)h(information)-182 2851 y(pro)o(vided)15
b(by)i(an)h(SEV)-11 b(,)18 b(in)g(order)f(to)g(achie)n(v)o(e)g(a)h
(further)e(signi\002cant)-182 2950 y(reduction)k(in)j(the)g(number)d
(of)j(\003oating)f(point)f(operations)g(by)i(e)o(x-)-182
3050 y(tending)k(this)h(mechanism)f(to)i(the)f(branch)f(length)h
(optimization)-182 3150 y(function.)-83 3252 y(T)-7 b(o)32
b(mak)o(e)f(better)f(use)i(of)f(the)g(information)e(pro)o(vided)g(by)i
(an)-182 3352 y(SEV)e(at)g(an)g(inner)f(node)g Fk(p)h
Fm(with)g(children)f Fk(r)k Fm(and)c Fk(q)s Fm(,)k(it)d(is)h(suf)n
(\002-)-182 3451 y(cient)25 b(to)h(analyze)f(at)h(a)g(high)f(le)n(v)o
(el)g(ho)n(w)g(a)h(single)g(entry)f Fk(i)h Fm(of)f(the)-182
3551 y(lik)o(elihood)18 b(v)o(ector)h(at)i Fk(p)p Fm(,)f
Fk(l)r(v)p 640 3551 25 4 v 33 w(p)p Fh(\()p Fk(i)p Fh(\))p
Fm(,)g(is)h(calculated:)-92 3739 y Fk(l)r(v)p -17 3739
V 33 w(p)p Fh(\()p Fk(i)p Fh(\))i(=)f Fk(f)9 b Fh(\()p
Fk(g)s Fh(\()p Fk(l)r(v)p 485 3739 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))p Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))p
Fk(;)g(g)s Fh(\()p Fk(l)r(v)p 1124 3739 V 33 w(r)r Fh(\()p
Fk(i)p Fh(\))p Fk(;)g(z)t Fh(\()p Fk(p;)g(r)r Fh(\)\))p
Fk(;)92 b Fm(\(2\))-182 3927 y(where)36 b Fk(z)t Fh(\()p
Fk(p;)14 b(q)s Fh(\))37 b Fm(\()p Fk(z)t Fh(\()p Fk(p;)14
b(r)r Fh(\))p Fm(\))37 b(is)h(the)f(length)f(of)h(the)g(branch)e(from)
-182 4027 y Fk(p)e Fm(to)f Fk(q)k Fm(\()p Fk(p)d Fm(to)g
Fk(r)j Fm(respecti)n(v)o(ely\).)60 b(Function)31 b Fk(g)s
Fh(\(\))i Fm(is)h(a)f(computa-)-182 4127 y(tionally)e(e)o(xpensi)n(v)o
(e)g(function,)i(that)g(calculates)f(the)g(lik)o(elihood)-182
4226 y(of)c(the)g(left)h(and)f(the)g(right)g(branch)f(of)h
Fk(p)h Fm(respecti)n(v)o(ely)-5 b(,)28 b(depend-)-182
4326 y(ing)35 b(on)g(the)g(branch)f(lengths)h(and)f(the)i(v)n(alues)f
(of)g Fk(l)r(v)p 1473 4326 V 32 w(q)s Fh(\()p Fk(i)p
Fh(\))h Fm(and)-182 4426 y Fk(l)r(v)p -107 4426 V 32
w(r)r Fh(\()p Fk(i)p Fh(\))p Fm(,)29 b(whereas)c Fk(f)9
b Fh(\(\))26 b Fm(performs)e(some)i(simple)g(arithmetic)f(op-)-182
4525 y(erations)19 b(for)g(combining)f(the)i(results)h(of)f
Fk(g)s Fh(\()p Fk(l)r(v)p 1194 4525 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))p Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))20
b Fm(and)-182 4625 y Fk(g)s Fh(\()p Fk(l)r(v)p -32 4625
V 32 w(r)r Fh(\()p Fk(i)p Fh(\))p Fk(;)14 b(z)t Fh(\()p
Fk(p;)g(r)r Fh(\)\))44 b Fm(into)e(the)g(v)n(alue)g(of)g
Fk(l)r(v)p 1186 4625 V 32 w(p)p Fh(\()p Fk(i)p Fh(\))p
Fm(.)92 b(Note)42 b(that)-182 4724 y Fk(z)t Fh(\()p Fk(p;)14
b(q)s Fh(\))20 b Fm(and)g Fk(z)t Fh(\()p Fk(p;)14 b(r)r
Fh(\))21 b Fm(do)e(not)h(change)f(with)h Fk(i)p Fm(.)-83
4827 y(If)72 b(we)g(ha)n(v)o(e)f Fk(ev)p 527 4827 V 33
w(q)s Fh(\()p Fk(i)p Fh(\))119 b Fk(>)f Fu(\000)p Fh(1)72
b Fm(and)f Fk(ev)p 1445 4827 V 33 w(q)s Fh(\()p Fk(i)p
Fh(\))119 b(=)-182 4926 y Fk(ev)p -95 4926 V 32 w(q)s
Fh(\()p Fk(j)5 b Fh(\))p Fk(;)43 b(i)35 b(<)h(j)5 b Fm(,)29
b(we)f(ha)n(v)o(e)f Fk(l)r(v)p 774 4926 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))36 b(=)g Fk(l)r(v)p 1143 4926 V 33 w(q)s
Fh(\()p Fk(j)5 b Fh(\))28 b Fm(and)f(therefore)-182 5026
y Fk(g)s Fh(\()p Fk(l)r(v)p -32 5026 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))p Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))43
b(=)g Fk(g)s Fh(\()p Fk(l)r(v)p 721 5026 V 33 w(q)s Fh(\()p
Fk(j)5 b Fh(\))p Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))32
b Fm(\(the)f(same)g(equal-)-182 5126 y(ity)c(holds)g(for)g(node)g
Fk(r)r Fm(\).)47 b(Thus,)29 b(for)e(an)o(y)g(node)f Fk(q)31
b Fm(we)d(can)f(a)n(v)n(oid)-182 5225 y(the)c(recalculation)g(of)g
Fk(g)s Fh(\()p Fk(l)r(v)p 640 5225 V 33 w(q)s Fh(\()p
Fk(i)p Fh(\))p Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))24
b Fm(for)f(all)i Fk(j)34 b(>)c(i)p Fm(,)25 b(where)-182
5325 y Fk(ev)p -95 5325 V 32 w(q)s Fh(\()p Fk(j)5 b Fh(\))43
b(=)f Fk(ev)p 309 5325 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))h
Fk(>)e Fu(\000)p Fh(1)p Fm(.)55 b(W)-7 b(e)32 b(precalculate)d(those)h
(v)n(alues)1974 83 y(and)21 b(store)g(them)g(in)h(arrays)f
Fk(pr)r(ecal)r(c)p 3067 83 V 29 w(q)s Fh(\()p Fk(c)p
Fh(\))i Fm(and)e Fk(pr)r(ecal)r(c)p 3664 83 V 29 w(r)r
Fh(\()p Fk(c)p Fh(\))i Fm(re-)1974 183 y(specti)n(v)o(ely)-5
b(,)17 b(where)g Fk(c)i Fm(is)g(the)f(number)e(of)i(distinct)g
(character)n(-v)n(alue)1974 282 y(mappings)g(found)h(in)h(the)g
(sequence)g(alignment.)2073 382 y(Our)42 b(\002nal)g(optimization)e
(consists)i(in)g(the)g(elimination)e(of)1974 482 y(v)n(alue)17
b(assignments)h(of)g(type)g Fk(l)r(v)p 2920 482 V 32
w(q)s Fh(\()p Fk(i)p Fh(\))24 b(:=)e Fk(l)r(v)p 3286
482 V 33 w(q)s Fh(\()p Fk(j)5 b Fh(\))p Fm(,)19 b(for)f
Fk(ev)p 3697 482 V 33 w(q)s Fh(\()p Fk(i)p Fh(\))23 b(=)1974
581 y Fk(ev)p 2061 581 V 33 w(q)s Fh(\()p Fk(j)5 b Fh(\))23
b Fk(>)g Fu(\000)p Fh(1)p Fk(;)33 b(i)23 b(<)g(j)i Fm(where)20
b Fk(i)g Fm(is)h(the)f(\002rst)h(entry)e(for)g(a)i(speci\002c)1974
681 y(homogeneous)e(equality)j(class)h Fk(ev)p 3020 681
V 33 w(q)s Fh(\()p Fk(i)p Fh(\))28 b(=)f(0)p Fk(;)14
b(:::;)g(c)22 b Fm(in)h Fk(ev)p 3716 681 V 32 w(q)s Fm(.)33
b(W)-7 b(e)1974 780 y(need)17 b(not)h(assign)h(those)f(v)n(alues)g(due)
f(to)i(the)f(f)o(act)g(that)h Fk(l)r(v)p 3627 780 V 32
w(q)s Fh(\()p Fk(j)5 b Fh(\))19 b Fm(will)1974 880 y(ne)n(v)o(er)i(be)h
(accessed.)31 b(Instead,)22 b(since)g Fk(ev)p 3186 880
V 33 w(q)s Fh(\()p Fk(j)5 b Fh(\))28 b(=)e Fk(ev)p 3560
880 V 33 w(q)s Fh(\()p Fk(i)p Fh(\))h Fk(>)g Fu(\000)p
Fh(1)1974 980 y Fm(and)16 b(the)h(v)n(alue)f(of)g Fk(g)p
2559 980 V 33 w(q)s Fh(\()p Fk(j)5 b Fh(\))23 b(=)g Fk(g)p
2886 980 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))18 b Fm(has)f(been)f
(precalculated)f(and)1974 1079 y(stored)21 b(in)i Fk(pr)r(ecal)r(c)p
2555 1079 V 29 w(q)s Fh(\()p Fk(ev)p 2738 1079 V 33 w(p)p
Fh(\()p Fk(i)p Fh(\)\))p Fm(,)g(we)f(access)h Fk(l)r(v)p
3403 1079 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))g Fm(through)d(its)1974
1179 y(reference)e(in)j Fk(r)r(ef)p 2522 1179 V 39 w(q)s
Fh(\()p Fk(ev)p 2706 1179 V 33 w(q)s Fh(\()p Fk(i)p Fh(\)\))p
Fm(.)2073 1279 y(During)27 b(the)i(main)e(for)n(-loop)f(in)j(the)f
(calculation)f(of)h Fk(l)r(v)p 3751 1279 V 32 w(p)h Fm(we)1974
1378 y(ha)n(v)o(e)d(to)g(consider)f(6)i(cases,)h(depending)c(on)i(the)g
(v)n(alues)g(of)g Fk(ev)p 3878 1378 V 33 w(q)1974 1478
y Fm(and)32 b Fk(ev)p 2214 1478 V 32 w(r)r Fm(.)63 b(F)o(or)32
b(simplicity)g(we)g(will)h(write)g Fk(p)p 3415 1478 V
29 w(q)s Fh(\()p Fk(i)p Fh(\))g Fm(instead)f(of)1974
1577 y Fk(pr)r(ecal)r(c)p 2242 1577 V 29 w(q)s Fh(\()p
Fk(i)p Fh(\))21 b Fm(and)f Fk(g)p 2609 1577 V 32 w(q)s
Fh(\()p Fk(i)p Fh(\))h Fm(instead)f(of)g Fk(g)s Fh(\()p
Fk(l)r(v)p 3283 1577 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))p
Fk(;)14 b(z)t Fh(\()p Fk(p;)g(q)s Fh(\)\))p Fm(.)2178
2775 y Fk(l)r(v)p 2253 2775 V 33 w(p)p Fh(\()p Fk(i)p
Fh(\))23 b(:=)2546 1758 y Ff(8)2546 1833 y(>)2546 1858
y(>)2546 1883 y(>)2546 1908 y(>)2546 1933 y(>)2546 1957
y(>)2546 1982 y(>)2546 2007 y(>)2546 2032 y(>)2546 2057
y(>)2546 2082 y(>)2546 2107 y(>)2546 2132 y(>)2546 2157
y(>)2546 2182 y(>)2546 2207 y(>)2546 2231 y(>)2546 2256
y(>)2546 2281 y(>)2546 2306 y(>)2546 2331 y(>)2546 2356
y(>)2546 2381 y(>)2546 2406 y(>)2546 2431 y(>)2546 2456
y(>)2546 2481 y(>)2546 2505 y(>)2546 2530 y(>)2546 2555
y(>)2546 2580 y(>)2546 2605 y(>)2546 2630 y(>)2546 2655
y(>)2546 2680 y(<)2546 2829 y(>)2546 2854 y(>)2546 2879
y(>)2546 2904 y(>)2546 2929 y(>)2546 2954 y(>)2546 2979
y(>)2546 3004 y(>)2546 3028 y(>)2546 3053 y(>)2546 3078
y(>)2546 3103 y(>)2546 3128 y(>)2546 3153 y(>)2546 3178
y(>)2546 3203 y(>)2546 3228 y(>)2546 3253 y(>)2546 3278
y(>)2546 3302 y(>)2546 3327 y(>)2546 3352 y(>)2546 3377
y(>)2546 3402 y(>)2546 3427 y(>)2546 3452 y(>)2546 3477
y(>)2546 3502 y(>)2546 3527 y(>)2546 3552 y(>)2546 3576
y(>)2546 3601 y(>)2546 3626 y(>)2546 3651 y(>)2546 3676
y(:)2662 1828 y Fk(f)9 b Fh(\()p Fk(p)p 2791 1828 V 29
w(q)s Fh(\()p Fk(ev)p 2974 1828 V 33 w(q)s Fh(\()p Fk(i)p
Fh(\)\))p Fk(;)14 b(p)p 3248 1828 V 30 w(r)r Fh(\()p
Fk(ev)p 3431 1828 V 34 w(r)r Fh(\()p Fk(i)p Fh(\)\)\))2662
1928 y Fe(if)9 b Fk(ev)p 2814 1928 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))24 b(=)e Fk(ev)p 3169 1928 V 33 w(r)r Fh(\()p
Fk(i)p Fh(\))i Fk(>)f Fu(\000)p Fh(1)p Fk(;)2662 2027
y(r)r(ef)p 2795 2027 V 39 w(p)p Fh(\()p Fk(ev)p 2981
2027 V 33 w(r)r Fh(\()p Fk(i)p Fh(\)\))h(=)e Fk(N)9 b(U)g(LL)2662
2226 y(sk)s(ip)2662 2326 y Fe(if)g Fk(ev)p 2814 2326
V 32 w(q)s Fh(\()p Fk(i)p Fh(\))24 b(=)e Fk(ev)p 3169
2326 V 33 w(r)r Fh(\()p Fk(i)p Fh(\))i Fk(>)f Fu(\000)p
Fh(1)p Fk(;)2662 2426 y(r)r(ef)p 2795 2426 V 39 w(p)p
Fh(\()p Fk(ev)p 2981 2426 V 33 w(r)r Fh(\()p Fk(i)p Fh(\)\))h
Fu(6)p Fh(=)e Fk(N)9 b(U)g(LL)2662 2625 y(f)g Fh(\()p
Fk(p)p 2791 2625 V 29 w(q)s Fh(\()p Fk(ev)p 2974 2625
V 33 w(q)s Fh(\()p Fk(i)p Fh(\)\))p Fk(;)14 b(p)p 3248
2625 V 30 w(r)r Fh(\()p Fk(ev)p 3431 2625 V 34 w(r)r
Fh(\()p Fk(i)p Fh(\)\)\))2662 2725 y Fe(if)9 b Fk(ev)p
2814 2725 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))24 b Fu(6)p
Fh(=)e Fk(ev)p 3169 2725 V 33 w(r)r Fh(\()p Fk(i)p Fh(\))p
Fk(;)2662 2824 y(ev)p 2749 2824 V 33 w(q)s Fh(\()p Fk(i)p
Fh(\))p Fk(;)14 b(ev)p 3031 2824 V 32 w(r)r Fh(\()p Fk(i)p
Fh(\))24 b Fk(>)f Fu(\000)p Fh(1)2662 3023 y Fk(f)9 b
Fh(\()p Fk(p)p 2791 3023 V 29 w(q)s Fh(\()p Fk(ev)p 2974
3023 V 33 w(q)s Fh(\()p Fk(i)p Fh(\)\))p Fk(;)14 b(g)p
3249 3023 V 33 w(r)r Fh(\()p Fk(i)p Fh(\)\))2662 3123
y Fe(if)9 b Fk(ev)p 2814 3123 V 32 w(q)s Fh(\()p Fk(i)p
Fh(\))24 b Fk(>)e Fu(\000)p Fh(1)p Fk(;)14 b(ev)p 3313
3123 V 32 w(r)r Fh(\()p Fk(i)p Fh(\))24 b(=)f Fu(\000)p
Fh(1)2662 3322 y Fk(f)9 b Fh(\()p Fk(g)p 2792 3322 V
32 w(q)s Fh(\()p Fk(i)p Fh(\))p Fk(;)14 b(p)p 3033 3322
V 30 w(r)r Fh(\()p Fk(ev)p 3216 3322 V 34 w(r)r Fh(\()p
Fk(i)p Fh(\)\)\))2662 3422 y Fe(if)9 b Fk(ev)p 2814 3422
V 32 w(r)r Fh(\()p Fk(i)p Fh(\))24 b Fk(>)f Fu(\000)p
Fh(1)p Fk(;)14 b(ev)p 3313 3422 V 32 w(q)s Fh(\()p Fk(i)p
Fh(\))23 b(=)g Fu(\000)p Fh(1)2662 3621 y Fk(f)9 b Fh(\()p
Fk(g)p 2792 3621 V 32 w(q)s Fh(\()p Fk(i)p Fh(\))p Fk(;)14
b(g)p 3034 3621 V 33 w(r)r Fh(\()p Fk(i)p Fh(\)\))2662
3721 y Fe(if)9 b Fk(ev)p 2814 3721 V 32 w(q)s Fh(\()p
Fk(i)p Fh(\))24 b(=)e Fu(\000)p Fh(1)p Fk(;)14 b(ev)p
3313 3721 V 32 w(r)r Fh(\()p Fk(i)p Fh(\))24 b(=)f Fu(\000)p
Fh(1)3846 2775 y Fm(\(3\))2073 3889 y(A)34 b(simple)f(e)o(xample)f(for)
g(the)h(optimized)f(lik)o(elihood)f(v)o(ector)1974 3988
y(calculation)f(and)h(the)g(respecti)n(v)o(e)f(data-types)h(used)g(is)h
(gi)n(v)o(en)e(in)1974 4088 y(\002gure)19 b(3.)1974 4316
y Fs(3.)24 b(Implementation)2073 4528 y Fm(W)-7 b(e)30
b(inte)o(grated)e(subtree)g(equality)g(v)o(ectors)f(into)i(three)f(e)o
(xist-)1974 4628 y(ing)17 b(phylogen)o(y)c(programs:)22
b Fq(fastDN)n(Aml)17 b Fm([6)o(],)h Fq(fastDN)n(AmlP)f
Fm([7)o(])1974 4727 y(and)45 b Fq(T)-6 b(rExML)46 b Fm([13)o(].)100
b(W)-7 b(e)46 b(name)f(the)g(optimized)f(v)o(ersions)1974
4827 y Fq(AxML)p Fm(,)29 b Fq(P)-6 b(AxML)29 b Fm(and)g
Fq(A)-8 b(T)i(rExML)30 b Fm(respecti)n(v)o(ely)-5 b(.)49
b(About)28 b(300)1974 4926 y(lines)19 b(of)g(code)f(ha)n(v)o(e)h(been)f
(added)g(to)h(the)g(v)n(arious)f(programs,)f(thus)1974
5026 y(demonstrating)f(the)j(ef)n(\002cienc)o(y)-5 b(,)17
b(simplicity)i(and)f(applicability)f(of)1974 5126 y(our)i(approach.)
2073 5225 y(A)28 b(simple)g(analysis)f(of)h Fq(fastDN)n(Aml)f
Fm(with)h(the)f Fd(gprof)g Fm(tool)1974 5325 y(sho)n(ws)32
b(that)h(the)g(tree)f(lik)o(elihood)f(function)g Fd(newview\(\))h
Fm(and)p eop
%%Page: 5 5
5 4 bop -182 83 a Fm(the)47 b(branch)f(length)g(optimization)g
(function)f Fd(makenewz\(\))-182 183 y Fm(consume)53
b(o)o(v)o(er)g(95\045)i(of)f(o)o(v)o(erall)g(e)o(x)o(ecution)e(time.)
129 b(The)-182 282 y(basic)55 b(ideas)g(of)g(this)h(paper)e(ha)n(v)o(e)
g(been)h(implemented)e(in)-182 382 y(functions)45 b Fd(newview\(\))p
Fm(,)52 b Fd(makenewz\(\))p Fm(,)g Fd(sigma\(\))46 b
Fm(and)-182 482 y Fd(evaluate\(\))p Fm(,)17 b(since)j(those)e
(functions)g(access)i(the)f(lik)o(elihood-)-182 581 y(v)o(ectors)c(of)g
(the)h(nodes)f(and)h(are)f(af)n(fected)g(by)h(the)g(changes)f(induced)
-182 681 y(by)32 b(skipping)g(assignments)g(of)h(type)f
Fk(l)r(v)p 1047 681 25 4 v 33 w(p)p Fh(\()p Fk(i)p Fh(\))46
b(=)h Fk(l)r(v)p 1440 681 V 32 w(p)p Fh(\()p Fk(j)5 b
Fh(\))p Fk(;)14 b(i)47 b(<)-182 780 y(j;)14 b(ev)p -24
780 V 33 w(p)p Fh(\()p Fk(j)5 b Fh(\))23 b(=)g Fk(ev)p
344 780 V 32 w(p)p Fh(\()p Fk(i)p Fh(\))g Fk(>)g Fu(\000)p
Fh(1)p Fm(.)-83 881 y(In)e(each)f(of)h(those)f(functions)g(the)g(main)h
(for)n(-loop)d(o)o(v)o(er)i(the)h(se-)-182 981 y(quence)e(length)h
Fk(m)376 950 y Fg(0)421 981 y Fm(has)h(been)g(modi\002ed)e(in)j(order)d
(to)i(correspond)-182 1080 y(to)j(formula)f(3)i(and)e(the)i(code)f(for)
f(calculating)h(the)g(equality)g(v)o(ec-)-182 1180 y(tor)d(v)n(alues)g
(has)h(been)f(added.)28 b(Furthermore,)20 b(an)h(additional)g(loop)-182
1280 y(for)h(initializing)h Fk(pr)r(ecal)r(c)p 590 1280
V 29 w(q)s Fh(\()p Fk(c)p Fh(\))i Fm(and)d Fk(pr)r(ecal)r(c)p
1190 1280 V 30 w(r)r Fh(\()p Fk(c)p Fh(\))j Fm(has)e(been)g(in-)-182
1379 y(serted.)-83 1480 y(The)g(remaining)e(modi\002cations)g(concern)g
(initialization)h(mat-)-182 1579 y(ters,)34 b(and)d(the)g(de\002nition)
f(of)h(a)h(fe)n(w)f(additional)f(data-types)h(for)-182
1679 y(storing)19 b(the)h Fk(pr)r(ecal)r(c)p Fh(\(\))h
Fm(and)e Fk(r)r(ef)9 b Fh(\(\))22 b Fm(array)d(information.)-182
1914 y Fs(4)o(.)25 b(Adaptation)h(to)f(the)g(Hitachi)g(SR8000-F1)-83
2133 y Fm(F)o(or)30 b(initial)g(testing)f(on)h(the)f(Hitachi)h
(SR8000-F1)e(we)i(chose)-182 2233 y(to)24 b(use)g(inter)n(-node)d(MPI,)
j(i.e.)g(all)g(8)g(processors)f(forming)f(part)h(of)-182
2332 y(one)k(shared)g(memory)f(node,)i(are)g(used)f(independently)e
(and)i(are)-182 2432 y(assigned)19 b(one)h(MPI)g(process)g(each.)-83
2533 y(The)38 b(\002rst)g(tests)h(in)f(this)g(con\002guration)d
(rendered)g(less)k(im-)-182 2632 y(pressi)n(v)o(e)48
b(results)h(in)h(terms)f(of)g(run)f(time)h(impro)o(v)o(ement)d(of)-182
2732 y Fq(P)-6 b(AxML)30 b Fm(o)o(v)o(er)f Fq(fastDN)n(Aml)p
Fm(,)k(compared)c(with)h(the)h(results)g(ob-)-182 2831
y(tained)40 b(on)g(con)m(v)o(entional)e(processor)i(architectures)g
(\(see)h(sec-)-182 2931 y(tion)36 b(5\).)74 b(The)36
b(problem)f(could)g(ho)n(we)n(v)o(er)g(be)h(quickly)g(identi-)-182
3031 y(\002ed.)24 b(The)19 b(case)h(analysis)g(of)f(formula)f(3)h(has)h
(originally)d(been)i(im-)-182 3130 y(plemented)25 b(within)i(the)h
(computationally)c(e)o(xpensi)n(v)o(e)i(for)n(-loops)-182
3230 y(of)f(functions)f Fd(newview\(\))p Fm(,)i Fd(makenewz\(\))p
Fm(,)g Fd(sigma\(\))e Fm(and)-182 3330 y Fd(evaluate\(\))29
b Fm(as)i(nested)g(conditional)e(statement.)56 b(This)31
b(im-)-182 3429 y(plementation)23 b(scales)k(well)f(on)g(con)m(v)o
(entional)c(architectures)j(b)n(ut)-182 3529 y(in)18
b(contrast)f(signi\002cantly)g(perturbs)f(the)i(pipelining)e(and)h
(prefetch)-182 3628 y(mechanisms)i(of)h(Hitachi')-5 b(s)20
b(hardw)o(are)f(architecture.)-83 3729 y(Therefore,)39
b(we)f(split)f(up)g(the)g(for)n(-loops)e(within)i(the)g(func-)-182
3829 y(tions)18 b(mentioned)f(abo)o(v)o(e,)g(and)h(implemented)f(a)i
(distinct)g(for)n(-loop)-182 3928 y(for)24 b(each)h(case,)h(thus)f(a)n
(v)n(oiding)f(further)g(conditional)f(statements)-182
4028 y(within)30 b(the)g(respecti)n(v)o(e)g(loops.)55
b(W)-7 b(e)31 b(inserted)f(a)h(precalculation)-182 4128
y(step)19 b(where)f(the)h(equality)e(v)o(ector)h(v)n(alues)g(are)h
(computed)e(and)h(cal-)-182 4227 y(culate)27 b(at)h(the)g(same)f(time)h
(a)g(reference)e(array)h(for)g(each)g(distinct)-182 4327
y(case)21 b(in)f(3.)26 b(In)20 b(addition)f(to)i(this,)g(the)f(number)f
(of)h(entries)g(for)g(each)-182 4426 y(case)26 b(is)h(counted,)e(such)h
(that)g(a)h(distinct)f(for)n(-loop)e(for)h(each)g(case)-182
4526 y(can)17 b(be)g(constructed,)f(which)g(accesses)i(the)f(lik)o
(elihood)f(v)o(ector)g(via)-182 4626 y(its)21 b(respecti)n(v)o(e)e
(reference)f(array)-5 b(.)-83 4726 y(This)31 b(modi\002cation)d
(boosted)h(program)f(ef)n(\002cienc)o(y)-5 b(,)31 b(both,)h(in)-182
4826 y(terms)19 b(of)g(\003oating)f(point)h(performance)d(and)j(run)g
(time)g(reduction,)-182 4926 y(although)c(some)i(additional)f(code)h
(had)g(to)g(be)g(inserted)g(for)g(precal-)-182 5025 y(culating)27
b(the)g(loop)g(split)i(and)e(accessing)h(the)g(lik)o(elihood)e(v)o
(ector)-182 5125 y(through)18 b(reference)g(arrays.)-83
5225 y(E.g.)24 b(the)17 b(non-adapted)d Fq(P)-6 b(AxML)17
b Fm(code)f(rendered)f(25.47\045)h(run)-182 5325 y(time)27
b(impro)o(v)o(ement)d(compared)h(with)i(34.71\045)f(for)g(the)h
(adapted)1974 83 y(one)22 b(with)i(the)f(41)f(taxa)h(mitochondrial)e
(rRN)m(A)i(test)h(set)g(e)o(x)o(ecuted)1974 183 y(on)c(tw)o(o)g(w)o
(ork)o(ers)g(\(see)g(section)g(5\).)1974 417 y Fs(5.)k(Results)2073
635 y Fm(The)30 b(amount)f(of)h(performance)d(impro)o(v)o(ement)g
(strongly)i(de-)1974 734 y(pends)23 b(on)g(the)g(number)f(and)h(length)
g(of)g(the)g(input)g(sequences,)g(as)1974 834 y(well)d(as)g(the)f
(quality)g(of)g(the)h(alignment.)j(W)-7 b(e)21 b(note)e(that)g(whene)n
(v)o(er)1974 934 y(more)24 b(subtree)h(column)e(equalities)i(are)h(e)o
(xpected,)e(performance)1974 1033 y(impro)o(v)o(es)18
b(more.)24 b(W)-7 b(e)22 b(establish)e(tw)o(o)g(general)f(rules:)2036
1201 y(1.)41 b(Performance)30 b(impro)o(v)o(es)g(with)i(the)g(quality)f
(of)h(the)g(align-)2140 1301 y(ment.)2036 1469 y(2.)41
b(Performance)47 b(impro)o(v)o(es)g(with)i(the)g(length)g(of)g(the)g
(se-)2140 1569 y(quences.)2073 1737 y(W)-7 b(e)32 b(initially)e
(present)g(the)h(results)f(and)g(tests)i(performed)c(on)1974
1836 y(con)m(v)o(entional)23 b(architectures)i(and)h(report)f(about)h
(\002rst)h(results)g(on)1974 1936 y(the)20 b(Hitachi)g(SR8000-F1)f(at)i
(the)f(end)f(of)h(this)h(section.)2073 2136 y(W)-7 b(e)47
b(tested)f(the)f(performance)d(of)j Fq(AxML)p Fm(,)h
Fq(P)-6 b(AxML)46 b Fm(and)1974 2235 y Fq(A)-8 b(T)i(rExML)17
b Fm(with)f(data)g(sets)h(from)d(v)n(arious)h(sources)g(and)h(obtained)
1974 2335 y(global)22 b(run)g(time)i(impro)o(v)o(ements)c(between)i
(35\045)h(and)g(47\045.)33 b(W)-7 b(e)1974 2435 y(compiled)19
b(the)j(sequential)e(programs)f(with)i Fd(gcc)50 b(-O3)21
b Fm(and)f(e)o(x)o(e-)1974 2534 y(cuted)d(them)g(under)f
Fd(Solaris)h Fm(on)g(a)h Fd(Sun-Blade-1000)p Fm(.)k(F)o(or)1974
2634 y(the)29 b(parallel)f(programs)g(we)h(used)g Fd(gcc)49
b(-O2)29 b Fm(with)g(the)g(master)1974 2733 y(and)18
b(foreman)e(components)h(located)g(on)h(a)h Fd(Sun-Blade-1000)1974
2833 y Fm(and)g(tw)o(o)i(w)o(ork)o(ers,)e(each)h(running)e(on)i(a)g
Fd(Sun)50 b(Ultra)f(5/10)p Fm(.)2073 2933 y(F)o(or)173
b(analyzing)d(the)j(global)e(run)h(time)1974 3033 y(impro)o(v)o(ement)
255 b(of)j Fq(AxML/P)-6 b(AxML)259 b Fm(o)o(v)o(er)1974
3133 y Fq(fastDN)n(Aml/fastDN)n(AmlP)66 b Fm(tests)i(with)f(data-sets)g
(of)g(20,)1974 3232 y(30,)28 b(40)e(and)h(50)g(taxa)f(\(sequence)g
(length:)38 b(840\))26 b(e)o(xtracted)f(from)1974 3332
y(the)20 b(alignment)f(of)h(56)g(sequences)f(deli)n(v)o(ered)g(as)i
(the)f(test-set)h(with)1974 3431 y Fd(fastDNAmlP)p Fm(,)37
b(as)i(well)h(as)f(tw)o(o)g(alignments)e(consisting)h(of)1974
3531 y(161)19 b(mitochondrial)e(rRN)m(A)j(sequences)f(\(sequence)f
(length:)24 b(511\))1974 3631 y(from)j(beetles)h(and)f(b)n
(utter\003ies)h(were)g(used.)47 b(W)-7 b(e)29 b(used)f(dif)n(ferent)
1974 3730 y(program)21 b(options)h(and)h(data-sizes)g(for)f
(demonstrating)f(the)i(scal-)1974 3830 y(ability)g(and)f(generality)g
(of)g(our)h(method.)32 b(In)22 b(table)h(1)g(we)h(present)1974
3930 y(the)29 b(global)g(run)f(time)i(impro)o(v)o(ement)c(of)j
Fq(AxML/P)-6 b(AxML)30 b Fm(o)o(v)o(er)1974 4029 y Fq(fastDN)n
(Aml/fastDN)n(AmlP)p Fm(,)35 b(both)h(with)h(the)f(quickadd)f(\(local)
1974 4129 y(branch)c(length)h(optimization\))f(option)g(enabled)h(and)g
(disabled.)1974 4228 y(F)o(or)38 b(the)g(mitochondrial)e(rRN)m(A)i
(test)i(sets)f(we)g(e)o(x)o(ecuted)d(tests)1974 4328
y(with)31 b(and)f(without)f(tree)i(rearrangements)d(\(for)h(details)i
(refer)f(to)1974 4428 y(the)20 b Fq(fastDN)n(Aml)g Fm(documentation\).)
2073 4528 y(Results)i(for)d(the)h(20)g(to)g(50)g(taxa)g(sequential)f
(test)i(runs)f(are)g(also)1974 4628 y(depicted)d(in)i(\002gure)e(4.)25
b(An)18 b(important)f(result)h(is)h(that)g Fq(AxML)g
Fm(with)1974 4727 y(the)25 b(quickadd)e(option)h(disabled,)h(still)i
(runs)d(about)g(15\045)h(to)g(20\045)1974 4827 y(f)o(aster)j(than)f
Fq(fastDN)n(Aml)h Fm(with)g(the)f(quickadd)f(option)h(enabled,)1974
4926 y(thus)33 b(ensuring)e(a)i(higher)f(tree)g(quality)-5
b(.)62 b(Furthermore,)33 b(the)g(al-)1974 5026 y(gorithmic)23
b(optimizations)g(scale)i(well)g(to)f Fq(P)-6 b(AxML)p
Fm(,)25 b(e)n(v)o(en)f(in)g(the)1974 5126 y(case)i(of)f(considerably)e
(small)j(test)g(sets)h(for)d(a)i(parallel)f(run)g(as)h(in)1974
5225 y(the)f(case)h(of)f(the)g(20)g(to)g(50)g(taxa)g(test)h(set.)41
b(The)25 b(results)h(obtained)1974 5325 y(from)i(the)h(161)f(taxa)h
(tests)i(demonstrate)c(the)i(scalability)g(of)g(our)p
eop
%%Page: 6 6
6 5 bop -182 0 a
 gsave currentpoint currentpoint translate 270 neg rotate neg exch
neg exch translate
 -182 0 a @beginspecial 50 @llx 50 @lly
554 @urx 770 @ury 4950 @rhi @setspecial
%%BeginDocument: sp.ps
%!PS-Adobe-2.0
%%Title: sp.ps
%%Creator: gnuplot 3.7 patchlevel 1
%%CreationDate: Fri Apr 19 10:34:00 2002
%%DocumentFonts: (atend)
%%BoundingBox: 50 50 554 770
%%Orientation: Landscape
%%Pages: (atend)
%%EndComments
/gnudict 256 dict def
gnudict begin
/Color false def
/Solid false def
/gnulinewidth 5.000 def
/userlinewidth gnulinewidth def
/vshift -46 def
/dl {10 mul} def
/hpt_ 31.5 def
/vpt_ 31.5 def
/hpt hpt_ def
/vpt vpt_ def
/M {moveto} bind def
/L {lineto} bind def
/R {rmoveto} bind def
/V {rlineto} bind def
/vpt2 vpt 2 mul def
/hpt2 hpt 2 mul def
/Lshow { currentpoint stroke M
  0 vshift R show } def
/Rshow { currentpoint stroke M
  dup stringwidth pop neg vshift R show } def
/Cshow { currentpoint stroke M
  dup stringwidth pop -2 div vshift R show } def
/UP { dup vpt_ mul /vpt exch def hpt_ mul /hpt exch def
  /hpt2 hpt 2 mul def /vpt2 vpt 2 mul def } def
/DL { Color {setrgbcolor Solid {pop []} if 0 setdash }
 {pop pop pop Solid {pop []} if 0 setdash} ifelse } def
/BL { stroke userlinewidth 2 mul setlinewidth } def
/AL { stroke userlinewidth 2 div setlinewidth } def
/UL { dup gnulinewidth mul /userlinewidth exch def
      10 mul /udl exch def } def
/PL { stroke userlinewidth setlinewidth } def
/LTb { BL [] 0 0 0 DL } def
/LTa { AL [1 udl mul 2 udl mul] 0 setdash 0 0 0 setrgbcolor } def
/LT0 { PL [] 1 0 0 DL } def
/LT1 { PL [4 dl 2 dl] 0 1 0 DL } def
/LT2 { PL [2 dl 3 dl] 0 0 1 DL } def
/LT3 { PL [1 dl 1.5 dl] 1 0 1 DL } def
/LT4 { PL [5 dl 2 dl 1 dl 2 dl] 0 1 1 DL } def
/LT5 { PL [4 dl 3 dl 1 dl 3 dl] 1 1 0 DL } def
/LT6 { PL [2 dl 2 dl 2 dl 4 dl] 0 0 0 DL } def
/LT7 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 1 0.3 0 DL } def
/LT8 { PL [2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 2 dl 4 dl] 0.5 0.5 0.5 DL } def
/Pnt { stroke [] 0 setdash
   gsave 1 setlinecap M 0 0 V stroke grestore } def
/Dia { stroke [] 0 setdash 2 copy vpt add M
  hpt neg vpt neg V hpt vpt neg V
  hpt vpt V hpt neg vpt V closepath stroke
  Pnt } def
/Pls { stroke [] 0 setdash vpt sub M 0 vpt2 V
  currentpoint stroke M
  hpt neg vpt neg R hpt2 0 V stroke
  } def
/Box { stroke [] 0 setdash 2 copy exch hpt sub exch vpt add M
  0 vpt2 neg V hpt2 0 V 0 vpt2 V
  hpt2 neg 0 V closepath stroke
  Pnt } def
/Crs { stroke [] 0 setdash exch hpt sub exch vpt add M
  hpt2 vpt2 neg V currentpoint stroke M
  hpt2 neg 0 R hpt2 vpt2 V stroke } def
/TriU { stroke [] 0 setdash 2 copy vpt 1.12 mul add M
  hpt neg vpt -1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt 1.62 mul V closepath stroke
  Pnt  } def
/Star { 2 copy Pls Crs } def
/BoxF { stroke [] 0 setdash exch hpt sub exch vpt add M
  0 vpt2 neg V  hpt2 0 V  0 vpt2 V
  hpt2 neg 0 V  closepath fill } def
/TriUF { stroke [] 0 setdash vpt 1.12 mul add M
  hpt neg vpt -1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt 1.62 mul V closepath fill } def
/TriD { stroke [] 0 setdash 2 copy vpt 1.12 mul sub M
  hpt neg vpt 1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt -1.62 mul V closepath stroke
  Pnt  } def
/TriDF { stroke [] 0 setdash vpt 1.12 mul sub M
  hpt neg vpt 1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt -1.62 mul V closepath fill} def
/DiaF { stroke [] 0 setdash vpt add M
  hpt neg vpt neg V hpt vpt neg V
  hpt vpt V hpt neg vpt V closepath fill } def
/Pent { stroke [] 0 setdash 2 copy gsave
  translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
  closepath stroke grestore Pnt } def
/PentF { stroke [] 0 setdash gsave
  translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
  closepath fill grestore } def
/Circle { stroke [] 0 setdash 2 copy
  hpt 0 360 arc stroke Pnt } def
/CircleF { stroke [] 0 setdash hpt 0 360 arc fill } def
/C0 { BL [] 0 setdash 2 copy moveto vpt 90 450  arc } bind def
/C1 { BL [] 0 setdash 2 copy        moveto
       2 copy  vpt 0 90 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C2 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 90 180 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C3 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 0 180 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C4 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 180 270 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C5 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 0 90 arc
       2 copy moveto
       2 copy  vpt 180 270 arc closepath fill
               vpt 0 360 arc } bind def
/C6 { BL [] 0 setdash 2 copy moveto
      2 copy  vpt 90 270 arc closepath fill
              vpt 0 360 arc closepath } bind def
/C7 { BL [] 0 setdash 2 copy moveto
      2 copy  vpt 0 270 arc closepath fill
              vpt 0 360 arc closepath } bind def
/C8 { BL [] 0 setdash 2 copy moveto
      2 copy vpt 270 360 arc closepath fill
              vpt 0 360 arc closepath } bind def
/C9 { BL [] 0 setdash 2 copy moveto
      2 copy  vpt 270 450 arc closepath fill
              vpt 0 360 arc closepath } bind def
/C10 { BL [] 0 setdash 2 copy 2 copy moveto vpt 270 360 arc closepath fill
       2 copy moveto
       2 copy vpt 90 180 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C11 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 0 180 arc closepath fill
       2 copy moveto
       2 copy  vpt 270 360 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C12 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 180 360 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C13 { BL [] 0 setdash  2 copy moveto
       2 copy  vpt 0 90 arc closepath fill
       2 copy moveto
       2 copy  vpt 180 360 arc closepath fill
               vpt 0 360 arc closepath } bind def
/C14 { BL [] 0 setdash 2 copy moveto
       2 copy  vpt 90 360 arc closepath fill
               vpt 0 360 arc } bind def
/C15 { BL [] 0 setdash 2 copy vpt 0 360 arc closepath fill
               vpt 0 360 arc closepath } bind def
/Rec   { newpath 4 2 roll moveto 1 index 0 rlineto 0 exch rlineto
       neg 0 rlineto closepath } bind def
/Square { dup Rec } bind def
/Bsquare { vpt sub exch vpt sub exch vpt2 Square } bind def
/S0 { BL [] 0 setdash 2 copy moveto 0 vpt rlineto BL Bsquare } bind def
/S1 { BL [] 0 setdash 2 copy vpt Square fill Bsquare } bind def
/S2 { BL [] 0 setdash 2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S3 { BL [] 0 setdash 2 copy exch vpt sub exch vpt2 vpt Rec fill Bsquare } bind def
/S4 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S5 { BL [] 0 setdash 2 copy 2 copy vpt Square fill
       exch vpt sub exch vpt sub vpt Square fill Bsquare } bind def
/S6 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S7 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt vpt2 Rec fill
       2 copy vpt Square fill
       Bsquare } bind def
/S8 { BL [] 0 setdash 2 copy vpt sub vpt Square fill Bsquare } bind def
/S9 { BL [] 0 setdash 2 copy vpt sub vpt vpt2 Rec fill Bsquare } bind def
/S10 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt Square fill
       Bsquare } bind def
/S11 { BL [] 0 setdash 2 copy vpt sub vpt Square fill 2 copy exch vpt sub exch vpt2 vpt Rec fill
       Bsquare } bind def
/S12 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill Bsquare } bind def
/S13 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
       2 copy vpt Square fill Bsquare } bind def
/S14 { BL [] 0 setdash 2 copy exch vpt sub exch vpt sub vpt2 vpt Rec fill
       2 copy exch vpt sub exch vpt Square fill Bsquare } bind def
/S15 { BL [] 0 setdash 2 copy Bsquare fill Bsquare } bind def
/D0 { gsave translate 45 rotate 0 0 S0 stroke grestore } bind def
/D1 { gsave translate 45 rotate 0 0 S1 stroke grestore } bind def
/D2 { gsave translate 45 rotate 0 0 S2 stroke grestore } bind def
/D3 { gsave translate 45 rotate 0 0 S3 stroke grestore } bind def
/D4 { gsave translate 45 rotate 0 0 S4 stroke grestore } bind def
/D5 { gsave translate 45 rotate 0 0 S5 stroke grestore } bind def
/D6 { gsave translate 45 rotate 0 0 S6 stroke grestore } bind def
/D7 { gsave translate 45 rotate 0 0 S7 stroke grestore } bind def
/D8 { gsave translate 45 rotate 0 0 S8 stroke grestore } bind def
/D9 { gsave translate 45 rotate 0 0 S9 stroke grestore } bind def
/D10 { gsave translate 45 rotate 0 0 S10 stroke grestore } bind def
/D11 { gsave translate 45 rotate 0 0 S11 stroke grestore } bind def
/D12 { gsave translate 45 rotate 0 0 S12 stroke grestore } bind def
/D13 { gsave translate 45 rotate 0 0 S13 stroke grestore } bind def
/D14 { gsave translate 45 rotate 0 0 S14 stroke grestore } bind def
/D15 { gsave translate 45 rotate 0 0 S15 stroke grestore } bind def
/DiaE { stroke [] 0 setdash vpt add M
  hpt neg vpt neg V hpt vpt neg V
  hpt vpt V hpt neg vpt V closepath stroke } def
/BoxE { stroke [] 0 setdash exch hpt sub exch vpt add M
  0 vpt2 neg V hpt2 0 V 0 vpt2 V
  hpt2 neg 0 V closepath stroke } def
/TriUE { stroke [] 0 setdash vpt 1.12 mul add M
  hpt neg vpt -1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt 1.62 mul V closepath stroke } def
/TriDE { stroke [] 0 setdash vpt 1.12 mul sub M
  hpt neg vpt 1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt -1.62 mul V closepath stroke } def
/PentE { stroke [] 0 setdash gsave
  translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
  closepath stroke grestore } def
/CircE { stroke [] 0 setdash 
  hpt 0 360 arc stroke } def
/Opaque { gsave closepath 1 setgray fill grestore 0 setgray closepath } def
/DiaW { stroke [] 0 setdash vpt add M
  hpt neg vpt neg V hpt vpt neg V
  hpt vpt V hpt neg vpt V Opaque stroke } def
/BoxW { stroke [] 0 setdash exch hpt sub exch vpt add M
  0 vpt2 neg V hpt2 0 V 0 vpt2 V
  hpt2 neg 0 V Opaque stroke } def
/TriUW { stroke [] 0 setdash vpt 1.12 mul add M
  hpt neg vpt -1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt 1.62 mul V Opaque stroke } def
/TriDW { stroke [] 0 setdash vpt 1.12 mul sub M
  hpt neg vpt 1.62 mul V
  hpt 2 mul 0 V
  hpt neg vpt -1.62 mul V Opaque stroke } def
/PentW { stroke [] 0 setdash gsave
  translate 0 hpt M 4 {72 rotate 0 hpt L} repeat
  Opaque stroke grestore } def
/CircW { stroke [] 0 setdash 
  hpt 0 360 arc Opaque stroke } def
/BoxFill { gsave Rec 1 setgray fill grestore } def
end
%%EndProlog
%%Page: 1 1
gnudict begin
gsave
50 50 translate
0.100 0.100 scale
90 rotate
0 -5040 translate
0 setgray
newpath
(Helvetica) findfont 140 scalefont setfont
1.000 UL
LTb
714 420 M
63 0 V
6185 0 R
-63 0 V
630 420 M
(0) Rshow
714 865 M
63 0 V
6185 0 R
-63 0 V
630 865 M
(100) Rshow
714 1310 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(200) Rshow
714 1756 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(300) Rshow
714 2201 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(400) Rshow
714 2646 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(500) Rshow
714 3091 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(600) Rshow
714 3536 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(700) Rshow
714 3982 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(800) Rshow
714 4427 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(900) Rshow
714 4872 M
63 0 V
6185 0 R
-63 0 V
-6269 0 R
(1000) Rshow
714 420 M
0 63 V
0 4389 R
0 -63 V
714 280 M
(20) Cshow
1755 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(25) Cshow
2797 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(30) Cshow
3838 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(35) Cshow
4879 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(40) Cshow
5921 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(45) Cshow
6962 420 M
0 63 V
0 4389 R
0 -63 V
0 -4529 R
(50) Cshow
1.000 UL
LTb
714 420 M
6248 0 V
0 4452 V
-6248 0 V
714 420 L
140 2646 M
currentpoint gsave translate 90 rotate 0 0 M
(Time in Secs) Cshow
grestore
3838 70 M
(Number of Taxa) Cshow
1.000 UL
LT0
6311 4739 M
("fastDNAml") Rshow
6395 4739 M
399 0 V
714 580 M
2083 547 V
4879 2232 L
6962 4529 L
1.000 UL
LT1
6311 4599 M
("fastDNAml_QAdd") Rshow
6395 4599 M
399 0 V
714 529 M
2797 913 L
2082 709 V
6962 3099 L
1.000 UL
LT2
6311 4459 M
("AxMl") Rshow
6395 4459 M
399 0 V
714 508 M
2797 810 L
2082 612 V
6962 2681 L
1.000 UL
LT3
6311 4319 M
("AxMl_QAdd") Rshow
6395 4319 M
399 0 V
714 480 M
2797 692 L
2082 389 V
2083 810 V
stroke
grestore
end
showpage
%%Trailer
%%DocumentFonts: Helvetica
%%Pages: 1

%%EndDocument
 @endspecial 2705 0 a
 currentpoint grestore moveto
 2705 0 a -83 3039 a Fl(Figure)34
b(4.)g(Overall)h(e)o(x)o(ecution)e(times)h(of)f(fastDNAml)h(and)f(AxML)
h(with)f(the)h(quic)n(kad)o(d)g(option)e(enab)o(led)i(and)-83
3139 y(disab)o(led)-182 3472 y Fm(approach,)26 b(both)h(to)g(lar)o(ge)f
(test)j(sets,)g(i.e.)47 b(with)27 b(a)h(great)f(number)-182
3572 y(of)c(taxa,)g(as)h(well)g(as)g(to)f(the)g(parallel)g(algorithm.)
33 b(The)23 b(good)e(par)n(-)-182 3672 y(allel)30 b(performance)d
(impro)o(v)o(ement)g(is)k(due)e(to)i(the)f(f)o(act)g(that)g(the)-182
3771 y(tree)f(e)n(v)n(aluation)e(function)h(is)i(the)f(core)g(of)g(the)
g(w)o(ork)o(er)g(compo-)-182 3871 y(nents,)18 b(which)g(perform)f(the)i
(actual)f(computation)e(\(for)i(details)h(re-)-182 3970
y(fer)h(to)g([7)o(]\).)-83 4100 y(F)o(or)52 b(the)h(performance)c
(analysis)k(of)f Fq(A)-8 b(T)i(rExML)53 b Fm(v)o(ersus)-182
4199 y Fq(T)-6 b(rExML)p Fm(,)26 b(presented)e(in)i(table)f(2)h(we)g
(used)f(the)g(same)h(data-sets)-182 4299 y(as)g(in)f(the)h(original)e
Fq(T)-6 b(rExML)27 b Fm(publication.)38 b(F)o(or)25 b(details)h(on)f
(the)-182 4399 y(parameters)19 b(and)g(data)h(used)g(refer)g(to)g([13)o
(].)-83 4528 y(Since)38 b Fq(AxML)g Fm(does)f(not)g(implement)f
(heuristics)h(b)n(ut)h(only)-182 4628 y(a)33 b(purely)e(algorithmic)g
(optimization)h(in)h(all)g(tests)h Fq(AxML)f Fm(and)-182
4727 y Fq(fastDN)n(Aml)d Fm(rendered)d(e)o(xactly)i(the)h(same)g
(results,)j(a)d(f)o(act)g(that)-182 4827 y(can)20 b(be)g(v)o(eri\002ed)
f(by)h(a)g(simple)g Fd(diff)g Fm(on)g(the)g(output)f(\002les.)-147
4926 y(F)o(or)k(the)g(initial)g(tests)i(performed)c(on)h(the)i
(SR8000-F1)e(we)h(used)-182 5026 y(the)g(same)h(30,)g(40,)g(50)f(taxa)g
(input)g(data)h(as)g(in)g(the)g(pre)n(vious)e(tests)-182
5126 y(and)17 b(an)h(additional)e(56)i(taxa)g(test)g(set.)25
b(Furthermore)16 b(we)i(also)g(used)-182 5225 y(a)25
b(41)f(taxa)h(alignment)e(\(sequence)g(length:)34 b(1500\))23
b(of)h(mitochon-)-182 5325 y(drial)h(rRN)m(A)i(sequences)e(from)f
(beetles)i(and)g(b)n(utter\003ies,)h(similar)p 2167 3393
1583 4 v 2165 3492 4 100 v 2264 3462 a(data)20 b(set)p
2611 3492 V 192 w(option)p 3013 3492 V 153 w Fq(AxML)p
3368 3492 V 111 w(P)-6 b(AxML)p 3748 3492 V 2167 3496
1583 4 v 2165 3595 4 100 v 2269 3565 a Fm(20)20 b(taxa)p
2611 3595 V 212 w(Qadd)p 3013 3595 V 159 w(44.91\045)p
3368 3595 V 110 w(36.74\045)p 3748 3595 V 2165 3695 V
2269 3665 a(30)g(taxa)p 2611 3695 V 212 w(Qadd)p 3013
3695 V 159 w(44.81\045)p 3368 3695 V 110 w(37.93\045)p
3748 3695 V 2165 3794 V 2269 3765 a(40)g(taxa)p 2611
3794 V 212 w(Qadd)p 3013 3794 V 159 w(44.91\045)p 3368
3794 V 110 w(37.30\045)p 3748 3794 V 2165 3894 V 2269
3864 a(50)g(taxa)p 2611 3894 V 212 w(Qadd)p 3013 3894
V 159 w(45.09\045)p 3368 3894 V 110 w(38.01\045)p 3748
3894 V 2167 3897 1583 4 v 2167 3914 V 2165 4014 4 100
v 2269 3984 a(20)g(taxa)p 2611 4014 V 150 w(No)h(Qadd)p
3013 4014 V 98 w(44.95\045)p 3368 4014 V 110 w(35.17\045)p
3748 4014 V 2165 4113 V 2269 4083 a(30)f(taxa)p 2611
4113 V 150 w(No)h(Qadd)p 3013 4113 V 98 w(44.77\045)p
3368 4113 V 110 w(38.06\045)p 3748 4113 V 2165 4213 V
2269 4183 a(40)f(taxa)p 2611 4213 V 150 w(No)h(Qadd)p
3013 4213 V 98 w(44.72\045)p 3368 4213 V 110 w(37.58\045)p
3748 4213 V 2165 4313 V 2269 4283 a(50)f(taxa)p 2611
4313 V 150 w(No)h(Qadd)p 3013 4313 V 98 w(44.97\045)p
3368 4313 V 110 w(36.96\045)p 3748 4313 V 2167 4316 1583
4 v 2167 4332 V 2165 4432 4 100 v 2217 4402 a(161)e(taxa.1)p
2611 4432 V 163 w(rearr)-5 b(.)p 3013 4432 V 163 w(46.90\045)p
3368 4432 V 110 w(39.32\045)p 3748 4432 V 2165 4532 V
2217 4502 a(161)19 b(taxa.2)p 2611 4532 V 163 w(rearr)-5
b(.)p 3013 4532 V 163 w(46.98\045)p 3368 4532 V 110 w(39.24\045)p
3748 4532 V 2167 4535 1583 4 v 2167 4552 V 2165 4651
4 100 v 2217 4621 a(161)19 b(taxa.1)p 2611 4651 V 102
w(No)h(rearr)-5 b(.)p 3013 4651 V 102 w(39.48\045)p 3368
4651 V 110 w(37.81\045)p 3748 4651 V 2165 4751 V 2217
4721 a(161)19 b(taxa.2)p 2611 4751 V 102 w(No)h(rearr)-5
b(.)p 3013 4751 V 102 w(39.53\045)p 3368 4751 V 110 w(39.03\045)p
3748 4751 V 2167 4754 1583 4 v 2073 4906 a Fl(T)e(ab)o(le)22
b(1.)g(Global)f(run)g(time)g(impr)n(o)n(vements)h(fastD\255)2073
5006 y(NAml\(p\))g(vs.)i(\(P\)AxML)p eop
%%Page: 7 7
7 6 bop -112 3 1827 4 v -114 103 4 100 v -39 73 a Fm(a)p
69 103 V 144 w(n)p 252 103 V 120 w(impro)o(v)o(ement)p
792 103 V 809 103 V 135 w(a)p 991 103 V 143 w(n)p 1174
103 V 120 w(impro)o(v)o(ement)p 1714 103 V -112 106 1827
4 v -114 206 4 100 v -41 176 a(8)p 69 206 V 120 w(10)p
252 206 V 191 w(38.21\045)p 792 206 V 809 206 V 227 w(8)p
991 206 V 120 w(11)p 1174 206 V 191 w(38.67\045)p 1714
206 V -114 306 V -41 276 a(8)p 69 306 V 120 w(12)p 252
306 V 191 w(39.58\045)p 792 306 V 809 306 V 227 w(8)p
991 306 V 120 w(13)p 1174 306 V 191 w(40.02\045)p 1714
306 V -114 405 V -41 375 a(8)p 69 405 V 120 w(14)p 252
405 V 191 w(39.87\045)p 792 405 V 809 405 V 227 w(8)p
991 405 V 120 w(15)p 1174 405 V 191 w(40.68\045)p 1714
405 V -114 505 V -41 475 a(8)p 69 505 V 120 w(16)p 252
505 V 191 w(40.71\045)p 792 505 V 809 505 V 227 w(9)p
991 505 V 120 w(10)p 1174 505 V 191 w(38.24\045)p 1714
505 V -114 604 V -41 575 a(9)p 69 604 V 120 w(11)p 252
604 V 191 w(38.91\045)p 792 604 V 809 604 V 227 w(9)p
991 604 V 120 w(12)p 1174 604 V 191 w(39.91\045)p 1714
604 V -114 704 V -41 674 a(9)p 69 704 V 120 w(13)p 252
704 V 191 w(40.77\045)p 792 704 V 809 704 V 227 w(9)p
991 704 V 120 w(14)p 1174 704 V 191 w(40.19\045)p 1714
704 V -114 804 V -41 774 a(9)p 69 804 V 120 w(15)p 252
804 V 191 w(41.04\045)p 792 804 V 809 804 V 227 w(9)p
991 804 V 120 w(16)p 1174 804 V 191 w(41.10\045)p 1714
804 V -114 903 V -62 873 a(10)p 69 903 V 99 w(10)p 252
903 V 191 w(37.23\045)p 792 903 V 809 903 V 206 w(10)p
991 903 V 99 w(11)p 1174 903 V 191 w(38.39\045)p 1714
903 V -114 1003 V -62 973 a(10)p 69 1003 V 99 w(12)p
252 1003 V 191 w(39.94\045)p 792 1003 V 809 1003 V 206
w(10)p 991 1003 V 99 w(13)p 1174 1003 V 191 w(41.08\045)p
1714 1003 V -114 1103 V -62 1073 a(10)p 69 1103 V 99
w(14)p 252 1103 V 191 w(42.26\045)p 792 1103 V 809 1103
V 206 w(10)p 991 1103 V 99 w(15)p 1174 1103 V 191 w(43.00\045)p
1714 1103 V -114 1202 V -62 1172 a(10)p 69 1202 V 99
w(16)p 252 1202 V 191 w(42.26\045)p 792 1202 V 809 1202
V 991 1202 V 1174 1202 V 1714 1202 V -112 1205 1827 4
v -83 1357 a Fl(T)-7 b(ab)o(le)73 b(2.)g(Global)g(run)f(time)h(impr)n
(o)n(vements)-83 1457 y(T)-7 b(rExML)24 b(vs.)g(A)-7
b(T)g(rExML)-182 1824 y Fm(to)30 b(the)h(161)f(taxa)g(test)i(set)f
(mentioned)e(abo)o(v)o(e.)54 b(The)30 b(latter)h(w)o(as)-182
1923 y(used)25 b(for)f(analyzing)g(the)h(scalability)h(of)f(our)f
(optimization)g(con-)-182 2023 y(cerning)g(long)i(sequences.)42
b(W)-7 b(e)27 b(compiled)e(both,)h Fq(fastDN)n(AmlP)-182
2123 y Fm(and)32 b Fq(P)-6 b(AxML)33 b Fm(with)g Fd(mpicc)49
b(-O3)g(-model=F1)p Fm(,)34 b(measured)-182 2222 y
(M\003ops/s/processor\(w)o(ork)o(er\))h(performance)h(using)j
Fd(PCL)p Fm(,)f(and)-182 2322 y(e)o(x)o(ecuted)29 b(the)i(test)h(runs)f
(with)g(2)h(up)f(to)g(4)g(w)o(ork)o(ers)g(located)f(on)-182
2421 y(the)k(same)g(node)f(in)i(intra-node)d(MPI-mode.)65
b(The)34 b(results)g(in-)-182 2521 y(cluding)j(the)i(respecti)n(v)o(e)e
(program)g(options)h(are)g(presented)g(in)-182 2621 y(table)i(3.)87
b(W)-7 b(e)42 b(performed)d(those)h(tests)i(with)f(the)g(rearrange-)
-182 2720 y(ment)25 b(and)g(quickadd)f(options)h(enabled.)41
b(Those)25 b(results)i(are)e(en-)p -37 2875 1678 4 v
-39 2974 4 100 v 13 2944 a(data)20 b(set)p 313 2974 V
100 w(w)o(ork)o(ers)p 678 2974 V 98 w Fq(P)-6 b(AxML)p
1057 2974 V 100 w Fm(M\003ops/s/proc.)p 1639 2974 V -37
2978 1678 4 v -39 3077 4 100 v 18 3047 a(30)19 b(taxa)p
313 3077 V 216 w(2)p 678 3077 V 223 w(24.82\045)p 1057
3077 V 237 w(123.77)p 1639 3077 V -39 3177 V 18 3147
a(40)g(taxa)p 313 3177 V 216 w(2)p 678 3177 V 223 w(28.10\045)p
1057 3177 V 237 w(128.06)p 1639 3177 V -39 3277 V 18
3247 a(50)g(taxa)p 313 3277 V 216 w(2)p 678 3277 V 223
w(27.76\045)p 1057 3277 V 237 w(128.62)p 1639 3277 V
-39 3376 V 18 3346 a(56)g(taxa)p 313 3376 V 216 w(2)p
678 3376 V 223 w(27.10\045)p 1057 3376 V 237 w(128.55)p
1639 3376 V -39 3476 V 18 3446 a(41)g(taxa)p 313 3476
V 216 w(2)p 678 3476 V 223 w(34.17\045)p 1057 3476 V
237 w(119.74)p 1639 3476 V -39 3575 V 18 3546 a(41)g(taxa)p
313 3575 V 216 w(4)p 678 3575 V 223 w(30.17\045)p 1057
3575 V 237 w(106.51)p 1639 3575 V -37 3579 1678 4 v -83
3731 a Fl(T)-7 b(ab)o(le)23 b(3.)h(Global)e(run)g(time)h(impr)n(o)n
(vement)g(P)-8 b(AxML)-83 3830 y(vs.)51 b(fastDNAmlP)f(and)g
(M\003ops/s/pr)n(oc.)h(perf)n(or)n(\255)-83 3930 y(mance)23
b(on)g(the)f(Hitac)o(hi)i(SR8000\255F1)-182 4229 y Fm(couraging,)g
(since)i(the)g(algorithmic)e(optimizations)h(of)h Fq(P)-6
b(AxML)-182 4329 y Fm(scale)48 b(well)g(to)g(the)f(speci\002c)h(hardw)o
(are)e(architecture,)53 b(espe-)-182 4428 y(cially)25
b(when)g(longer)f(sequences)g(are)i(used,)g(as)g(will)g(be)f(the)g
(case)-182 4528 y(for)39 b(production)f(runs)h(using)h(data)g(from)f
(the)i(ARB.)g(Further)n(-)-182 4628 y(more,)25 b(the)g
(M\003ops/s/processor\(w)o(ork)o(er\))d(rate)j(is)h(already)e(satis-)
-182 4727 y(fying)31 b(\(e.g.)60 b(50)31 b(M\003ops/s/processor)g(are)h
(considered)e(to)i(be)g(a)-182 4827 y(\223good\224)21
b(v)n(alue)h(for)g(an)g(initial)h(test)h(run)e(by)g(the)g(Hitachi)h
(SR8000-)-182 4926 y(F1)34 b(administration\),)g(although)e(no)i
(special)f(compiler)g(options)-182 5026 y(for)41 b(further)g
(optimizing)f(the)i(code)g(ha)n(v)o(e)f(been)h(used)f(so)i(f)o(ar)-5
b(.)-182 5126 y(The)24 b(M\003ops/s/processor)f(performance)f(v)n
(aries)i(less)i(than)e(0.5\045)-182 5225 y(among)19 b(the)i(dif)n
(ferent)e(w)o(ork)o(ers,)h(i.e.)27 b(there)21 b(is)h(no)e(load)h
(balancing)-182 5325 y(problem.)1974 83 y Fs(6.)j(A)-10
b(v)o(ailability)2073 297 y Fm(The)16 b(most)g(recent)f(distrib)n
(ution)f(v)o(ersions)h(of)h Fq(AxML)p Fm(,)g Fq(P)-6
b(AxML)1974 397 y Fm(and)20 b Fq(A)-8 b(T)i(rExML)22
b Fm(are)f(a)n(v)n(ailable)g(for)f(do)n(wnload)f(at)i([10)o(].)27
b(W)-7 b(e)22 b(also)1974 496 y(pro)o(vide)16 b(a)i(program)e(called)h
(Simple)h Fq(P)-6 b(AxML)p Fm(,)18 b(that)g(may)g(be)f(used)1974
596 y(for)25 b(de)n(v)o(eloping)e(CORB)m(A)28 b(and)d(P)-8
b(AxML@home-lik)o(e)25 b(\(see)h(sec-)1974 696 y(tions)j(7)g(and)g(8\))
g(applications)f(and)h(pro)o(vides)e(a)j(more)f(adequate)1974
795 y(program)h(structure)i(for)g(de)n(v)o(eloping)d(such)j(kind)g(of)g
(programs.)1974 895 y(A)20 b Fq(P)-6 b(AxML)20 b Fm(distrib)n(ution)f
(v)o(ersion)f(including)g(a)i(compiler)f(switch)1974
995 y(for)k(using)g(the)h(loop)f(transformations)e(for)i
(supercomputers)e(will)1974 1094 y(soon)e(be)i(released.)1974
1325 y Fs(7.)j(Curr)n(ent)j(W)-7 b(ork)2073 1539 y Fm(Currently)55
b(we)h(focus)g(on)f(the)h(e)n(v)n(aluation)e(of)i(dif)n(ferent)1974
1639 y(Hitachi-speci\002c)32 b(parallelization)g(concepts,)k(such)d(as)
h(pseudo-)1974 1738 y(v)o(ectorization)23 b(or)i(inter)n(-node)e(MPI)j
(and)f(the)g(respecti)n(v)o(e)f(adapta-)1974 1838 y(tion)f(of)g(the)g
(program,)f(as)i(well)f(as)h(on)f(the)h(preparation)d(and)h(e)o(x)o(e-)
1974 1938 y(cution)16 b(of)h(\002rst)h(production)d(test)j(runs)f
(using)g(sequence)f(data)h(from)1974 2037 y(the)j(ARB)i(database.)2073
2137 y(F)o(or)31 b(estimating)g(the)h(e)o(xpected)d(run)i(time)g(impro)
o(v)o(ement)d(in-)1974 2237 y(duced)g(by)g Fq(AxML)i
Fm(for)e(a)i(speci\002c)f(input)f(data)h(set)h(we)g(ha)n(v)o(e)e(al-)
1974 2336 y(ready)e(de)n(v)o(eloped)f(an)i(ef)n(\002cient)g
(best-case/w)o(orst-case)g(estimate)1974 2436 y(algorithm,)35
b(which)e(is)i(presently)e(being)g(implemented.)63 b(Note,)1974
2535 y(that)40 b(a)g(quick)f(estimate)h(for)f(a)h(speci\002c)g
(sequence)f(alignment)1974 2635 y(might)d(also)i(be)f(obtained)f(by)g
(e)o(x)o(ecuting)f Fq(AxML)j Fm(and)f Fq(fastD-)1974
2735 y(N)n(Aml)30 b Fm(without)f(local)g(and)g(global)f
(rearrangements,)h(since)g(the)1974 2834 y(programs)e(e)o(x)o(ecute)h
(signi\002cantly)g(f)o(aster)h(in)h(that)f(con\002guration)1974
2934 y(\(see)20 b(section)g(8\).)2073 3034 y(Furthermore,)i(we)h(are)g
(continuously)e(e)o(xtending)g(the)i Fq(AxML)1974 3133
y Fm(program)e(f)o(amily)i(and)g(in)m(v)o(estigate)f(the)i
(applicability)e(of)h(v)n(arious)1974 3233 y(programming)16
b(paradigms)h(for)i(handling)f(the)h(comple)o(xity)e(of)i(the)1974
3332 y(problem)30 b(be)o(yond)f(the)i(scope)g(of)h(traditional)e
(supercomputing.)1974 3432 y(W)m(ithin)h(this)h(conte)o(xt)e(we)h(are)g
(currently)f(de)n(v)o(eloping)e Fq(D)m(AxML)1974 3532
y Fm(\(Distrib)n(uted)19 b Fq(AxML)p Fm(\))i(and)e Fq(GAxML)i
Fm(\(Grid)f Fq(AxML)p Fm(\).)2073 3631 y Fq(D)m(AxML)33
b Fm(is)f(a)g(CORB)m(A)h(\(Common)d(Object)h(Request)g(Bro-)1974
3731 y(k)o(er\))i(v)o(ersion)f(of)h Fq(P)-6 b(AxML)33
b Fm(based)g(on)g Fq(LMC)i Fm(\(Load)d(Managed)1974 3831
y(CORB)m(A)22 b([5)o(]\).)j Fq(LMC)d Fm(is)f(an)g(automatic)e(load)h
(balancing)f(tool)h(for)1974 3930 y(CORB)m(A)j(applications)d(which)h
(is)i(inte)o(grated)d(transparently)f(into)1974 4030
y(the)28 b(ORB)i(\(Object)e(Request)h(Brok)o(er\))e(and)h(distrib)n
(utes)h(load)f(by)1974 4129 y(initial)d(serv)n(ant)f(object)h
(placement,)f(migration)f(and)i(replication.)1974 4229
y(The)31 b(initial)g(v)o(ersion)f(of)h Fq(D)m(AxML)g
Fm(has)h(already)e(been)g(success-)1974 4329 y(fully)18
b(tested)g(on)g(the)g(Sun-cluster)f(of)h(the)h(LRR.)g(It)f(performs)f
(well,)1974 4428 y(both)28 b(in)g(terms)h(of)f(performance,)f(i.e.)51
b(CORB)m(A)30 b(o)o(v)o(erhead)c(and)1974 4528 y(load)31
b(distrib)n(ution,)j(since)e(the)g(parallel)g(algorithm)e(of)i
Fq(P)-6 b(AxML)1974 4628 y Fm(is)35 b(well)h(suited)e(for)g(distrib)n
(uted)g(computation.)66 b(Presently)34 b(we)1974 4727
y(are)29 b(de)n(v)o(eloping)d(a)j(standard)f(CORB)m(A)j(distrib)n
(ution)d(v)o(ersion)f(of)1974 4827 y Fq(D)m(AxML)p Fm(,)38
b(i.e.)g(without)f(load)h(balancing,)i(based)d(on)h(a)g(freely)1974
4926 y(a)n(v)n(ailable)20 b(ORB)h(implementation.)2073
5026 y Fq(GAxML)33 b Fm(is)g(a)f(\223phylogenetic)d(grid)i(w)o
(orm\224,)j(which)e(is)h(be-)1974 5126 y(ing)c(de)n(v)o(eloped)d(in)k
(cooperation)c(with)k(the)f(Cactus)h(team)f([2)o(][1)o(])1974
5225 y(at)h(the)f(Max-Planck-Institut)e(f)7 b(\250)-35
b(ur)28 b(Gra)n(vitationsphysik,)h(Albert-)1974 5325
y(Einstein-Institut.)p eop
%%Page: 8 8
8 7 bop -83 83 a Fm(Unlik)o(e)27 b(man)o(y)f(typical)h(supercomputer)e
(applications,)i(inter)n(-)-182 183 y(rupting,)21 b(checkpointing)f
(and)i(restarting)f Fq(GAxML)i Fm(is)h(v)o(ery)e(f)o(ast,)-182
282 y(and)35 b(the)g(state)h(to)g(be)f(sa)n(v)o(ed)h(comprises)e(only)h
(a)h(fe)n(w)f(lines)h(of)-182 382 y(ASCII)29 b(te)o(xt.)52
b(Since)29 b(the)h(co-scheduling)c(problem)i(has)h(not)g(yet)-182
482 y(been)d(resolv)o(ed)f(in)h(practice)g(and)g(communication)e
(between)i(su-)-182 581 y(percomputers)14 b(at)j(dif)n(ferent)e(sites)j
(might)e(ha)n(v)o(e)h(a)g(ne)o(gati)n(v)o(e)d(impact)-182
681 y(on)21 b(performance)d([7)o(][8)o(],)k(we)g(in)m(v)o(ented)d(the)j
(term)f(\223phylogenetic)-182 780 y(grid)26 b(w)o(orm\224)h(for)f(an)h
(application)f(migrating)f(to)j(sites)g(with)f(free)-182
880 y(capacities)20 b(on)f(the)i(grid,)e(for)h(a)n(v)n(oiding)f(those)h
(problems.)-83 999 y Fq(GAxML)j Fm(is)g(also)g(based)f(on)f
Fq(P)-6 b(AxML)23 b Fm(and)f(already)f(incorpo-)-182
1098 y(rates)k(the)g(necessary)f(modi\002cations)g(for)g(initiating)h
(a)g(migration)-182 1198 y(request)d(and)g(a)i(compiler)e(switch)h(for)
f(selecting)h(the)g(appropriate)-182 1298 y(case-switch)17
b(implementation)e(\(see)j(section)f(4\))g(for)g(a)h(speci\002c)g(ar)n
(-)-182 1397 y(chitecture,)25 b(e.g.)40 b(a)26 b(classical)g
(supercomputer)c(or)j(a)h(huge)e(Linux)-182 1497 y(cluster)-5
b(.)45 b(Migrations)25 b(will)j(be)f(performed)d(by)i(using)h(a)g(grid)
f(mi-)-182 1597 y(gration)19 b(serv)o(er)g(de)n(v)o(eloped)f(by)h(the)i
(Cactus)f(team.)-182 1887 y Fs(8)o(.)25 b(Futur)n(e)i(W)-7
b(ork)-83 2160 y Fm(Future)22 b(w)o(ork)g(will)h(co)o(v)o(er)e(the)i
(implementation)d(and)i(analysis)-182 2260 y(of)e(a)g(dif)n(ferent)f
(parallelization)f(approach.)-83 2378 y(An)g(important)f(f)o(act)h
(within)f(this)i(conte)o(xt)e(is,)i(that)f Fq(AxML)g
Fm(runs)-182 2478 y(signi\002cantly)j(f)o(aster)h(with)g(the)g(local)g
(and)f(global)g(rearrangement)-182 2578 y(option)g(switched)i(of)n(f)g
(\(E.g.)33 b(f)o(actor)22 b(100)g(for)h(the)g(161)f(mitochon-)-182
2677 y(drial)32 b(rRN)m(A)i(sequences\).)63 b(Simply)32
b(switching)h(of)n(f)f(rearrange-)-182 2777 y(ments)d(may)g(decrease)g
(tree)h(quality)f(on)g(the)h(one)f(hand,)h(b)n(ut)g(f)o(a-)-182
2876 y(cilitates)23 b(the)f(analysis)h(of)f(a)h(greater)e(number)g(of)h
(input)g(sequence)-182 2976 y(permutations)16 b(on)h(the)h(other)g
(hand,)f(which)g(in)i(turn)e(increases)h(tree)-182 3076
y(quality)h(again.)-83 3195 y(Since)24 b(the)g(calculation)f(of)g(a)i
(single)e(tree)h(without)f(rearrange-)-182 3294 y(ments)34
b(becomes)g(signi\002cantly)g(f)o(aster)g(one)g(can)h(distrib)n(ute)f
(in-)-182 3394 y(put)39 b(sequence)h(permutations)e(instead)i(of)g
(tree)g(topologies)f(to)-182 3493 y(the)20 b(w)o(ork)o(ers,)f(thus)h
(signi\002cantly)f(reducing)f(the)i(communication)-182
3593 y(and)k(synchronization)d(o)o(v)o(erhead.)35 b(Furthermore,)23
b(the)i(similarity)-182 3693 y(among)18 b(the)j(sequence)e(of)g
(generated)g(topologies)g(during)f(tree)i(re-)-182 3792
y(construction,)g(is)j(greater)d(without)i(performing)d(rearrangements)
-182 3892 y(and)g(therefore,)g(there)h(is)h(a)g(potential)f(for)f
(additional)h(algorithmic)-182 3992 y(optimizations.)-83
4110 y(W)-7 b(e)41 b(plan)f(to)g(implement)e(a)j(tw)o(o-step)e
(parallel)h(algorithm,)-182 4210 y(which)35 b(initially)i(performs)d
(tree)i(reconstruction)e(as)j(described)-182 4310 y(abo)o(v)o(e)32
b(and)h(then)h(e)o(x)o(ecutes)f(the)g(standard)g Fq(P)-6
b(AxML)34 b Fm(algorithm)-182 4409 y(with)j(rearrangements)d(in)k(the)f
(second)f(step,)42 b(using)37 b(those)g(se-)-182 4509
y(quence)32 b(permutations,)i(that)f(rendered)f(the)h(best)h(trees)f
(in)h(step)-182 4608 y(one.)28 b(W)m(ithin)21 b(this)i(conte)o(xt)d(we)
i(will)g(e)n(v)n(aluate)f(v)n(arious)f(strate)o(gies)-182
4708 y(and)d(algorithms)f(for)i(generating)e(useful)h(input)g(sequence)
g(permu-)-182 4808 y(tations.)-83 4926 y(Finally)-5 b(,)119
b(we)101 b(plan)e(to)h(de)n(v)o(elop)e(and)h(distrib)n(ute)-182
5026 y(P)-8 b(AxML@home,)44 b(an)d(application)e(in)i(the)g(style)g(of)
f(the)h(v)o(ery)-182 5126 y(successful)26 b(project)h(SETI@home)e([3)o
(],)k(based)e(on)f(peer)n(-to-peer)-182 5225 y(communication,)46
b(the)e(f)o(ast)h(algorithm)d(of)i Fq(P)-6 b(AxML)44
b Fm(and)g(the)-182 5325 y(e)o(xperience)18 b(gained)g(with)j(the)f(de)
n(v)o(elopment)d(of)j Fq(D)m(AxML)p Fm(.)1974 83 y Fs(Refer)n(ences)
2025 291 y Fc([1])42 b(G.)14 b(Allen,)h(W)-7 b(.)15 b(Benger)m(,)h(T)-6
b(.)14 b(Dramlitsch,)i(T)-6 b(.)14 b(Goodale,)j(H.-C.)c(He)o(ge,)2154
382 y(G.)22 b(Lanfermann,)j(A.)e(Merzk)o(y)-5 b(,)25
b(T)-6 b(.)23 b(Radk)o(e,)i(and)f(E.)e(Seidel.)41 b(Cac-)2154
473 y(tus)19 b(grid)g(computing:)24 b(Re)n(vie)n(w)19
b(of)g(current)h(de)n(v)o(elopment.)28 b Fb(LNCS)p Fc(,)2154
565 y(2150:817)21 b(f)n(f.,)d(2001.)2025 652 y([2])42
b(G.)36 b(Allen,)41 b(W)-7 b(.)36 b(Benger)m(,)42 b(T)-6
b(.)36 b(Dramlitsch,)41 b(T)-6 b(.)37 b(Goodale,)42 b(H.-C.)2154
743 y(He)o(ge,)22 b(G.)f(Lanfermann,)h(A.)f(Merzk)o(y)-5
b(,)23 b(T)-6 b(.)21 b(Radk)o(e,)i(E.)d(Seidel,)i(and)2154
834 y(J.)d(Shal.)28 b(Cactus)19 b(tools)h(for)f(grid)h(applications.)29
b Fb(Cluster)19 b(Comput-)2154 926 y(ing)p Fc(,)g(4\(3\):179\226188,)i
(2001.)2025 1013 y([3])42 b(Berkle)o(y)-5 b(.)27 b(Setiathome)19
b(homepage.)28 b(T)-5 b(echnical)19 b(report,)2156 1104
y Fa(S)t(E)t(T)t(I)t(A)m(T)t(H)t(O)t(M)t(E)t Fc(.)t Fa(S)t(S)t(L)t
Fc(.)s Fa(B)t(E)s(R)t(K)t(E)s(L)s(E)s(Y)-5 b Fc(.)t Fa(E)s(D)t(U)r
Fc(,)12 b(2002.)2025 1191 y([4])42 b(J.)26 b(Felsenstein.)53
b(Ev)o(olutionary)27 b(trees)g(from)g(dna)h(sequences:)41
b(A)2154 1283 y(maximum)23 b(lik)o(elihood)h(approach.)40
b Fb(J)n(.)23 b(Mol.)f(Evol.)p Fc(,)h(17:368\226376,)2154
1374 y(1981.)2025 1461 y([5])42 b(M.)25 b(Lindermeier)l(.)47
b(Load)25 b(management)i(for)e(distrib)o(uted)g(object-)2154
1553 y(oriented)38 b(en)m(vironments.)88 b(In)38 b Fb(Pr)m(oceedings)h
(of)e(2nd)i(Interna-)2154 1644 y(tional)24 b(Symposium)h(on)f(Distrib)o
(uted)g(Objects)g(and)h(Applications)2154 1735 y(\(DO)l(A)m('00\))p
Fc(,)18 b(pages)i(59\22668,)g(2000.)2025 1822 y([6])42
b(G.)36 b(Olsen,)42 b(H.)36 b(Matsuda,)42 b(R.)37 b(Hagstrom,)42
b(and)37 b(R.)g(Ov)o(erbeek.)2154 1914 y(f)o(astdnaml:)c(A)23
b(tool)h(for)f(construction)i(of)f(phylogenetic)h(trees)e(of)2154
2005 y(dna)j(sequences)i(using)e(maximum)h(lik)o(elihood.)50
b Fb(Comput.)26 b(Appl.)2154 2096 y(Biosci.)p Fc(,)18
b(10:41\22648,)i(1994.)2025 2183 y([7])42 b(C.)28 b(Ste)n(w)o(art,)j
(D.)d(Hart,)j(D.)d(Berry)-5 b(,)31 b(G.)e(Olsen,)i(E.)d(W)-6
b(ernert,)31 b(and)2154 2275 y(W)-7 b(.)31 b(Fischer)l(.)68
b(P)o(arallel)31 b(implementation)i(and)g(performance)g(of)2154
2366 y(f)o(astdnaml)16 b(-)f(a)g(program)h(for)f(maximum)i(lik)o
(elihood)f(phylogenetic)2154 2457 y(inference.)27 b(In)19
b Fb(Pr)m(oceedings)h(of)f(SC2001)p Fc(,)h(No)o(v)o(ember)g(2001.)2025
2545 y([8])42 b(C.)22 b(Ste)n(w)o(art,)i(T)-6 b(.)23
b(T)-6 b(an,)25 b(M.)e(Buchhorn,)j(D.)d(Hart,)h(D.)f(Berry)-5
b(,)24 b(Z.)f(L.,)2154 2636 y(E.)31 b(W)-6 b(ernert,)34
b(M.)e(Sakharkar)m(,)k(W)-7 b(.)31 b(Fisher)m(,)j(and)f(D.)e(McMullen.)
2154 2727 y(Ev)o(olutionary)f(biology)h(and)f(computational)h(grids.)61
b(T)-5 b(echnical)2154 2819 y(report,)29 b(IBM)e(CASCON)f
(Computational)i(Biology)g(W)-6 b(orkshop:)2154 2910
y(Softw)o(are)18 b(T)-6 b(ools)19 b(for)g(Computational)h(Biology)-5
b(,)19 b(1999.)2025 2997 y([9])42 b(TUM.)26 b(The)19
b(arb)g(project.)27 b(T)-5 b(echnical)19 b(report,)2156
3088 y Fa(W)t(W)t(W)n Fc(.)t Fa(A)t(R)t(B)t Fc(-)t Fa(H)t(O)t(M)t(E)t
Fc(.)t Fa(D)t(E)r Fc(,)14 b(2002.)1988 3176 y([10])42
b(TUM.)70 b(Axml,)36 b(paxml,)g(atre)o(xml)d(do)n(wnload)h(site.)70
b(T)-5 b(echnical)2154 3267 y(report,)2156 3358 y Fa(W)t(W)t(W)t(B)t(O)
t(D)t(E)t Fc(.)t Fa(I)t(N)t Fc(.)t Fa(T)t(U)t(M)t Fc(.)t
Fa(D)t(E)t Fc(/)t(\230)s Fa(S)t(T)n(A)t(M)t(A)m(T)m(A)t(K)t
Fc(/)t Fa(R)s(E)s(S)t(E)s(A)t(R)t(C)s(H)t Fc(.)t Fa(H)t(T)s(M)t(L)q
Fc(,)2154 3450 y(2002.)1988 3537 y([11])42 b(UIUC.)26
b(f)o(astdnaml)19 b(distrib)o(ution.)27 b(T)-5 b(echnical)19
b(report,)2156 3628 y Fa(G)t(E)t(T)n(A)t Fc(.)t Fa(L)t(I)t(F)t(E)t
Fc(.)t Fa(U)t(I)t(U)t(C)t Fc(.)s Fa(E)s(D)t(U)t Fc(/)t(\230)s
Fa(G)t(A)t(RY)s Fc(/)t Fa(P)t(R)q(O)t(G)t(R)s(A)t(M)t(S)r
Fc(,)12 b(2002.)1988 3715 y([12])42 b(UW)-7 b(.)26 b(The)19
b(phylogen)o(y)h(inference)g(package.)28 b(T)-5 b(echnical)19
b(report,)2156 3807 y Fa(E)t(V)r(O)t(L)t(U)t(T)t(I)t(O)t(N)t
Fc(.)t Fa(G)t(E)t(N)t(E)s(T)s(I)t(C)s(S)t Fc(.)t Fa(W)m(A)t(S)s(H)t(I)t
(N)t(G)t(T)r(O)t(N)s Fc(.)t Fa(E)s(D)t(U)t Fc(/)s Fa(P)t(H)t(Y)t(L)s(I)
t(P)l Fc(.)t Fa(H)s(T)t(M)t(L)q Fc(,)2154 3898 y(2002.)1988
3985 y([13])42 b(M.)25 b(W)-6 b(olf,)25 b(S.)g(Easteal,)h(M.)f(Kahn,)i
(B.)d(McKay)-5 b(,)28 b(and)d(L.)g(Jermiin.)2154 4076
y(T)m(re)o(xml:)e(A)c(maximum)h(lik)o(elihood)h(program)f(for)f(e)o
(xtensi)n(v)o(e)h(tree-)2154 4168 y(space)f(e)o(xploration.)28
b Fb(Bioinformatics)p Fc(,)19 b(16\(4\):383\226394,)i(2000.)p
eop
%%Trailer
end
userdict /end-hook known{end-hook}if
%%EOF