%!PS-Adobe-2.0 %%Creator: dvipsk 5.66a Copyright 1986-97 Radical Eye Software (www.radicaleye.com) %%Title: mga.final.dvi %%Pages: 9 %%PageOrder: Ascend %%BoundingBox: 0 0 596 842 %%DocumentFonts: Helvetica-BoldOblique Helvetica-Oblique Helvetica-Bold %%+ Helvetica Times-Roman Times-Italic Times-BoldItalic Times-Bold %%+ Courier %%DocumentPaperSizes: a4 %%EndComments %DVIPSCommandLine: dvips -o mga.final.ps mga.final.dvi %DVIPSParameters: dpi=600, compressed %DVIPSSource: TeX output 2002.03.29:0141 %%BeginProcSet: texc.pro %! /TeXDict 250 dict def TeXDict begin /N{def}def /B{bind def}N /S{exch}N /X{S N}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{dup dup 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 /IE 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 IE N end dup{/foo setfont}2 array copy cvx N load 0 nn put /ctr 0 N[}B /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 dup definefont setfont}B /ch-width{ch-data dup length 5 sub get}B /ch-height{ch-data dup length 4 sub get}B /ch-xoff{ 128 ch-data dup length 3 sub get sub}B /ch-yoff{ch-data dup length 2 sub get 127 sub}B /ch-dx{ch-data dup length 1 sub get}B /ch-image{ch-data dup 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 /sf 0 N /CharBuilder{save 3 1 roll S dup /base get 2 index get S /BitMaps get S get /ch-data X pop /ctr 0 N ch-dx 0 ch-xoff ch-yoff ch-height sub ch-xoff ch-width add ch-yoff setcachedevice ch-width ch-height true[1 0 0 -1 -.1 ch-xoff sub ch-yoff .1 sub]/id ch-image N /rw ch-width 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 dup 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 dup gp add /gp X adv}B /nd{/cp 0 N rw exit}B /lsh{rw cp 2 copy get dup 0 eq{pop 1}{ dup 255 eq{pop 254}{dup dup add 255 and S 1 and or}ifelse}ifelse put 1 adv}B /rsh{rw cp 2 copy get dup 0 eq{pop 128}{dup 255 eq{pop 127}{dup 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}]dup{bind pop}forall N /D{/cc X dup type /stringtype ne{] }if nn /base get cc ctr put nn /BitMaps get S ctr S sf 1 ne{dup dup length 1 sub dup 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 dup 1 get dup mul exch 0 get dup 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 /IE 256 array N 0 1 255{IE S 1 string dup 0 3 index put cvn put}for 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 /rulex 0 N /ruley 0 N /v{/ruley X /rulex X V}B /V {}B /RV statusdict begin /product where{pop false[(Display)(NeXT) (LaserWriter 16/600)]{dup length product length le{dup 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 rulex ruley false RMat{BDot} imagemask grestore}}{{gsave TR -.1 .1 TR rulex ruley scale 1 1 false RMat{BDot}imagemask grestore}}ifelse B /QV{gsave newpath transform round exch round exch itransform moveto rulex 0 rlineto 0 ruley neg rlineto rulex neg 0 rlineto fill grestore}B /a{moveto}B /delta 0 N /tail{dup /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 = "22 June 1996", % filename = "8r.enc", % email = "kb@@mail.tug.org", % address = "135 Center Hill Rd. // Plymouth, MA 02360", % codetable = "ISO/ASCII", % checksum = "119 662 4424", % 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 down 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{/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 %%BeginProcSet: color.pro %! TeXDict begin /setcmykcolor where{pop}{/setcmykcolor{dup 10 eq{pop setrgbcolor}{1 sub 4 1 roll 3{3 index add neg dup 0 lt{pop 0}if 3 1 roll }repeat setrgbcolor pop}ifelse}B}ifelse /TeXcolorcmyk{setcmykcolor}def /TeXcolorrgb{setrgbcolor}def /TeXcolorgrey{setgray}def /TeXcolorgray{ setgray}def /TeXcolorhsb{sethsbcolor}def /currentcmykcolor where{pop}{ /currentcmykcolor{currentrgbcolor 10}B}ifelse /DC{exch dup userdict exch known{pop pop}{X}ifelse}B /GreenYellow{0.15 0 0.69 0 setcmykcolor}DC /Yellow{0 0 1 0 setcmykcolor}DC /Goldenrod{0 0.10 0.84 0 setcmykcolor} DC /Dandelion{0 0.29 0.84 0 setcmykcolor}DC /Apricot{0 0.32 0.52 0 setcmykcolor}DC /Peach{0 0.50 0.70 0 setcmykcolor}DC /Melon{0 0.46 0.50 0 setcmykcolor}DC /YellowOrange{0 0.42 1 0 setcmykcolor}DC /Orange{0 0.61 0.87 0 setcmykcolor}DC /BurntOrange{0 0.51 1 0 setcmykcolor}DC /Bittersweet{0 0.75 1 0.24 setcmykcolor}DC /RedOrange{0 0.77 0.87 0 setcmykcolor}DC /Mahogany{0 0.85 0.87 0.35 setcmykcolor}DC /Maroon{0 0.87 0.68 0.32 setcmykcolor}DC /BrickRed{0 0.89 0.94 0.28 setcmykcolor} DC /Red{0 1 1 0 setcmykcolor}DC /OrangeRed{0 1 0.50 0 setcmykcolor}DC /RubineRed{0 1 0.13 0 setcmykcolor}DC /WildStrawberry{0 0.96 0.39 0 setcmykcolor}DC /Salmon{0 0.53 0.38 0 setcmykcolor}DC /CarnationPink{0 0.63 0 0 setcmykcolor}DC /Magenta{0 1 0 0 setcmykcolor}DC /VioletRed{0 0.81 0 0 setcmykcolor}DC /Rhodamine{0 0.82 0 0 setcmykcolor}DC /Mulberry {0.34 0.90 0 0.02 setcmykcolor}DC /RedViolet{0.07 0.90 0 0.34 setcmykcolor}DC /Fuchsia{0.47 0.91 0 0.08 setcmykcolor}DC /Lavender{0 0.48 0 0 setcmykcolor}DC /Thistle{0.12 0.59 0 0 setcmykcolor}DC /Orchid{ 0.32 0.64 0 0 setcmykcolor}DC /DarkOrchid{0.40 0.80 0.20 0 setcmykcolor} DC /Purple{0.45 0.86 0 0 setcmykcolor}DC /Plum{0.50 1 0 0 setcmykcolor} DC /Violet{0.79 0.88 0 0 setcmykcolor}DC /RoyalPurple{0.75 0.90 0 0 setcmykcolor}DC /BlueViolet{0.86 0.91 0 0.04 setcmykcolor}DC /Periwinkle {0.57 0.55 0 0 setcmykcolor}DC /CadetBlue{0.62 0.57 0.23 0 setcmykcolor} DC /CornflowerBlue{0.65 0.13 0 0 setcmykcolor}DC /MidnightBlue{0.98 0.13 0 0.43 setcmykcolor}DC /NavyBlue{0.94 0.54 0 0 setcmykcolor}DC /RoyalBlue{1 0.50 0 0 setcmykcolor}DC /Blue{1 1 0 0 setcmykcolor}DC /Cerulean{0.94 0.11 0 0 setcmykcolor}DC /Cyan{1 0 0 0 setcmykcolor}DC /ProcessBlue{0.96 0 0 0 setcmykcolor}DC /SkyBlue{0.62 0 0.12 0 setcmykcolor}DC /Turquoise{0.85 0 0.20 0 setcmykcolor}DC /TealBlue{0.86 0 0.34 0.02 setcmykcolor}DC /Aquamarine{0.82 0 0.30 0 setcmykcolor}DC /BlueGreen{0.85 0 0.33 0 setcmykcolor}DC /Emerald{1 0 0.50 0 setcmykcolor}DC /JungleGreen{0.99 0 0.52 0 setcmykcolor}DC /SeaGreen{ 0.69 0 0.50 0 setcmykcolor}DC /Green{1 0 1 0 setcmykcolor}DC /ForestGreen{0.91 0 0.88 0.12 setcmykcolor}DC /PineGreen{0.92 0 0.59 0.25 setcmykcolor}DC /LimeGreen{0.50 0 1 0 setcmykcolor}DC /YellowGreen{ 0.44 0 0.74 0 setcmykcolor}DC /SpringGreen{0.26 0 0.76 0 setcmykcolor} DC /OliveGreen{0.64 0 0.95 0.40 setcmykcolor}DC /RawSienna{0 0.72 1 0.45 setcmykcolor}DC /Sepia{0 0.83 1 0.70 setcmykcolor}DC /Brown{0 0.81 1 0.60 setcmykcolor}DC /Tan{0.14 0.42 0.56 0 setcmykcolor}DC /Gray{0 0 0 0.50 setcmykcolor}DC /Black{0 0 0 1 setcmykcolor}DC /White{0 0 0 0 setcmykcolor}DC end %%EndProcSet TeXDict begin 39158280 55380996 1000 600 600 (mga.final.dvi) @start %DVIPSBitmapFont: Fa cmr8 8 10 /Fa 10 121 df<13031307130E131C1338137013F0EA01E013C01203EA0780A2EA0F00A2 121EA35AA45AA512F8A25AAB7EA21278A57EA47EA37EA2EA0780A2EA03C0120113E0EA00 F013701338131C130E1307130310437AB11B>40 D<12C07E12707E7E7E120FEA07801203 13C0EA01E0A2EA00F0A21378A3133CA4131EA5131FA2130FAB131FA2131EA5133CA41378 A313F0A2EA01E0A2EA03C013801207EA0F00120E5A5A5A5A5A10437CB11B>I43 D<130C133C137CEA03FC12FFEAFC7C12 00B3B113FE387FFFFEA2172C7AAB23>49 DI<13FF000713C0380F01F0381C00 F8003F137C80A2143F001E7FC7FCA4EB07FF137F3801FE1FEA07F0EA1FC0EA3F80EA7F00 127E00FE14065AA3143F7E007E137F007FEBEF8C391F83C7FC390FFF03F83901FC01E01F 207D9E23>97 D105 D<2607C07FEB07F03BFFC3FFC03FFC903AC783 F0783F3C0FCE01F8E01F803B07DC00F9C00F01F8D9FF8013C04990387F000749137EA249 137CB2486C01FEEB0FE03CFFFE0FFFE0FFFEA2371E7E9D3C>109 D<3807C0FE39FFC3FF809038C703E0390FDE01F0EA07F8496C7EA25BA25BB2486C487E3A FFFE1FFFC0A2221E7E9D27>I<3AFFFC07FF80A23A0FF003FC000003EB01F0000114C06D 485A000091C7FCEB7C06EB3E0E6D5A14B8EB0FB0EB07E013036D7E497E1307EB067C497E EB1C1F01387FEB700F496C7E6E7ED803C07F00076D7E391FE003FC3AFFF007FFC0A2221D 7F9C25>120 D E %EndDVIPSBitmapFont /Fb 147[18 6[29 2[37 33 12[44 32[33 33 33 2[17 46[{ TeXBase1Encoding ReEncodeFont }9 66.4176 /Times-Bold rf %DVIPSBitmapFont: Fc cmmi8 8 1 /Fc 1 97 df96 D E %EndDVIPSBitmapFont /Fd 138[33 18 1[26 4[48 18 2[18 3[29 15[48 7[55 5[48 1[41 3[41 65[{TeXBase1Encoding ReEncodeFont }12 66.4176 /Times-Italic rf /Fe 134[33 33 48 33 33 18 26 22 33 33 33 33 52 18 2[18 33 33 22 29 33 29 33 29 9[63 2[41 37 2[37 2[59 4[48 48 1[41 1[44 1[48 5[18 18 33 33 33 33 33 33 33 33 33 33 18 17 1[17 2[22 22 2[55 1[33 32[37 2[{TeXBase1Encoding ReEncodeFont }53 66.4176 /Times-Roman rf /Ff 170[45 6[45 1[45 6[45 1[45 45 45 7[45 45 45 45 45 45 45 45 45 45 1[45 46[{TeXBase1Encoding ReEncodeFont }18 74.7198 /Courier rf /Fg 134[44 2[44 48 29 34 39 1[48 44 48 73 24 2[24 3[39 48 39 48 44 12[58 48 5[82 4[68 2[58 1[63 1[63 6[29 3[44 1[44 44 44 2[24 22 46[{ TeXBase1Encoding ReEncodeFont }31 87.1731 /Times-Bold rf /Fh 133[29 33 33 50 33 37 21 29 29 1[37 37 37 54 21 33 1[21 37 37 21 33 37 33 37 37 9[62 46 54 42 37 46 1[46 1[50 62 42 1[33 25 54 54 1[46 54 50 46 46 7[37 37 1[37 1[37 1[37 37 37 21 19 25 19 44[{TeXBase1Encoding ReEncodeFont }54 74.7198 /Times-Italic rf /Fi 87[25 17[37 27[33 37 37 54 37 37 21 29 25 37 37 37 37 58 21 37 1[21 37 37 25 33 37 33 37 33 6[46 54 1[71 54 54 46 42 50 54 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 1[58 35[42 2[{ TeXBase1Encoding ReEncodeFont }71 74.7198 /Times-Roman rf /Fj 150[21 1[37 32[46 12[37 37 37 37 37 37 37 37 37 37 1[19 46[{TeXBase1Encoding ReEncodeFont }14 74.7198 /Times-Bold rf %DVIPSBitmapFont: Fk cmmi5 5 2 /Fk 2 114 df106 D113 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fl cmr5 5 2 /Fl 2 51 df<1360EA01E0120F12FF12F11201B3A3387FFF80A2111C7B9B1C>49 DI E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fm cmss8 7 6 /Fm 6 118 df97 D<12F8AD133FEBFFC000FB13E0B512F0EB03F838FE00FC 48137C48137E143EA2141FA8143EA2147E6C137C38FE01F8EAFF07EBFFF000FB13E000F9 138038007E0018297BA720>I102 D115 DI<00F813F8B3A213011303EAFC0FEA7FFF13FEEA3FF8381FC000151B7B9920>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fn cmsy10 14.4 1 /Fn 1 3 df<0070EF038000F8EF07C06C170F6C171F007FEF3F806C6CEE7F006C6C16FE 6C6C4B5A6C6C4B5A6C6C4B5A6C6C4B5A6C6C4B5A017F4B5A6D6C4AC7FC6D6C14FE6D6C49 5A6D6C495A6D6C495A6D6C495A6D6C495A027F495A6E6C48C8FC91381FC0FE91380FE1FC 913807F3F86EB45A6E5B6E5B6F5A6FC9FC4B7E4B7E4A7F4A7F913807F3F891380FE1FC91 381FC0FE91383F807F4A486C7E02FE6D7E49486D7E49486D7E49486D7E49486D7E49486D 7E4948147F49C86C7E01FE6F7E48486F7E48486F7E48486F7E48486F7E48486F7E484816 7F48CAEA3F8000FEEF1FC048170F4817070070EF03803A3B6FBA5D>2 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fo cmss10 10.95 13 /Fo 13 118 df83 DI97 D<12FEB3A414FF010713E0011F7F017F7FB67E819038F80FFFEBE001D98000138090C7EA 7FC0153F48141F16E0150FA3ED07F0AAED0FE0A3151FED3FC07E6DEB7F8015FFD9E00313 009038F81FFE90B55A485C6D5B6D5B010F1380260001FEC7FC244079BE2F>I<49B47E01 0F13F0013F13FC4913FF90B612805A481300D807FCEB1F00D80FF0130748487F4990C7FC 123F5B127F90C9FCA312FEAA127FA36C7EA26C6C14406DEB01C06C6C13036C6C131F01FF 13FF6C90B5FC7E6C6C14806DEBFE00010F13F001011380222B7DA928>I102 D<12FEB3B3B3A9073F79BE16>108 D111 D<14FFD8FE0713E0011F7F017F7FB67E819038F80FFFEBE003D9800013 8090C7EA7FC0153F5AED1FE0A2150FA216F01507A8150F16E0A2151FA2ED3FC06C147F6D EBFF805CD9E00313009038F81FFE90B55A485C6D5B6D5B010F1380D901FEC7FC90C9FCB1 243B79A82F>I<00FC137CEB03FC130F131F133F137FEBFFC038FDFE00EAFFF85B5B5BA2 5BA290C7FCA25AB3A6162979A81F>114 DII<00FE147FB3AC15FFA25C6C5B6C130FEBC03F90B6FC6CEBFE7F6C13FC6C13E000 0390C7FC202979A72F>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fp line10 10 1 /Fp 1 46 df<12C012F012FCB4FC13C013F813FEEBFFC014F814FF15E015FEA215E01500 14F814C049C7FC13F813C090C8FC12FC12F012C01F184E8B53>45 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Fq cmex10 10.95 3 /Fq 3 81 df<17F01601EE03E0EE07C0EE0F80EE1F00163E5E16FC4B5A4B5A4B5A5E150F 4B5A4BC7FCA2157E5D14015D4A5AA24A5A140F5D141F5D143F4AC8FCA214FEA2495AA249 5AA2495AA3495AA2495AA3495AA349C9FCA25B5BA312015BA21203A25BA21207A25BA212 0FA35BA2121FA45BA2123FA65B127FAA48CAFCB3AE6C7EAA123F7FA6121FA27FA4120FA2 7FA31207A27FA21203A27FA21201A27F1200A37F7FA26D7EA36D7EA36D7EA26D7EA36D7E A26D7EA26D7EA2147FA26E7E141F81140F8114076E7EA26E7E811400157E81A26F7E6F7E 1507826F7E6F7E6F7E167C8282EE0F80EE07C0EE03E0EE01F016002CDA6D8343>18 D<12F07E127C7E7E6C7E6C7E6C7E7F6C7E6C7E137E133E133F6D7E6D7EA26D7E6D7E8013 016D7EA2147E147F8081141F816E7EA26E7EA26E7EA26E7EA26E7EA3157FA26F7EA36F7E A36F7EA2821507A3821503A282A21501A282A21500A282A382A21780A4163FA217C0A616 1F17E0AAEE0FF0B3AEEE1FE0AA17C0163FA61780A2167FA41700A25EA35EA21501A25EA2 1503A25EA215075EA3150F5EA24B5AA34B5AA34BC7FCA215FEA34A5AA24A5AA24A5AA24A 5AA24A5A5D143F92C8FC5C147E5CA2495A13035C495A495AA2495A49C9FC133E137E5B48 5A485A5B485A485A48CAFC123E5A5A5A2CDA7D8343>I80 D E %EndDVIPSBitmapFont /Fr 136[66 1[51 30 36 2[51 46 51 76 25 51 1[25 51 46 30 41 51 41 1[46 13[51 3[71 7[71 3[66 1[66 65[{ TeXBase1Encoding ReEncodeFont }23 91.3242 /Times-Bold rf %DVIPSBitmapFont: Fs cmsy5 5 1 /Fs 1 49 df48 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: Ft cmmi7 7 14 /Ft 14 120 df<010FB5FC013F148049140048B6FC2603F07EC7FC3807C01FEA0F80497E 5A123EA2003C5B127CA30078133E12F8143C0078137C14785C6C485A495A381E0F80D80F FEC8FCEA03F8211A7D9826>27 D<143C147E14E6EB01C3EB038313071402EB0F06130E13 1EA2EB3E0C133CEB7C18A2EB783013F8146014E03801F0C0EBF180EBF30013F7EA03E613 EC13F85B5B5BA31207120F121B123300E313040043130E0001131C14383800E0E0EBF7C0 EB7F00182A7FA81C>96 DI<130E131F5BA2133E131C90C7FCA7EA03E0487EEA0C78EA18 7C1230A212605B12C0A2EA01F0A3485AA2485AA2EBC180EA0F81A2381F0300A213066C5A 131CEA07F06C5A11287DA617>105 D<1407EC0F80141FA21500140E91C7FCA7EB03E0EB 07F8EB0C3C1318EB303E136013C0A248485AA2C7FCA25CA4495AA4495AA4495AA4495AA2 1238D87C1FC7FC12FC133E485AEA70F8EA7FE0EA1F80193380A61B>I<133EEA07FEA2EA 007CA213FCA25BA21201A25BA21203EC07809038E01FC0EC38600007EB61E014C3EBC187 EBC307D80FC613C09038CC038001B8C7FC13E0487E13FEEB3F80EB0FC0486C7E1303003E 1460A2127EECC0C0127CECC18012FC903801E30038F800FE0070137C1B297CA723>I<13 7CEA0FFCA2EA00F8A21201A213F0A21203A213E0A21207A213C0A2120FA21380A2121FA2 1300A25AA2123EA2127EA2EA7C18A3EAF830A21320EA786013C0EA3F80EA0F000E297EA7 15>I<3B07801FC007E03B0FE07FF01FF83B18F0E0F8783C3B30F1807CE03E903AFB007D 801ED860FEEB3F005B49133E00C14A133E5B1201A24848495BA35F4848485A1830EE01F0 A23C0F8003E003E060A218C0933801E180271F0007C013E3933800FF00000E6D48137C34 1B7D993B>I<3907801FC0390FE07FF03918F0E0F83930F1807CEBFB00D860FE133C5B5B 00C1147C5B1201A248485BA34A5AEA07C01660EC03E0A23A0F8007C0C0A2EDC180913803 C300D81F0013C7EC01FE000EEB00F8231B7D9929>I113 D<3807803E390FE0FF803818F3C13930F703C0EBFE073860FC0F13F815 8039C1F0070091C7FC1201A2485AA4485AA4485AA448C8FCA2120E1A1B7D991F>I117 D<3903E001C03907F003E0380C7807EA187C0030130314011260EB F80000C014C0A2EA01F0A2EC0180EA03E0A2EC0300EA07C0A21406A25CA200035B6D5A38 01F0E06CB45A013FC7FC1B1B7D9921>II E %EndDVIPSBitmapFont /Fu 198[42 42 42 42 42 42 42 42 50[{TeXBase1Encoding ReEncodeFont }8 74.7198 /Helvetica-Bold rf /Fv 138[51 25 1[36 4[71 25 2[25 3[41 13[81 1[66 1[51 5[81 56 4[66 1[61 2[61 61 65[{ TeXBase1Encoding ReEncodeFont }16 91.3242 /Times-BoldItalic rf %DVIPSBitmapFont: Fw cmsy7 7 2 /Fw 2 49 df0 D<13E0EA01F0EA03F8A3EA07F0A313E0A2120F 13C0A3EA1F80A21300A25A123EA35AA3127812F8A25A12100D1E7D9F13>48 D E %EndDVIPSBitmapFont /Fx 206[48 49[{TeXBase1Encoding ReEncodeFont }1 87.1731 /Helvetica-Bold rf %DVIPSBitmapFont: Fy cmsy8 8 2 /Fy 2 22 df13 D<12E012F812FEEA3F80EA0FE0EA03F8EA00FEEB3F80EB0FE0EB03F8EB00 FC143FEC0FC0EC07F0EC01FCEC007FED1FC0ED07F0ED01FCED007FEE1FC01607161FEE7F 00ED01FCED07F0ED1FC0037FC7FCEC01FCEC07F0EC0FC0023FC8FC14FCEB03F8EB0FE0EB 3F8001FEC9FCEA03F8EA0FE0EA3F80007ECAFC12F812E0CBFCAD007FB71280B812C0A22A 3B7AAB37>21 D E %EndDVIPSBitmapFont /Fz 134[33 33 1[33 1[18 33 22 2[37 37 4[15 2[18 37 37 33 13[48 4[44 52 28[37 1[37 48[{TeXBase1Encoding ReEncodeFont }18 66.4176 /Helvetica rf %DVIPSBitmapFont: FA cmsy10 10.95 17 /FA 17 111 df<007FB812FEBAFCA26C17FE3804799847>0 D<121EEA7F80A2EAFFC0A4 EA7F80A2EA1E000A0A799B19>I<0060166000F816F06C1501007E15036CED07E06C6CEC 0FC06C6CEC1F806C6CEC3F006C6C147E6C6C5C6C6C495A017E495A6D495A6D6C485A6D6C 485A6D6C48C7FC903803F07E6D6C5A903800FDF8EC7FF06E5A6E5AA24A7E4A7EECFDF890 3801F8FC903803F07E49487E49486C7E49486C7E49486C7E017E6D7E496D7E48486D7E48 48147E4848804848EC1F804848EC0FC048C8EA07E0007EED03F048150148150000601660 2C2C73AC47>I15 D<180E183F18FFEF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FE C7FCED0FF8ED7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB1FF0EB7F C04848CAFCEA07FCEA1FF0EA7FC048CBFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1F F0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801FF809138007FE0ED1FF8ED03FE9238 00FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FEEF00FF183F180E1800AE 007FB812FEBAFCA26C17FE384879B947>20 D<127012FCB4FCEA7FC0EA1FF0EA07FCEA01 FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF0EC07FE913801FF809138007FE0ED 1FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3FE0EF0FF8EF03FEEF00FF A2EF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FEC7FCED0FF8ED 7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA 07FCEA1FF0EA7FC048CBFC12FC1270CCFCAE007FB812FEBAFCA26C17FE384879B947>I< 1806180FA3181FA2181EA2183EA2187C18FC18F8EF01F01703EF07E0EF0FC0EF3F80EFFF 00EE03FCEE0FF8EE7FE0923807FF80DBFFFEC7FC49B512F8007FB612C0B600FCC8FCA26C ECFFC0D8000114F890C713FE923807FF809238007FE0EE0FF8EE03FCEE00FFEF3F80EF0F C0EF07E0EF03F01701EF00F818FC187C183EA2181EA2181FA2180FA31806383679B047> 30 D<19301978A2197C193CA2193E191EA2191F737EA2737E737EA2737E737E1A7C1A7E F21F80F20FC0F207F0007FBB12FCBDFCA26C1AFCCDEA07F0F20FC0F21F80F27E001A7C62 4F5A4F5AA24F5A4F5AA24FC7FC191EA2193E193CA2197C1978A2193050307BAE5B>33 D<0203B512F8023F14FC91B6FC010315F8D90FFEC8FCEB1FE0EB7F8001FEC9FCEA01F848 5A485A485A5B48CAFCA2123EA25AA21278A212F8A25AA2B812F817FCA217F800F0CAFCA2 7EA21278A2127CA27EA27EA26C7E7F6C7E6C7E6C7EEA00FEEB7F80EB1FE0EB0FFE0103B6 12F8010015FC143F020314F82E3679B13D>50 D<1718173C177CA217F8A2EE01F0A2EE03 E0A2EE07C0160F1780EE1F00A2163EA25EA25EA24B5AA24B5AA24B5AA24B5AA24BC7FCA2 153E157E157C5DA24A5AA24A5AA24A5AA24A5AA24AC8FCA2143EA25CA25C13015C495AA2 495AA2495AA249C9FCA2133EA25BA25BA2485AA2485AA2485A120F5B48CAFCA2123EA25A A25AA25A12602E5474C000>54 D<1518153CA2157CA2903803FC7890380FFFF8EB3E0790 387801F0EBF0004848487ED803C07FD807807FA2390F0003EFA248ECCF80001EEB07C700 3E15C01587A2140F007E15E0007C1403A2141FA2141E00FC013E13F0A2143CA2147CA214 78A214F8A214F01301A214E0A21303A214C0A21307A21480D87C0F14E0A21400007E1407 5BA2D83E1E14C0A2133E001FEC0F80133CD80F7C1400A2495B0007141E00035C00015C49 13F83900F801E03901FE07C090B5C7FCEBE3FCD803E0C8FCA25BA26C5A244D7CC52D>59 D<4AB6FC023F15F849B712FE0107EEFF80011F17E090287FE1FC007F13F02601FC010203 13F8D803F0030013FC2607C003ED3FFED80F80160FD81F00160748EF03FF484A80127E12 FE488300F0130712C0C74915FEA319FC020F15014B15F8A2F003F0A2021FED07E04B15C0 F00F80F01F00183E4A485C4D5AEF03E0EF0FC04AC7007FC7FCEE0FFE923807FFF8DA7E1F 13C0DAFE3F90C8FCED7FF84BC9FC4948CAFCA35C1303A25C1307A25C130F5CA2131F5C13 3FA291CBFC5B137EA25B13F013C040437EBD3F>80 D<0060EE018000F0EE03C0B3B3A36C 1607A200781780007C160FA26CEE1F00003F5E6C6C157E6C6C5DD807F0EC03F8D803FCEC 0FF06CB4EC3FE03B007FF003FF80011FB548C7FC010714F8010114E09026001FFEC8FC32 397BB63D>91 D<153FEC03FFEC0FE0EC3F80EC7E00495A5C495AA2495AB3AA130F5C131F 495A91C7FC13FEEA03F8EA7FE048C8FCEA7FE0EA03F8EA00FE133F806D7E130F801307B3 AA6D7EA26D7E80EB007EEC3F80EC0FE0EC03FFEC003F205B7AC32D>102 D<12FCEAFFC0EA07F0EA01FCEA007E6D7E131F6D7EA26D7EB3AA801303806D7E1300147F EC1FC0EC07FEEC00FFEC07FEEC1FC0EC7F0014FC1301495A5C13075CB3AA495AA2495A13 3F017EC7FC485AEA07F0EAFFC000FCC8FC205B7AC32D>I<126012F0B3B3B3B3B1126004 5B76C319>106 D<126012F07EA21278127CA2123C123EA2121E121FA27E7FA212077FA2 12037FA212017FA212007FA21378137CA27FA2131E131FA27F80A2130780A2130380A213 0180A2130080A21478147CA2143C143EA2141E141FA26E7EA2140781A2140381A2140181 A2140081A21578157CA2153C153EA2151E151FA2811680A2150716C0A21503ED0180225B 7BC32D>110 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: FB cmr10 10.95 25 /FB 25 112 df2 D6 D<14E0A4EB07FC90383FFF8090 B512E03901F8E3F03903E0E0FCD807C0133CD80F807FD81F007F003E80003C1580007C14 0316C00078141F00F8143F157FA47EED3F806CEC0E0092C7FC127F138013C0EA3FF013FE EA1FFF6C13FC6C13FF6C14C06C806C6C13F8011F7F130301007FECE7FF14E102E0138015 7F153FED1FC0A2003E140F127FD8FF801307A5130000FC158000F0140F1270007815005D 6C141E153E6C5C6C5C3907C0E1F03903F8EFE0C6B51280D93FFEC7FCEB0FF8EB00E0A422 497BC32D>36 D<1430147014E0EB01C0EB03801307EB0F00131E133E133C5B13F85B1201 5B1203A2485AA2120F5BA2121F90C7FCA25AA3123E127EA6127C12FCB2127C127EA6123E 123FA37EA27F120FA27F1207A26C7EA212017F12007F13787F133E131E7FEB07801303EB 01C0EB00E014701430145A77C323>40 D<12C07E12707E7E121E7E6C7E7F12036C7E7F12 007F1378137CA27FA2133F7FA21480130FA214C0A3130714E0A6130314F0B214E01307A6 14C0130FA31480A2131F1400A25B133EA25BA2137813F85B12015B485A12075B48C7FC12 1E121C5A5A5A5A145A7BC323>I<1506150FB3A9007FB912E0BA12F0A26C18E0C8000FC9 FCB3A915063C3C7BB447>43 D48 DIII<150E15 1E153EA2157EA215FE1401A21403EC077E1406140E141CA214381470A214E0EB01C0A2EB 0380EB0700A2130E5BA25B5BA25B5B1201485A90C7FC5A120E120C121C5AA25A5AB8FCA3 C8EAFE00AC4A7E49B6FCA3283E7EBD2D>I<00061403D80780131F01F813FE90B5FC5D5D 5D15C092C7FC14FCEB3FE090C9FCACEB01FE90380FFF8090383E03E090387001F8496C7E 49137E497F90C713800006141FC813C0A216E0150FA316F0A3120C127F7F12FFA416E090 C7121F12FC007015C012780038EC3F80123C6CEC7F00001F14FE6C6C485A6C6C485A3903 F80FE0C6B55A013F90C7FCEB07F8243F7CBC2D>II<1238123C123F90B612FCA316F85A16F016E00078C712010070EC03C0ED 078016005D48141E151C153C5DC8127015F04A5A5D14034A5A92C7FC5C141EA25CA2147C 147814F8A213015C1303A31307A3130F5CA2131FA6133FAA6D5A0107C8FC26407BBD2D> III<007FB912E0BA12F0A26C18E0CDFCAE007FB912E0BA12 F0A26C18E03C167BA147>61 D91 D93 D<167C903903F801FF903A1F FF078F8090397E0FDE1F9038F803F83803F001A23B07E000FC0600000F6EC7FC49137E00 1F147FA8000F147E6D13FE00075C6C6C485AA23901F803E03903FE0FC026071FFFC8FCEB 03F80006CAFC120EA3120FA27F7F6CB512E015FE6C6E7E6C15E06C810003813A0FC0001F FC48C7EA01FE003E140048157E825A82A46C5D007C153E007E157E6C5D6C6C495A6C6C49 5AD803F0EB0FC0D800FE017FC7FC90383FFFFC010313C0293D7EA82D>103 D105 D108 D<2701F801FE14FF00FF902707FFC00313E0913B1E07E00F03F0913B7803 F03C01F80007903BE001F87000FC2603F9C06D487F000101805C01FBD900FF147F91C75B 13FF4992C7FCA2495CB3A6486C496CECFF80B5D8F87FD9FC3F13FEA347287DA74C>I<39 01F801FE00FF903807FFC091381E07E091387803F000079038E001F82603F9C07F000113 8001FB6D7E91C7FC13FF5BA25BB3A6486C497EB5D8F87F13FCA32E287DA733>I<14FF01 0713E090381F81F890387E007E01F8131F4848EB0F804848EB07C04848EB03E0000F15F0 4848EB01F8A2003F15FCA248C812FEA44815FFA96C15FEA36C6CEB01FCA3001F15F86C6C EB03F0A26C6CEB07E06C6CEB0FC06C6CEB1F80D8007EEB7E0090383F81FC90380FFFF001 0090C7FC282A7EA82D>I E %EndDVIPSBitmapFont %DVIPSBitmapFont: FC cmr7 7 13 /FC 13 117 df<1306130C13181330136013E0EA01C0EA0380A2EA07005A120E121EA212 1C123CA35AA512F85AAB7E1278A57EA3121C121EA2120E120F7EEA0380A2EA01C0EA00E0 136013301318130C13060F3B7AAB1A>40 D<12C012607E7E7E120E7EEA0380A2EA01C013 E0120013F0A213701378A3133CA5133E131EAB133E133CA51378A3137013F0A213E01201 13C0EA0380A2EA0700120E120C5A5A5A5A0F3B7DAB1A>I<140EB3A2B812E0A3C7000EC8 FCB3A22B2B7DA333>43 D48 D<13381378EA01F8121F12FE12E01200B3AB48 7EB512F8A215267BA521>I<13FF000313E0380E03F0381800F848137C48137E00787F12 FC6CEB1F80A4127CC7FC15005C143E147E147C5C495A495A5C495A010EC7FC5B5B903870 018013E0EA0180390300030012065A001FB5FC5A485BB5FCA219267DA521>I61 D91 D93 D<133F3801FFE03803E1F0380F80F838 1F007C143E123E007E131E141F127C12FCA2B6FCA200FCC7FCA4127C127E1403123E6C13 07380F800E3807C01C3803E0783800FFE0EB3F80181C7E9A1E>101 DI108 D<13C0A41201A312031207120F121FB512E0A23807C000AC1430A73803E0 60A23801F0C03800FF80EB3F0014257FA31A>116 D E %EndDVIPSBitmapFont %DVIPSBitmapFont: FD cmmi10 10.95 36 /FD 36 122 df11 DI26 D<020FB512FE027F14FF49B7FC1307011F15FE903A3FE03FE00090387F000F 01FE6D7E4848130348488048481301485A5B121F5B123F90C7FC5A127EA2150300FE5D5A A24B5AA2150F5E4B5AA2007C4AC7FC157E157C6C5C001E495A001FEB07E0390F800F8026 03E07EC8FC3800FFF8EB3FC030287DA634>I<121EEA7F80A2EAFFC0A4EA7F80A2EA1E00 0A0A798919>58 D<121EEA7F8012FF13C0A213E0A3127FEA1E601200A413E013C0A31201 1380120313005A120E5A1218123812300B1C798919>I<180E183F18FFEF03FEEF0FF8EF 3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF80DB03FEC7FCED1FF8ED7FE0913801FF80DA 07FEC8FCEC1FF0EC7FC04948C9FCEB07FCEB1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC0 48CBFCA2EA7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1F F0EC07FE913801FF809138007FE0ED1FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE9338 00FF80EF3FE0EF0FF8EF03FEEF00FF183F180E383679B147>II<127012FCB4FCEA 7FC0EA1FF0EA07FCEA01FF38007FC0EB1FF0EB07FCEB01FF9038007FC0EC1FF8EC07FE91 3801FF809138007FE0ED0FF8ED03FE923800FF80EE3FE0EE0FF8EE03FE933800FF80EF3F E0EF0FF8EF03FEEF00FFA2EF03FEEF0FF8EF3FE0EFFF80933803FE00EE0FF8EE3FE0EEFF 80DB03FEC7FCED0FF8ED7FE0913801FF80DA07FEC8FCEC1FF8EC7FC04948C9FCEB07FCEB 1FF0EB7FC04848CAFCEA07FCEA1FF0EA7FC048CBFC12FC1270383679B147>I67 D<49B912C0A3D9000190C71201F0003F4B 151F190F1A80020316075DA314075D1A00A2140F4BEB0380A205075B021FED000E4B92C7 FC5FA2023F141E5D173EEE01FE4AB55AA3ED800102FF6D5A92C71278A34915705C191C05 F0133C01034B13384A167894C71270A2010717F04A5E180161010F16034A4B5AA2180F01 1F4CC7FC4A5D187E013F16FE4D5A4A140F017F15FFB95AA260423E7DBD43>69 D71 D79 D83 D<48B912FCA25A913A0003FE000F01F84A1301D807E0EE00F84913074917 78000F5D90C7FC001E140FA2001C4B1470123C0038141FA200785D1270033F15F000F018 E0485DC81600157FA25EA215FFA293C9FCA25CA25DA21403A25DA21407A25DA2140FA25D A2141FA25DA2143FA25DA2147FA214FF497F001FB612FCA25E3E3D7FBC35>I86 D<151EED7F80913801F1C0EC03C1EC07 C0ED80E0EC0F005C141E91383E01C0147CA214F81503D901F01380A21303ECE007010714 005D90380FC00EA2151E90381F801C153C5D133F4A5A5D140149485A017E5B14074AC7FC EBFE1E13FC5C5C5C3801F9E0EBFBC0A2EBFF8091C8FC5B5B5B5BA212031207120F121F12 3D127800F0140300E0EC0780C66CEB0F000178131E157C6D13F04A5A90381E0F80D90FFE C7FCEB03F823417FBF26>96 DI101 D<143C14FEA21301A314FCEB00701400 AD137E3801FF803803C7C0EA0703000F13E0120E121C13071238A2EA780F007013C0A2EA F01F14801200133F14005B137EA213FE5BA212015B0003130E13F0A20007131EEBE01CA2 143CEBC0381478147014E013C13803E3C03801FF00EA007C173E7EBC1F>105 DI IIIIII<91381F800C9138FFE01C903903F0707C90390FC0387890391F 801CF890383F000F137E4914F000011407485A485A16E0485A121F150F484814C0A3007F 141F491480A300FF143F90C71300A35D48147EA315FE007E495A1403A26C13074A5A381F 801D000F13793807C1F33901FFC3F038007F03130014075DA3140F5DA3141F5DA2143F14 7F90381FFFFE5BA2263A7DA729>III<147014FC1301A2 5CA21303A25CA21307A25CA2130FA25CA2007FB512F0B6FC15E039001F8000133FA291C7 FCA25BA2137EA213FEA25BA21201A25BA21203A25BA21207EC01C013E01403000F1480A2 EBC0071500140E141E5C000713385C3803E1E03801FF80D8003EC7FC1C3A7EB821>I<13 7C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F121C010715801238163FEA780F 0070491400A2D8F01F5C5C0000157E133F91C712FEA2495C137E150113FE495CA2150300 01161C4914F0A21507173CEEE038150F031F1378000016706D133F017C017313F0017E01 E313E0903A3F03C1F1C0903A0FFF007F80D901FCEB1F002E297EA734>I<017E147848B4 EB01FC2603C7C013FED807031303000F13E0120E121C0107130100381400167ED8780F14 3E00705B161EEAF01F4A131C1200133F91C7123C16385B137E167801FE14705B16F016E0 120149EB01C0A2ED0380A2ED0700A20000140E5D6D133C017C5B6D5B90381F03C0903807 FF80D901FCC7FC27297EA72C>I<017CEE038048B40207EB0FE02603C7C090391F801FF0 EA0703000F7F000E153F001C16000107160F003817074C1303D8780F027E130100705B18 00D8F01F14FE4A4914E01200133FDA000114014C14C05B137E0303140301FE4A14805BA2 F0070000011407494A5B180EA260A2030F5C12006D011F5C017C496C5B017E0139495A6D 903870F80390281F81E07C0FC7FC903A07FFC01FFE010090380007F03C297EA741>II<137C48B4EC03802603C7C0EB0FC0EA0703000F7F000E151F001C16801307 1238163FD8780F150000705BA2D8F01F5C4A137E1200133F91C712FE5E5B137E150113FE 495CA2150300015D5BA215075EA2150F151F00005D6D133F017C137F017E13FF90393F03 DF8090380FFF1FEB01FC90C7123F93C7FCA25DD80380137ED80FE013FE001F5C4A5AA248 48485A4A5A6CC6485A001C495A001E49C8FC000E137C380781F03803FFC0C648C9FC2A3B 7EA72D>I E %EndDVIPSBitmapFont /FE 133[34 39 39 58 39 44 24 34 34 1[44 44 44 63 24 39 1[24 44 44 24 39 44 39 44 44 9[73 1[63 48 44 53 1[53 63 1[73 48 2[29 63 63 1[53 1[58 53 53 14[44 3[22 29 42[44 2[{TeXBase1Encoding ReEncodeFont }44 87.1731 /Times-Italic rf /FF 87[29 16[87 44 1[39 39 24[39 44 44 63 44 44 24 34 29 44 44 44 44 68 24 44 24 24 44 44 29 39 44 39 44 39 6[53 2[82 63 63 53 48 58 1[48 63 63 77 53 63 34 29 63 63 48 53 63 58 58 63 5[24 24 44 44 44 44 44 44 44 44 44 44 24 22 29 22 49 1[29 29 29 68 73 33[48 48 2[{ TeXBase1Encoding ReEncodeFont }78 87.1731 /Times-Roman rf /FG 167[61 86 1[66 56 61 66 1[61 71 66 76 56 66 1[25 66 71 56 61 66 66 66 66 65[{TeXBase1Encoding ReEncodeFont }21 91.3242 /Helvetica-Bold rf %DVIPSBitmapFont: FH cmsy9 9 2 /FH 2 104 df102 D<12FCEAFFC0EA07F0EA01FC6C7E137F7F80131FB3A580 130F6D7E6D7EEB01FC9038007FC0EC1FE0EC7FC0903801FC00EB03F0495A495A131F5CB3 A5133F91C7FC5B13FE485AEA07F0EAFFC000FCC8FC1B4B7BB726>I E %EndDVIPSBitmapFont /FI 137[39 39 22 31 26 1[39 1[39 61 22 39 1[22 39 39 26 35 39 35 39 35 38[22 10[22 20 26 45[{TeXBase1Encoding ReEncodeFont } 23 78.8709 /Times-Roman rf /FJ 144[44 2[18 2[18 5[39 21[66 5[61 1[53 3[53 18[22 46[{TeXBase1Encoding ReEncodeFont }9 78.8709 /Helvetica-Oblique rf /FK 107[26 26 24[39 39 39 57 39 44 22 39 26 44 44 44 44 66 18 39 1[18 44 44 22 44 44 39 44 44 9[74 2[48 5[57 66 5[61 48 1[57 2[53 80 4[22 22 44 44 44 44 44 44 44 44 44 44 1[22 26 22 2[26 26 2[70 34[39 2[{TeXBase1Encoding ReEncodeFont }55 78.8709 /Helvetica rf /FL 134[44 2[44 48 26 44 3[48 48 1[22 2[22 3[44 1[44 48 44 12[48 53 57 4[66 9[57 57 57 6[26 58[{ TeXBase1Encoding ReEncodeFont }21 78.8709 /Helvetica-Bold rf /FM 134[42 42 1[42 46 23 42 28 2[46 46 69 18 2[18 46 46 23 46 46 42 1[46 11[60 51 3[55 65 7[65 51 1[60 1[55 12[46 1[46 1[46 46 1[23 28 23 44[{TeXBase1Encoding ReEncodeFont } 34 83.022 /Helvetica-Oblique rf /FN 87[36 45[54 4[60 30 54 36 2[60 60 1[24 2[24 60 1[30 60 60 54 60 60 13[72 3[84 1[90 1[72 2[78 2[72 24[30 44[{TeXBase1Encoding ReEncodeFont }24 107.929 /Helvetica-Oblique rf /FO 138[81 44 3[81 81 81 118 37 2[37 1[81 44 74 1[74 21[111 5[103 1[89 3[96 62[81 2[{TeXBase1Encoding ReEncodeFont }17 132.835 /Helvetica-BoldOblique rf /FP 105[42 34[37 3[42 42 1[17 4[42 1[42 3[42 10[50 5[50 22[42 6[42 42 42 1[21 46[{TeXBase1Encoding ReEncodeFont }15 74.7198 /Helvetica-Oblique rf /FQ 171[101 111 120 2[129 120 138 3[46 2[101 2[120 120 120 65[{TeXBase1Encoding ReEncodeFont }11 166.044 /Helvetica-BoldOblique rf end %%EndProlog %%BeginSetup %%Feature: *Resolution 600dpi TeXDict begin %%PaperSize: a4 %%BeginPaperSize: a4 a4 %%EndPaperSize %%EndSetup %%Page: 1 1 1 0 bop Black .8 TeXcolorgray -4 -39 a FQ(BIOINFORMA)-15 b(TICS)p Black 3353 -126 a FP(V)-6 b(ol.)20 b(1)g(no)m(.)g(1)g(2002) 3555 -34 y(P)m(ages)g(1\2269)p Black Black -275 74 4185 7 v Black Black 771 285 a FO(Ef\002cient)37 b(Multiple)g(Genome)g (Alignment)p Black Black 771 480 a FN(Michael)30 b(H)1263 478 y(\250)1251 480 y(ohl,)g(Stef)m(an)g(K)m(ur)t(tz)46 b(and)30 b(Enno)g(Ohleb)n(usch)p Black Black 771 688 a FM(F)l(aculty)22 b(of)i(T)-10 b(echnology)i(,)23 b(Univ)n(ersity)f (of)i(Bielef)n(eld,)h(P)-15 b(.O)m(.)23 b(Bo)n(x)f(10)i(01)f(31,)g (Bielef)n(eld,)i(D-33501,)771 788 y(Ger)r(man)o(y)p -275 954 V Black -275 1112 a FL(ABSTRA)m(CT)-275 1211 y(Motiv)n(ation:)j FK(T)-9 b(o)27 b(allo)o(w)f(a)h(direct)g(compar)q(ison)g(of)g(the)g (genomic)-275 1311 y(DNA)f(sequences)h(of)g(suf\002ciently)f(similar)g (organisms)o(,)g(there)g(is)-275 1411 y(an)c(urgent)f(need)g(f)n(or)h (softw)o(are)g(tools)f(that)h(can)g(align)e(more)i(than)-275 1510 y(tw)o(o)g(genomic)f(sequences)o(.)-275 1610 y FL(Results:)36 b FK(W)n(e)g(de)n(v)n(eloped)e(ne)n(w)i(algor)q(ithms)e(and)i(a)f (softw)o(are)-275 1709 y(tool)54 b(\223Multiple)f(Genome)i(Aligner\224) f(\()p FJ(MGA)h FK(f)n(or)g(shor)s(t\))h(that)-275 1809 y(ef\002ciently)24 b(computes)h(m)o(ultiple)d(genome)i(alignments)f(of) h(large)o(,)-275 1909 y(closely)52 b(related)g(DNA)g(sequences)o(.)h(F) n(or)f(e)n(xample)o(,)f(it)h(can)-275 2008 y(align)i(85\045)i(percent)g (of)g(the)g(complete)f(genomes)g(of)h(six)-275 2108 y(human)30 b(adeno)o(vir)q(uses)h(\(a)n(v)n(er)o(age)i(length)d(35,305)g(bp)m(.\)) h(in)g(159)-275 2208 y(seconds)o(.)d(An)f(alignment)f(of)h(74\045)h(of) f(the)g(complete)g(genomes)-275 2307 y(of)18 b(three)f(of)h(str)o(ains) g(of)g FJ(E.)g(coli)24 b FK(\(lengths:)17 b(5,528,445;)g(5,498,450;) -275 2407 y(4,639,221)k(bp)m(.\))h(is)g(produced)f(in)h(30)f(min)o (utes)o(.)-275 2506 y FL(A)m(v)n(ailability:)f FK(The)g(softw)o(are)g FJ(MGA)g FK(is)g(a)n(v)n(ailab)n(le)f(free)h(of)g(charge)-275 2606 y(f)n(or)32 b(non-commercial)g(research)h(institutions)o(.)e(F)n (or)i(details)e(see)-275 2706 y FI(http://bibiserv)-5 b(.techf)o(ak.uni-)t(bielefeld.de/mga/)p FK(.)-275 2805 y FL(Contact:)23 b FH(f)p FK(kur)s(tz,)g(enno)p FH(g)p FK(@techf)n(ak.uni-bielef)n(eld.de)-275 3013 y FG(INTR)n(ODUCTION)-275 3138 y FF(The)43 b(DN)m(A)h(sequences)d(of)i(entire)h(genomes)d(are)j (being)e(de-)-275 3239 y(termined)g(at)h(a)g(rapid)f(rate.)h(Recently) -6 b(,)42 b(there)h(is)g(a)g(gro)n(wing)-275 3339 y(scienti\002c)34 b(interest)f(in)h(sequencing)d(dif)n(ferent)i(strains)h(of)f(bac-)-275 3439 y(teria)k(and)f(other)g(closely)g(related)g(or)n(ganisms.)g(F)o (or)h(e)o(xample,)-275 3540 y(the)i(genomes)e(of)i(se)n(v)o(eral)f (strains)g(of)h FE(Esc)o(heric)o(hia)e(coli)i FF(and)-275 3640 y FE(Chlamydophila)56 b(pneumoniae)f FF(ha)n(v)o(e)i(already)g (been)g(com-)-275 3741 y(pletely)23 b(sequenced.)e(When)i(the)h (genomic)e(DN)m(A)i(sequences)e(of)-275 3841 y(closely)37 b(related)h(or)n(ganisms)e(become)h(a)n(v)n(ailable,)g(one)g(of)h(the) -275 3941 y(\002rst)29 b(questions)d(researchers)g(ask)i(is)g(ho)n(w)f (the)h(genomes)e(align.)-275 4042 y(Although)c(a)i(number)f(of)g(softw) o(are)h(tools)f(aimed)g(at)i(comparing)-275 4142 y FE(two)h FF(genomic)f(DN)m(A)h(sequences)e(e)o(xist)h(\(Delcher)h FE(et)g(al.)p FF(,)g(1999;)-275 4242 y(Batzoglu)42 b FE(et)h(al.)p FF(,)f(2000;)g(K)n(ent)g(&)h(Zahler,)g(2000\),)e(there)h (is)-275 4343 y(an)32 b(immediate)g(need)g(for)h(\223reliable)f(and)g (automatic)g(softw)o(are)-275 4443 y(for)i(aligning)g(three)g(or)g (more)g(genomic)f(sequences\224)f(\(Miller,)-275 4544 y(2001\).)40 b(T)-7 b(o)42 b(our)f(kno)n(wledge,)f(this)i(paper)e (presents)h(the)h(\002rst)-275 4644 y(softw)o(are)21 b(tool)g(for)h(this)g(task.)-203 4744 y(It)52 b(should)e(be)h(pointed)f (out)h(that)g(an)g(alignment)f(of)h(the)-275 4845 y(genomes)21 b(\(genomic)g(DN)m(A)i(sequences\))d(of)j(se)n(v)o(eral)e(or)n(ganisms) -275 4945 y(mak)o(es)39 b(sense)g(only)h(if)g(the)g(or)n(ganisms)f(are) h(closely)f(related.)-275 5046 y(Otherwise,)25 b(if)h(the)o(y)e(are)h (not)h(closely)e(related,)h(one)g(has)f(to)i(tak)o(e)-275 5146 y(genome)38 b(rearrangements)f(into)j(account.)d(In)j(this)g (case,)e(one)-275 5246 y(w)o(ould)25 b(\002rst)h(try)g(to)g(identify)f (syntenic)f(re)o(gions)g(and)h(then)g(align)-275 5347 y(these)c(instead)g(of)g(the)g(entire)h(genomes.)-203 5447 y(Numerous)63 b(multiple)g(alignment)g(methods)g(ha)n(v)o(e)g (been)1892 1113 y(published)41 b(in)j(the)f(bioinformatics)f (literature,)h(b)n(ut)g(the)g(v)n(ast)1892 1214 y(literature)h(is)h (almost)f(entirely)g(geared)f(to)n(w)o(ard)g(comparison)1892 1314 y(of)c(protein)g(sequences)f(\(because)g(in)i(the)f(past,)h (genomes)e(of)1892 1415 y(se)n(v)o(eral)18 b(similar)h(or)n(ganisms)f (were)h(not)g(a)n(v)n(ailable\).)f(V)-5 b(irtually)19 b(all)1892 1516 y(of)j(the)g(global)g(multiple)h(alignment)e(methods)g (used)h(in)g(practice)1892 1617 y(are)36 b(v)n(ariants)h(of)f(either)h (\(1\))g(\223iterati)n(v)o(e)f(pairwise)h(alignment\224)1892 1718 y(or)28 b(\(2\))h(\223anchor)n(-based)c(multiple)k(alignment.)-6 b(\224)27 b(Methods)h(from)1892 1818 y(cate)o(gory)55 b(\(1\))h(follo)n(w)h(a)f(general)g(strate)o(gy)g(of)g(iterati)n(v)o (ely)1892 1919 y(mer)n(ging)29 b(tw)o(o)g(multiple)h(alignments)f(of)g (tw)o(o)h(disjoint)f(subsets)1892 2020 y(of)21 b(sequences)d(into)j(a)g (single)g(multiple)g(alignment)f(of)h(the)g(union)1892 2121 y(of)30 b(those)f(subsets.)g(If,)h(as)g(usually)f(done,)f(the)i (global)f(pairwise)1892 2222 y(alignment)e(of)h(tw)o(o)h(genomic)d(DN)m (A)j(sequences)d FD(S)3510 2236 y FC(1)3575 2222 y FF(and)i FD(S)3786 2236 y FC(2)3851 2222 y FF(is)1892 2322 y(computed)e(by)i (standard)f(dynamic)g(programming)f(algorithms)1892 2423 y(\(which)34 b(requires)g FD(O)s FB(\()p FA(j)p FD(S)2673 2437 y FC(1)2710 2423 y FA(j)d(\001)g(j)p FD(S)2903 2437 y FC(2)2940 2423 y FA(j)p FB(\))36 b FF(time,)f(where)f FA(j)p FD(S)5 b FA(j)36 b FF(denotes)1892 2524 y(the)45 b(length)f(of)i(a)f(sequence)e FD(S)5 b FF(\),)45 b(it)h(is)g(clear)f (that)h(such)e(an)1892 2625 y(iterati)n(v)o(e)24 b(method)g(cannot)g (be)g(used)g(in)i(practice)e(to)h(align)f(DN)m(A)1892 2726 y(sequences)19 b(of)i(entire)h(genomes.)1964 2826 y(Methods)j(from)h(cate)o(gory)d(\(2\))j(try)g(to)g(identify)f (substrings)g(of)1892 2927 y(the)i(sequences)d(under)i(consideration)f (that)i(are)g(v)o(ery)f(lik)o(ely)h(be)1892 3028 y(part)19 b(of)h(a)g(global)f(multiple)g(alignment.)g(These)g(substrings)g(form) 1892 3129 y(\223anchors\224)28 b(in)j(the)g(sequences)d(to)j(be)f (aligned.)g(Consequently)-6 b(,)1892 3230 y(a)55 b(method)f(of)i(cate)o (gory)d(\(2\))i(\002rst)i(aligns)d(those)h(anchors)1892 3330 y(and)f(subsequently)f(closes)h(the)h(gaps,)f(i.e.,)h(it)h(aligns) f(the)1892 3431 y(substrings)34 b(between)g(the)i(anchors.)e(The)h (latter)h(can)f(be)g(done)1892 3532 y(by)e(applying)f(the)i(same)f (method)g(recursi)n(v)o(ely)f(to)i(the)g(gaps\227)1892 3633 y(yielding)53 b(a)i(di)n(vide)f(and)g(conquer)e(method\227b)n(ut)i (also)g(by)1892 3734 y(an)o(y)48 b(other)g(alignment)g(method.)f (Anchor)n(-based)g(alignment)1892 3834 y(methods)21 b(are)i(well)h (suited)e(for)h(aligning)f(v)o(ery)g(long)g(sequences.)1892 3935 y(The)44 b(softw)o(are)h(tool)f FE(MUMmer)i FF(\(Delcher)e FE(et)h(al.)p FF(,)g(1999\))e(is)1892 4036 y(an)33 b(impressi)n(v)o(e)f (implementation)g(of)h(such)g(a)g(method.)g(In)g(our)1892 4137 y(opinion,)22 b(it)j(is)f(a)g(major)f(breakthrough)e(to)n(w)o(ard) i(the)h(solution)f(of)1892 4238 y(the)c(alignment)g(problem)g(of)h FE(two)g FF(suf)n(\002ciently)f(similar)h(genomic)1892 4338 y(DN)m(A)d(sequences.)e(Lik)o(e)i(an)o(y)g(other)f(e)o(xisting)h (method,)e(ho)n(we)n(v)o(er)m(,)1892 4439 y FE(MUMmer)22 b FF(cannot)e(align)i(more)f(than)f(tw)o(o)i(sequences.)1964 4540 y(In)50 b(this)g(paper)m(,)e(we)h(present)g(the)h(anchor)n(-based) d(method)1892 4641 y FE(MGA)28 b FF(that)h(is)f(capable)f(of)h (aligning)g(three)g(or)g(more)g(genomes.)1892 4741 y(The)46 b(method)g(is)h(di)n(vided)f(into)h(three)f(phases.)f(In)i(the)g (\002rst)1892 4842 y(phase,)c(a)h(no)o(v)o(el)f(algorithm)h(detects)g (all)h FE(maximal)e(multiple)1892 4943 y(e)n(xact)18 b(matc)o(hes)f FF(\()p FE(multiMEM)s FF(s\))j(whose)e(length)g(e)o (xceeds)e(a)j(gi)n(v)o(en)1892 5044 y(threshold.)27 b(Roughly)g (speaking,)g(a)i FE(multiMEM)j FF(is)d(a)g(sequence)1892 5145 y(that)47 b(occurs)f(in)i(all)g(genomes)d(to)j(be)f(aligned)f(and) h(cannot)1892 5245 y(simultaneously)32 b(be)h(e)o(xtended)f(to)i(the)g (left)g(or)g(right)g(in)g(e)n(v)o(ery)1892 5346 y(genome.)g(Our)i(no)o (v)o(el)f(algorithm)h(uses)f FD(O)s FB(\()p FD(k)s(n)d FB(+)f FD(r)s FB(\))37 b FF(time)f(in)1892 5447 y(the)30 b(w)o(orst)g(case,)f(where)h FD(k)j FF(is)e(the)f(number)f(of)h (genomes,)e FD(n)i FF(is)p Black -275 5630 V -256 5727 a Fz(c)-275 5729 y Fy(\015)18 b Fz(Oxf)n(ord)h(Univ)n(ersity)g(Press)g (2000)3187 b Fx(1)p Black eop %%Page: 2 2 2 1 bop Black -275 -76 4185 4 v Black -275 166 a FF(their)32 b(total)g(length,)e(and)h FD(r)k FF(is)d(the)g(number)e(of)i(right)f (maximal)-275 266 y(multiple)43 b(e)o(xact)f(matches.)g(Its)i(ef)n (\002cient)e(implementation)g(is)-275 365 y(based)50 b(on)h(the)g(virtual)h(suf)n(\002x)f(tree)g(\(Kasai)g FE(et)h(al.)p FF(,)f(2001\))-275 464 y(which)f(requires)h(only)f(5)h (bytes)g(per)g(input)g(character)-5 b(.)50 b(By)-275 564 y(contrast,)28 b(other)h(implementations)e(of)i(the)g(suf)n(\002x)g (tree)g(require)-275 663 y(much)37 b(more)h(space.)f(F)o(or)i(e)o (xample,)d(our)i(e)o(xperiments)e(sho)n(w)-275 762 y(that)c FE(MUMmer)r FF(')-5 b(s)30 b(implementation)h(uses)g(50)g(bytes)g(per)g (input)-275 862 y(character)m(,)19 b(see)j(the)f(section)g(on)g (Experiments.)-203 961 y(In)43 b(the)g(second)f(phase,)f FE(MGA)j FF(computes)d(the)i(\223anchors\224,)-275 1060 y(consisting)g(of)h(the)g(longest)g(non-o)o(v)o(erlapping)c(sequence)i (of)-275 1159 y FE(multiMEM)s FF(s)33 b(that)h(occur)e(in)h(the)g(same) f(order)h(in)g(each)f(of)h(the)-275 1259 y(genomes.)42 b(This)j(is)g(achie)n(v)o(ed)d(in)j(time)f FD(O)s FB(\()p FD(k)e FA(\001)c FD(m)1406 1226 y FC(2)1443 1259 y FB(\))45 b FF(in)g(the)-275 1358 y(w)o(orst)37 b(case,)e(where)h FD(m)h FF(is)g(the)g(number)e(of)h FE(multiMEM)s FF(s,)h(by)-275 1457 y(using)31 b(an)h(ef)n(\002cient)g(graph)e(algorithm)i(that)g (seems)f(to)h(be)g(folk)-275 1557 y(kno)n(wledge)21 b(\(Arkin)j(&)g (Silv)o(erber)n(g,)g(1987;)e(V)-5 b(ingron)23 b(&)h(Ar)n(gos,)-275 1656 y(1989;)c(Gus\002eld,)h(1997\).)-203 1755 y(In)53 b(the)f(third)h(phase,)e FE(MGA)h FF(closes)g(the)h(gaps)e(between)-275 1855 y(the)40 b(anchors.)f(First)j(this)f(is)h(done)d(by)h(recursi)n(v) o(ely)f(applying)-275 1954 y(the)47 b(same)g(method)g(a)g(certain)h (number)e(of)h(times,)h(thereby)-275 2053 y(lo)n(wering)39 b(the)g(length)g(threshold)g(for)g(the)h FE(multiMEM)s FF(s.)g(The)-275 2153 y(gaps)25 b(that)h(are)g(left)h(o)o(v)o(er)e(are) h(handled)e(as)i(follo)n(ws:)h(Short)f(gaps)-275 2252 y(are)34 b(closed)f(by)g(the)h(multiple)g(sequence)e(alignment)h (program)-275 2351 y(ClustalW)20 b(\(Thompson)e FE(et)i(al.)p FF(,)f(1994\),)g(which)g(is)h(a)f(widely)h(used)-275 2451 y(implementation)d(of)h(an)f(iterati)n(v)o(e)h(multiple)g (alignment)f(method.)-275 2550 y(Long)32 b(gaps)f(remain)g(unaligned)g (in)h(order)g(to)g(cope)g(with)g(long)-275 2649 y(insertions,)21 b(deletions,)f(etc.)-203 2749 y FE(MGA)47 b FF(is)g(not)f(only)g(a)h (multiple)f(alignment)g(tool.)g(It)h(can)-275 2848 y(also)35 b(ef)n(\002ciently)g(align)g(just)h(tw)o(o)f(genomes.)e(Applied)i(to)g (tw)o(o)-275 2947 y(sequences,)26 b(it)k(pro)o(vides)d(se)n(v)o(eral)h (important)g(adv)n(antages)e(o)o(v)o(er)-275 3047 y FE(MUMmer)r FF(:)p Black -275 3199 a FA(\017)p Black 79 w FF(While)35 b FE(MUMmer)g FF(computes)e(maximal)g(unique)g(matches)-151 3298 y(\()p FE(MUM)s FF(s,)23 b(i.e.)f(matches)g(that)g(occur)g(once)f (in)i(each)e(genome\))-151 3397 y(to)60 b(anchor)d(alignments,)h FE(MGA)i FF(uses)e(maximal)h(e)o(xact)-151 3497 y(matches)64 b(\()p FE(MEM)s FF(s\).)h(These)g(are)f(more)g(general)g(than)-151 3596 y FE(MUM)s FF(s,)30 b(as)f(the)o(y)g(are)g(allo)n(wed)g(to)g (occur)g(more)g(than)g(once)-151 3695 y(in)22 b(each)f(genome.)f(Ho)n (we)n(v)o(er)m(,)g(if)i(the)g(user)f(requests)g FE(MUM)s FF(s,)-151 3794 y(then)g FE(MGA)h FF(also)f(deli)n(v)o(ers)f(them)i(as) f(anchors.)p Black -275 3948 a FA(\017)p Black 79 w FF(The)35 b(computation)d(of)j FE(MEM)s FF(s)f(or)g FE(MUM)s FF(s)h(is)g(based)e (on)h(a)-151 4047 y(virtual)27 b(suf)n(\002x)g(tree.)f(This)h(inde)o(x) f(structure)g(requires)g(much)-151 4147 y(less)17 b(space)e(than)h FE(MUMmer)r FF(s)f(implementation)g(of)h(the)g(suf)n(\002x)-151 4246 y(tree)22 b(\(see)f(abo)o(v)o(e\),)e(and)i(it)h(deli)n(v)o(ers)e (matches)h(f)o(aster)-5 b(.)p Black -275 4400 a FA(\017)p Black 79 w FF(Despite)42 b(the)f(more)g(general)f(notion)h(of)g (matches,)g FE(MGA)-151 4499 y FF(al)o(w)o(ays)50 b(deli)n(v)o(ers)e (the)i(anchors)e(for)h(tw)o(o)h(sequences)e(in)-151 4598 y FD(O)s FB(\()p FD(m)15 b FB(log)i FD(m)p FB(\))28 b FF(time,)g(where)f FD(m)h FF(is)g(the)g(number)e(of)i FE(MUM)s FF(s)-151 4698 y(or)21 b FE(MEM)s FF(s,)g(using)f(the)g (algorithm)h(of)f(\(Joseph)g FE(et)h(al.)p FF(,)f(1992\).)p Black -275 4851 a FA(\017)p Black 79 w FF(T)-7 b(o)26 b(close)f(the)h(gaps,)e FE(MGA)i FF(applies)f(the)g(greedy)g(alignment) -151 4950 y(algorithm)41 b(of)g(\(Ukk)o(onen,)f(1985\).)g(This)h (aligns)g(tw)o(o)h(se-)-151 5050 y(quences)25 b(of)h(length)g FD(r)k FF(and)25 b FD(r)768 5017 y Fw(0)818 5050 y FF(in)h FD(O)s FB(\()p FD(e)f FA(\001)f FB(min)o(\()p FD(r)m(;)15 b(r)1444 5017 y Fw(0)1468 5050 y FB(\)\))28 b FF(time,)-151 5149 y(where)23 b FD(e)g FF(is)g(their)g(edit)g(distance.)f(Thus,)g(it) i(gi)n(v)o(es)e(a)h(speedup)-151 5248 y(o)o(v)o(er)h(the)g FD(O)s FB(\()p FD(r)h FA(\001)e FD(r)423 5215 y Fw(0)446 5248 y FB(\))i FF(standard)e(dynamic)g(programming)f(al-)-151 5348 y(gorithm)h(used)f(in)h FE(MUMmer)h FF(for)e(the)h(same)f(task,)h (pro)o(vided)-151 5447 y(the)f(sequences)d(to)j(be)f(aligned)f(are)h (similar)-5 b(.)p Black 1892 166 a FA(\017)p Black 79 w FF(While)28 b FE(MUMmer)g FF(restricts)f(the)g(length)f(of)h(the)f (gaps)g(to)h(be)2016 266 y(closed,)34 b FE(MGA)g FF(aligns)g(gaps)f(of) h(arbitrary)g(length,)f(if)i(the)o(y)2016 365 y(are)26 b(suf)n(\002ciently)f(similar)h(according)d(to)j(a)f(percent)g (identity)2016 465 y(score)c(speci\002ed)g(by)g(the)g(user)-5 b(.)1964 639 y(Our)30 b(e)o(xperiments)e(sho)n(w)h(that)h FE(MGA)g FF(is)h(al)o(w)o(ays)e(f)o(aster)h(than)1892 739 y FE(MUMmer)22 b FF(\(for)f(tw)o(o)g(strains)g(of)h FE(E.coli)f FF(o)o(v)o(er)f(\002)n(v)o(e)g(times)i(f)o(aster\),)1892 838 y(using)f(less)i(than)e(18\045)h(of)g(the)g(space)f(\(for)i(tw)o(o) f(strains)g(of)g FE(E.coli)1892 938 y FF(only)f(8\045)g(of)g(the)g (space\).)1964 1037 y(The)29 b(rest)g(of)g(the)g(paper)f(is)h(or)n (ganized)e(as)i(follo)n(ws.)g(W)-7 b(e)29 b(start)1892 1137 y(with)c(brief)g(descriptions)f(of)h(e)o(xisting)f(tools)h(for)g (aligning)f(pairs)1892 1237 y(of)c(lar)n(ge)f(genomic)g(DN)m(A)h (sequences.)d(After)j(introducing)e(some)1892 1336 y(basic)45 b(de\002nitions,)f(the)i(section)e(on)h(Algorithms)g(and)g(Data)1892 1436 y(Structures)d(outlines)f(the)h(three)g(phases)f(of)h(our)g(tool)g FE(MGA)p FF(.)1892 1535 y(The)21 b(ne)n(w)g(algorithm)g(for)h (\002nding)f FE(multiMEM)s FF(s)h(is)g(described)e(in)1892 1635 y(detail,)30 b(including)f(some)g(important)h(implementation)f (details.)1892 1734 y(Finally)-6 b(,)22 b(we)f(present)g(e)o (xperimental)e(results.)1892 1940 y FG(RELA)-8 b(TED)24 b(W)n(ORK)1892 2064 y FF(T)-7 b(o)29 b(the)g(best)f(of)h(our)f(kno)n (wledge,)f(there)h(is)h(no)g(other)f(softw)o(are)1892 2164 y(tool)f(that)h(can)f(align)g(more)g(than)g(tw)o(o)g(DN)m(A)h (sequences)d(of)j(the)1892 2263 y(size)c(of)h(entire)f(genomes)f (\(e.g.)h(of)g(bacteria)g(or)g(of)h(eukaryotes\).)1892 2363 y(F)o(or)f(this)g(reason,)f(we)h(must)g(restrict)h(our)e (discussion)g(of)h(related)1892 2463 y(w)o(ork)41 b(to)h(softw)o(are)f (tools)h(that)f(are)h(aimed)f(at)h(aligning)e FE(two)1892 2562 y FF(genomic)e(DN)m(A)i(sequences.)e(W)-7 b(e)40 b(will)h(brie\003y)f(describe)f(the)1892 2662 y(softw)o(are)30 b(tools)h FE(MUMmer)r FF(,)f FE(GLASS)q FF(,)h(and)f FE(W)-5 b(AB)n(A)p FF(.)31 b(The)g(well-)1892 2761 y(kno)n(wn)36 b(web-based)f(tool)i FE(PipMak)o(er)i FF(constructs)d(alignments)1892 2861 y(using)i FE(blastz)h FF(\(Miller,)h(2001\),)d(b)n(ut)i(there)g (is)g(no)g(description)1892 2960 y(of)c(ho)n(w)f(this)h(is)h(done.)e(F) o(or)h(this)g(reason,)f(we)h(do)f(not)h(further)1892 3060 y(discuss)g FE(PipMak)o(er)r FF(.)g(Recently)h(\(Buhler,)g(2001\)) f(described)g(a)1892 3159 y(no)o(v)o(el)25 b(approach)h(to)h(align)g (lar)n(ge)g(sequences,)e(b)n(ut)i(no)g(softw)o(are)1892 3259 y(tool)21 b(seems)g(to)h(be)f(a)n(v)n(ailable)f(incorporating)g (this)i(approach.)1892 3431 y Fv(MUMmer)1892 3556 y FF(As)i(already)e (mentioned,)g FE(MUMmer)j FF(is)f(an)f(anchor)n(-based)e(tool.)1892 3655 y(It)27 b(proceeds)e(in)i(the)f(follo)n(wing)g(three)g(phases:)g (\(1\))g(A)h(maximal)1892 3755 y(unique)22 b(match)g(\()p FE(MUM)s FF(\))i(decomposition)d(of)i(the)g(tw)o(o)g(genomes)1892 3854 y FD(S)1948 3868 y FC(1)2006 3854 y FF(and)d FD(S)2209 3868 y FC(2)2267 3854 y FF(is)h(computed.)e(A)i FE(MUM)j FF(is)d(a)g(sequence)e(that)i(occurs)1892 3954 y(e)o(xactly)27 b(once)h(in)h(genome)e FD(S)2823 3968 y FC(1)2889 3954 y FF(and)h(once)g(in)g(genome)f FD(S)3695 3968 y FC(2)3732 3954 y FF(,)i(and)1892 4053 y(is)i(not)f(contained)f(in)i(an)o(y)e (longer)h(such)f(sequence.)g(Using)h(the)1892 4153 y(suf)n(\002x)j (tree)h(of)g FD(S)2450 4167 y FC(1)2487 4153 y FB($)p FD(S)2588 4167 y FC(2)2625 4153 y FF(,)g FE(MUM)s FF(s)g(can)f(be)g (computed)f(in)i FD(O)s FB(\()p FD(n)p FB(\))1892 4253 y FF(time)e(and)e(space,)h(where)f FD(n)45 b FB(=)f FA(j)p FD(S)3024 4267 y FC(1)3061 4253 y FB($)p FD(S)3162 4267 y FC(2)3200 4253 y FA(j)32 b FF(and)f FB($)h FF(is)g(a)f(symbol)1892 4352 y(neither)25 b(occurring)g(in)h FD(S)2671 4366 y FC(1)2735 4352 y FF(nor)f(in)i FD(S)3028 4366 y FC(2)3065 4352 y FF(.)f(\(2\))21 b(The)h(matches)j(found)1892 4452 y(in)36 b(the)g FE(MUM)j FF(decomposition)34 b(are)i(sorted,)g(and)f (the)h(longest)1892 4551 y(possible)20 b(set)h(of)f FE(MUM)s FF(s)h(that)g(occur)f(in)g(the)h(same)f(order)g(in)h(both)1892 4651 y(genomes)31 b(is)i(e)o(xtracted,)f(yielding)g(the)g(anchors.)f (This)j(can)e(be)1892 4750 y(done)18 b(using)h(the)h(algorithm)f(of)h (\(Jacobson)d(&)j(V)-11 b(o,)19 b(1992\))g(to)h(\002nd)1892 4850 y(the)28 b(hea)n(viest)f(increasing)g(subsequence)e(\(HIS\))k(of)f (a)g(sequence)1892 4949 y(of)20 b(weighted)g(inte)o(gers.)g(This)h (phase)e(tak)o(es)h FD(O)s FB(\()p FD(m)e FA(\001)f FB(log)g FD(m)p FB(\))k FF(time)1892 5049 y(in)f(the)g(w)o(orst)g(case,)f(where) g FD(m)h FF(is)h(the)f(number)e(of)i FE(MUM)s FF(s.)g(Note,)1892 5148 y(ho)n(we)n(v)o(er)m(,)31 b(that)k FE(MUMmer)g FF(actually)e(uses) h(a)g(simpler)h FD(O)s FB(\()p FD(m)3837 5115 y FC(2)3874 5148 y FB(\))1892 5248 y FF(time)19 b(dynamic)d(programming)h (algorithm.)g(\(3\))22 b(The)f(gaps)c(in)i(the)1892 5348 y(anchor)33 b(alignment)g(that)h(ha)n(v)o(e)f(length)h(less)g(than)g (or)g(equal)f(to)1892 5447 y(a)g(gi)n(v)o(en)f(limit)i(\(5,000)e(bp.)g (is)i(the)f(def)o(ault)f(in)i FE(MUMmer)r FF(\))e(are)p Black -275 5630 V -275 5729 a Fu(2)p Black eop %%Page: 3 3 3 2 bop Black -275 -76 4185 4 v Black -275 166 a FF(closed)31 b(with)h(a)f(standard)g(dynamic)f(programming)f(algorithm)-275 266 y(\(Needleman)23 b(&)h(W)l(unsch,)f(1970\).)g(F)o(or)i(one)e(gap)g (consisting)h(of)-275 366 y(tw)o(o)d(sequences)e(of)h(length)h FD(r)i FF(and)d FD(r)839 333 y Fw(0)862 366 y FF(,)h(this)g(tak)o(es)g FD(O)s FB(\()p FD(r)g FA(\001)d FD(r)1508 333 y Fw(0)1531 366 y FB(\))j FF(time)-275 465 y(and)33 b FD(O)s FB(\(min)n(\()p FD(r)m(;)15 b(r)300 432 y Fw(0)324 465 y FB(\)\))35 b FF(space.)d(Gaps)h(that)g(are)g(longer)g(than)g(the)-275 565 y(limit)22 b(remain)f(unaligned.)-203 664 y(The)29 b(restriction)h(of)f(using)f(only)h FE(MUM)s FF(s)g(as)h(anchors)d (seems)-275 764 y(unnecessary)-6 b(,)20 b(and)h(is)i(not)f (justi\002ed.)h(Exact)f(matches)f(occurring)-275 864 y(more)38 b(than)g(once)f(in)i(a)f(genome)f(may)h(also)g(be)g (meaningful.)-275 963 y(Furthermore,)32 b(the)h(co)o(v)o(erage)e(of)j (the)f(sequences)e(increases)h(if)-275 1063 y(other)18 b(matches)h(are)f(tak)o(en)h(into)g(account.)e(Moreo)o(v)o(er)m(,)g (the)i(use)g(of)-275 1163 y(the)24 b(HIS)h(algorithm)e(of)h(\(Jacobson) e(&)j(V)-11 b(o,)23 b(1992\))g(for)h(chaining)-275 1262 y(the)29 b FE(MUM)s FF(s)g(is)g(not)g(adequate.)e(This)i(is)g(because)e (the)i(resulting)-275 1362 y(chain)g(of)g FE(MUM)s FF(s)h(may)f (contain)f(o)o(v)o(erlapping)f FE(MUM)s FF(s,)i(which)-275 1462 y(in)39 b(turn)f(may)g(lead)h(to)g(inconsistencies)d(\(i.e.)j(it)g (may)g(not)f(be)-275 1561 y(possible)c(to)h(\002nd)g(an)g(alignment)e (that)j(is)f(consistent)f(with)h(all)-275 1661 y(selected)29 b FE(MUM)s FF(s\).)g FE(MUMmer)h FF(tak)o(es)f(an)g(ad)h(hoc)e (approach)g(to)-275 1760 y(handle)22 b(this:)j(It)f(simply)f(remo)o(v)o (es)f(the)i(o)o(v)o(erlapping)c(parts)k(from)-275 1860 y(the)d FE(MUM)s FF(s,)g(see)g(Figure)h(1.)-275 2035 y Fv(GLASS)-275 2159 y FF(The)16 b(acron)o(ym)f FE(GLASS)i FF(stands)f(for)h FE(GL)p FF(obal)f FE(A)p FF(lignment)g FE(S)q FF(y)p FE(S)q FF(tem)-275 2259 y(\(Batzoglu)41 b FE(et)g(al.)p FF(,)h(2000\).)e(It)i(has)f(been)g(de)n(v)o(eloped)d (for)k(the)-275 2358 y(preprocessing)23 b(step)j(of)f(the)h(gene)f (prediction)f(tool)i FE(R)m(OSETT)l(A)p FF(.)-275 2458 y FE(GLASS)21 b FF(is)g(based)e(on)g(a)i(model)e(of)h(eukaryotic)f(DN)m (A)h(sequences)-275 2558 y(containing)49 b(long,)g(weakly)h(conserv)o (ed)e(introns)i(and)f(short,)-275 2657 y(strongly)23 b(conserv)o(ed)e(e)o(xons.)i(Thus,)g(the)h(model)f(is)h(not)g(suitable) -275 2757 y(for)d(prokaryotes.)-203 2857 y FE(GLASS)47 b FF(also)f(f)o(alls)h(into)f(the)h(cate)o(gory)d(of)i(anchor)n(-based) -275 2956 y(alignment)35 b(tools.)h(It)h(consists)e(of)h(\002)n(v)o(e)g (steps)g(\(1\)\226\(5\),)f(which)-275 3056 y(deli)n(v)o(er)i(a)h (partial)f(alignment)g(of)h(the)g(tw)o(o)g(input)f(sequences,)-275 3155 y(possibly)20 b(lea)n(ving)h(some)g(re)o(gions)f(unaligned.)-203 3255 y(\(1\))46 b(All)g(pairs)f(of)g(e)o(xact)g(matching)f FD(k)s FF(-mers)i(\(i.e.)f(strings)-275 3355 y(of)35 b(length)g FD(k)s FF(\))h(in)f(the)g(tw)o(o)h(input)f(sequences)e FD(S)1273 3369 y FC(1)1346 3355 y FF(and)h FD(S)1563 3369 y FC(2)1636 3355 y FF(are)-275 3454 y(searched)e(for)-5 b(.)34 b(Initially)-6 b(,)35 b FD(k)53 b FB(=)c(20)p FF(.)36 b(\(2\))e(F)o(or)g(a)g(gi)n(v)o(en)f(pair)h(of)-275 3554 y(matching)28 b FD(k)s FF(-mers)h FB(\()p FD(w)457 3568 y FC(1)495 3554 y FD(;)15 b(w)600 3568 y FC(2)638 3554 y FB(\))p FF(,)29 b(its)h(score)f FD(s)39 b FB(=)h FD(s)1286 3568 y Ft(l)1338 3554 y FB(+)25 b FD(s)1477 3568 y Ft(r)1543 3554 y FF(is)30 b(de-)-275 3654 y(termined)e(as)h (follo)n(ws:)f(A)h(dynamic)f(programming)e(algorithm)-275 3753 y(is)h(applied)f(to)i(the)f(12)f(nucleotides)g(to)h(the)g(left)g (of)g FD(w)1400 3767 y FC(1)1465 3753 y FF(and)f FD(w)1683 3767 y FC(2)1721 3753 y FF(,)-275 3853 y(yielding)e(score)h FD(s)289 3867 y Ft(l)314 3853 y FF(,)g(and)g(to)g(the)h(right)f(of)g FD(w)1092 3867 y FC(1)1155 3853 y FF(and)g FD(w)1372 3867 y FC(2)1409 3853 y FF(,)h(yielding)-275 3953 y(score)42 b FD(s)-5 3967 y Ft(r)31 3953 y FF(.)h(\(3\))g(The)g(highest)f(scoring) g(sequence)f(of)i FD(k)s FF(-mers)-275 4052 y(that)33 b(occur)f(in)i(the)f(same)g(order)f(in)h(both)g(DN)m(A)g(sequences)e (is)-275 4152 y(computed)26 b(by)i(a)g(dynamic)f(programming)f (algorithm.)h(\(4\))h(All)-275 4251 y FD(k)s FF(-mer)23 b(matches)f(in)h(the)g(resulting)g(sequence)e(whose)h(score)g FD(s)h FF(is)-275 4351 y(belo)n(w)c(a)h(gi)n(v)o(en)f(threshold)f(are)i (remo)o(v)o(ed.)e(Furthermore,)h(incon-)-275 4451 y(sistent)40 b(o)o(v)o(erlapping)d FD(k)s FF(-mers)k(are)f(also)f(remo)o(v)o(ed;)g FB(\()p FD(w)1527 4465 y FC(1)1564 4451 y FD(;)15 b(w)1669 4465 y FC(2)1707 4451 y FB(\))-275 4550 y FF(and)20 b FB(\()p FD(w)-26 4517 y Fw(0)-28 4573 y FC(1)9 4550 y FD(;)15 b(w)116 4517 y Fw(0)114 4573 y FC(2)152 4550 y FB(\))21 b FF(are)g(inconsistent,)e(if)i(the)g(o)o(v)o(erlap)d(of)j FD(w)1435 4564 y FC(1)1493 4550 y FF(and)f FD(w)1707 4517 y Fw(0)1705 4573 y FC(1)-275 4650 y FF(dif)n(fers)e(from)h(the)g (o)o(v)o(erlap)e(of)h FD(w)718 4664 y FC(2)775 4650 y FF(and)g FD(w)987 4617 y Fw(0)985 4672 y FC(2)1022 4650 y FF(.)h(\(5\))g(The)g(resulting)f FD(k)s FF(-)-275 4750 y(mers)g(serv)o(e)f(as)h(anchors)f(in)h(the)g(alignment)f(of)h FD(S)1220 4764 y FC(1)1276 4750 y FF(and)f FD(S)1476 4764 y FC(2)1513 4750 y FF(.)h(Steps)-275 4849 y(\(1\)\226\(5\))28 b(are)g(recursi)n(v)o(ely)e(applied)i(to)g(the)g(gaps)g(\(all)h (unaligned)-275 4949 y(re)o(gions)k(between)g(the)i(anchors\))e(with)i (decreasing)d(v)n(alues)i(of)-275 5049 y FD(k)s FF(,)25 b(namely)f FB(15)p FD(;)15 b FB(12)p FD(;)g FB(9)p FD(;)g FB(8)p FD(;)g FB(7)p FD(;)g FB(6)p FD(;)g FB(5)q FF(.)31 b(Finally)-6 b(,)26 b(all)f(remaining)f(gaps)-275 5148 y(are)d(aligned)g(by)g(standard)f(dynamic)g(programming.)-203 5248 y(A)k(major)f(dra)o(wback)e(of)i FE(GLASS)h FF(is)g(the)f(huge)f (space)g(require-)-275 5347 y(ment.)k(F)o(or)g(e)o(xample,)f(an)g (alignment)h(of)g(tw)o(o)h(DN)m(A)f(sequences)-275 5447 y(of)19 b(human)f(and)g(mouse)g(\(length)g(222,930)f(bp.)i(and)f (227,538)f(bp.,)1892 166 y(see)28 b(the)g(\002rst)i(sequence)c(set)j (in)g(Experiments\))e(is)i(produced)d(in)1892 267 y(about)h(14)i (minutes)f(using)f(1.14)h(gigabytes)f(of)h(main)h(memory)-6 b(.)1892 368 y(It)34 b(tak)o(es)f(38)g(minutes)g(to)g(align)h(a)f (similar)h(pair)f(of)h(sequences)1892 468 y(of)25 b(twice)h(the)f (length,)g(using)g(2.05)f(gigabytes.)f(Furthermore,)i(it)1892 569 y(seems)c(that)h FE(GLASS)g FF(does)f(not)h(tak)o(e)f(adv)n(antage) f(of)h(long)h(identi-)1892 670 y(cal)f(re)o(gions)e(in)i(sequences.)d (F)o(or)j(e)o(xample,)e(to)i(deli)n(v)o(er)e(an)i(align-)1892 771 y(ment)30 b(of)g(the)g(initial)i(200,000)c(bp.)h(of)i(tw)o(o)f (strains)h(of)f(E.)h(coli,)1892 871 y FE(GLASS)c FF(requires)e(more)g (than)h(25)f(hours)g(of)h(computation)e(time)1892 972 y(\(we)d(stopped)f(the)i(job)f(after)g(25)g(hours\).)1892 1153 y Fv(W)-7 b(AB)n(A)1892 1279 y FF(The)53 b(acron)o(ym)e FE(W)-5 b(AB)n(A)54 b FF(stands)e(for)h FE(W)6 b FF(obble)52 b FE(A)p FF(w)o(are)i FE(B)p FF(ulk)1892 1380 y FE(A)p FF(ligner)24 b(\(K)n(ent)g(&)h(Zahler,)f(2000\).)f(The)h(k)o(e)o(y)g (feature)g(of)g FE(W)-5 b(AB)n(A)1892 1480 y FF(is)41 b(that)f(w)o(obble)g(bases)f(are)h(treated)g(dif)n(ferently)g(from)g (other)1892 1581 y(bases.)34 b(The)h(third)g(base)f(in)h(a)h(codon)d (is)j(called)e FE(wobble)g(base)1892 1682 y FF(because)19 b(mutations)h(in)h(this)g(base)f(are)g(often)h(silent)g(in)g(the)f (sense)1892 1783 y(that)40 b(the)o(y)f(do)h(not)g(change)e(the)i (corresponding)e(amino)h(acid)1892 1883 y(\(due)32 b(to)g(the)g (redundanc)o(y)e(of)i(the)g(genetic)g(code\).)f FE(W)-5 b(AB)n(A)33 b FF(has)1892 1984 y(been)k(de)n(v)o(eloped)e (speci\002cally)i(for)h(separately)e(aligning)h(229)1892 2085 y(dif)n(ferent)29 b(sequences)e(from)i FE(C.)h(brig)o(gsae)e FF(\(8)h(me)o(gabases)e(total)1892 2186 y(length,)h(34,722)f(bp.)h(a)n (v)o(erage)f(length\))h(against)g(97)g(me)o(gabases)1892 2286 y(of)21 b(the)h FE(C.)f(ele)m(gans)f FF(genome.)1964 2387 y FE(W)-5 b(AB)n(A)22 b FF(can)f(be)h(di)n(vided)e(into)i(three)g (phases.)e(\(1\))i(The)g(smaller)1892 2488 y(of)28 b(the)g(tw)o(o)g (input)g(sequences)e(is)j(brok)o(en)e(into)h(short,)f(o)o(v)o(erlap-) 1892 2589 y(ping)j(sequence)f(fragments.)h(Then)h(homologies)f(between) g(the)1892 2689 y(short)19 b(sequence)e(fragments)i(and)f(the)i(other)e (input)i(sequence)d(are)1892 2790 y(searched)32 b(for)-5 b(.)34 b(\(2\))f(Homologous)f(re)o(gions)h(are)g(aligned)g(in)h(an)1892 2891 y(e)o(xtended)22 b(windo)n(w)h(using)h(a)h(pairwise)f(hidden)f (Mark)o(o)o(v)g(model)1892 2992 y(\(Durbin)j FE(et)i(al.)p FF(,)f(1998\).)f(\(3\))h(If)g(an)o(y)f(tw)o(o)i(of)f(these)g(local)g (align-)1892 3092 y(ments)j(o)o(v)o(erlap)e(by)i(at)h(least)f(15)g(bp.) g(and)f(are)h(identical)g(in)h(the)1892 3193 y(o)o(v)o(erlapping)26 b(re)o(gion,)h(then)h(the)o(y)g(are)g(mer)n(ged)g(into)h(one)e(lar)n (ger)1892 3294 y(alignment.)1964 3395 y(The)34 b(homology)f(search)g (in)i(the)f(\002rst)i(phase)d(is)i(carried)f(out)1892 3495 y(in)46 b(gapped)f FE(BLAST)7 b FF(-lik)o(e)47 b(f)o(ashion)f (\(Altschul)g FE(et)h(al.)p FF(,)f(1997\))1892 3596 y(with)51 b(one)f(modi\002cation.)g(In)h FE(W)-5 b(AB)n(A)p FF(,)52 b FE(high)e(scoring)g(pair)o(s)1892 3697 y FF(are)c(not)h(required)e (to)i(match)f(e)o(xactly)f(b)n(ut)i(may)f(contain)g(a)1892 3798 y(mismatch)31 b(e)n(v)o(ery)e(three)i(bases.)g(This)h(is)f (justi\002ed)h(by)f(the)g(f)o(act)1892 3898 y(that)h(homologous)d(re)o (gions)i(in)h(tw)o(o)g(related)g(DN)m(A)g(sequences)1892 3999 y(are)17 b(most)g(lik)o(ely)h(protein)f(coding)f(re)o(gions.)g(In) h(these,)g(most)g(point)1892 4100 y(mutations)j(occur)h(in)g(the)h (third)f(base)g(of)g(a)h(codon.)1964 4200 y(The)d(running)e(time)i(of)g FE(W)-5 b(AB)n(A)19 b FF(for)g(aligning)f(the)h(8)f(me)o(gabases)1892 4301 y(of)31 b FE(C.)g(brig)o(gsae)f FF(and)g(the)i(97)e(me)o(gabases)f (of)i FE(C.)g(ele)m(gans)f FF(w)o(as)1892 4402 y(about)47 b(12)g(days)g(on)h(a)f(Pentium)h(III)h(450)e(MHz)h(computer)1892 4503 y(\(20)43 b(hours)g(+)h(11)f(days)g(+)i(15)e(minutes)g(for)h(the)f (respecti)n(v)o(e)1892 4603 y(phases\).)27 b(This)h(renders)g(the)g (approach)e(impractical)i(for)g(lar)n(ger)1892 4704 y(genomes.)1892 4918 y FG(B)m(ASIC)e(DEFINITIONS)1892 5044 y FF(W)-7 b(e)47 b(inde)o(x)e(the)i(characters)e(of)i(a)g(sequence)e(from)h FB(0)p FF(.)h(That)1892 5145 y(is,)57 b(a)g(sequence)d FD(S)62 b FF(of)57 b(length)f FD(n)g FF(is)i(written)f(as)f FD(S)99 b FB(=)1892 5246 y FD(S)5 b FB([0])p FD(S)g FB([1])15 b FD(:)g(:)g(:)j(S)5 b FB([)p FD(n)16 b FA(\000)g FB(1])26 b(=)f FD(S)5 b FB([0)15 b FD(:)g(:)g(:)i(n)f FA(\000)f FB(1])p FF(.)22 b(A)e FE(pr)m(e\002x)g FF(of)g FD(S)26 b FF(is)21 b(a)1892 5346 y(sequence)e FD(S)5 b FB([0])15 b FD(:)g(:)g(:)i(S)5 b FB([)p FD(i)p FB(])22 b FF(for)f(some)f FD(i)26 b FA(2)f FB([0)p FD(;)15 b(n)k FA(\000)f FB(1])p FF(.)k(A)g FE(suf)n(\002x)f FF(of)1892 5447 y FD(S)k FF(is)20 b(a)g(sequence)e FD(S)5 b FB([)p FD(j)g FB(])15 b FD(:)g(:)g(:)j(S)5 b FB([)p FD(n)14 b FA(\000)g FB(1])21 b FF(for)f(some)f FD(j)31 b FA(2)25 b FB([0)p FD(;)15 b(n)f FA(\000)g FB(1])p FF(.)p Black -275 5630 V 3868 5729 a Fu(3)p Black eop %%Page: 4 4 4 3 bop Black -275 -76 4185 4 v Black -275 175 a FF(Consider)38 b(a)h(set)g FA(f)p FD(G)410 189 y FC(0)447 175 y FD(;)15 b(:)g(:)g(:)i(;)e(G)721 189 y Ft(k)q Fw(\000)p FC(1)847 175 y FA(g)39 b FF(of)g FD(k)63 b FA(\025)58 b FB(2)40 b FF(sequences,)-275 275 y(the)30 b(genomes.)e(A)j FE(multiple)f(e)n (xact)g(matc)o(h)g FF(is)g(a)h FB(\()p FD(k)f FB(+)d(1\))p FF(-tuple)-275 374 y FB(\()p FD(l)r(;)15 b(p)-125 388 y FC(0)-87 374 y FD(;)g(p)-1 388 y FC(1)36 374 y FD(;)g(:)g(:)g(:)i(;)e (p)284 388 y Ft(k)q Fw(\000)p FC(1)410 374 y FB(\))26 b FF(such)e(that)i FD(l)34 b(>)f FB(0)p FF(,)26 b FD(p)1117 388 y Ft(q)1186 374 y FA(2)32 b FB([0)p FD(;)15 b FA(j)p FD(G)1486 388 y Ft(q)1524 374 y FA(j)23 b(\000)g FD(l)r FB(])p FF(,)-275 474 y(and)c FD(G)-57 488 y Ft(q)-21 474 y FB([)p FD(p)50 488 y Ft(q)102 474 y FD(:)c(:)g(:)h(p)269 488 y Ft(q)318 474 y FB(+)d FD(l)i FA(\000)e FB(1])25 b(=)g FD(G)791 488 y Ft(q)823 471 y Fs(0)850 474 y FB([)p FD(p)921 488 y Ft(q)953 471 y Fs(0)995 474 y FD(:)15 b(:)g(:)h(p)1162 488 y Ft(q)1194 471 y Fs(0)1234 474 y FB(+)d FD(l)i FA(\000)e FB(1])20 b FF(for)f(all)-275 574 y FD(q)s(;)c(q)-147 541 y Fw(0)-96 574 y FA(2)28 b FB([0)p FD(;)15 b(k)26 b FA(\000)21 b FB(1])p FF(.)j(A)f(multiple)g (e)o(xact)f(match)g(is)h FE(left)h(maximal)-275 674 y FF(if)29 b(for)f(at)g(least)g(one)f(pair)h FB(\()p FD(q)s(;)15 b(q)697 641 y Fw(0)721 674 y FB(\))38 b FA(2)g FB([0)p FD(;)15 b(k)29 b FA(\000)c FB(1])h FA(\002)f FB([0)p FD(;)15 b(k)30 b FA(\000)25 b FB(1])p FF(,)-275 773 y(we)32 b(either)h(ha)n(v)o(e)e FD(p)331 787 y Ft(q)414 773 y FB(=)46 b(0)p FF(,)33 b(or)g FD(p)783 787 y Ft(q)815 770 y Fs(0)888 773 y FB(=)46 b(0)p FF(,)33 b(or)g FD(G)1283 787 y Ft(q)1319 773 y FB([)p FD(p)1390 787 y Ft(q)1455 773 y FA(\000)28 b FB(1])48 b FA(6)p FB(=)-275 873 y FD(G)-203 887 y Ft(q)-171 870 y Fs(0)-144 873 y FB([)p FD(p)-73 887 y Ft(q)-41 870 y Fs(0)10 873 y FA(\000)24 b FB(1])p FF(.)j(A)g(multiple)f(e)o(xact)g(match)g(is)h FE(right)f(maximal)g FF(if)-275 973 y(for)34 b(at)g(least)h(one)e(pair) h FB(\()p FD(q)s(;)15 b(q)646 940 y Fw(0)670 973 y FB(\))49 b FA(2)h FB([0)p FD(;)15 b(k)34 b FA(\000)c FB(1])g FA(\002)g FB([0)p FD(;)15 b(k)34 b FA(\000)c FB(1])p FF(,)-275 1073 y(we)39 b(either)g(ha)n(v)o(e)f FD(p)351 1087 y Ft(q)422 1073 y FB(+)33 b FD(l)62 b FB(=)d FA(j)p FD(G)842 1087 y Ft(q)878 1073 y FA(j)p FF(,)40 b(or)f FD(p)1123 1087 y Ft(q)1155 1070 y Fs(0)1216 1073 y FB(+)34 b FD(l)61 b FB(=)e FA(j)p FD(G)1636 1087 y Ft(q)1668 1070 y Fs(0)1695 1073 y FA(j)p FF(,)-275 1172 y(or)33 b FD(G)-97 1186 y Ft(q)-61 1172 y FB([)p FD(p)10 1186 y Ft(q)76 1172 y FB(+)28 b FD(l)r FB(])48 b FA(6)p FB(=)f FD(G)467 1186 y Ft(q)499 1169 y Fs(0)525 1172 y FB([)p FD(p)596 1186 y Ft(q)628 1169 y Fs(0)685 1172 y FB(+)28 b FD(l)r FB(])p FF(.)33 b(A)h(multiple)e(e)o(xact)g(match)-275 1272 y(is)40 b FE(maximal)f FF(if)h(it)g(is)g(left)g(maximal)f(and)f(right)i (maximal.)e(A)-275 1372 y(maximal)30 b(multiple)g(e)o(xact)g(match)g (is)h(also)f(called)g FE(multiMEM)s FF(.)-275 1471 y(F)o(or)e FD(k)42 b FB(=)c(2)p FF(,)29 b(we)g(use)f(the)g(notion)f FE(MEM)s FF(.)i(Roughly)e(speaking,)-275 1571 y(a)k FE(multiMEM)k FF(is)d(a)f(sequence)f(of)h(length)f FD(l)k FF(that)d(occurs)g(in)g (all)-275 1671 y(sequences)20 b FD(G)173 1685 y FC(0)210 1671 y FD(;)15 b(:)g(:)g(:)i(;)e(G)484 1685 y Ft(k)q Fw(\000)p FC(1)633 1671 y FF(\(at)23 b(positions)f FD(p)1132 1685 y FC(0)1169 1671 y FD(;)15 b(:)g(:)g(:)h(;)f(p)1416 1685 y Ft(k)q Fw(\000)p FC(1)1542 1671 y FF(\),)23 b(and)-275 1771 y(cannot)34 b(simultaneously)g(be)h(e)o(xtended)f(to)i(the)f(left) h(or)g(to)g(the)-275 1870 y(right)21 b(in)h(e)n(v)o(ery)e(sequence.) -275 2079 y FG(ALGORITHMS)25 b(AND)g(D)l(A)-8 b(T)g(A)25 b(STR)n(UCTURES)-275 2203 y Fr(Computing)d Fv(multiMEM)s Fr(s)-275 2328 y FF(Let)f FB($)-93 2342 y FC(0)-55 2328 y FD(;)15 b(:)g(:)g(:)h(;)f FB($)191 2342 y Ft(k)q Fw(\000)p FC(1)339 2328 y FF(be)20 b(pairwise)h(dif)n(ferent)e(symbols)h(not)g (occur)n(-)-275 2427 y(ring)c(in)g(an)o(y)f FD(G)179 2441 y Ft(q)232 2427 y FF(and)h(let)g FD(S)31 b FB(=)24 b FD(G)732 2441 y FC(0)769 2427 y FB($)814 2441 y FC(0)852 2427 y FD(G)924 2441 y FC(1)961 2427 y FB($)1006 2441 y FC(1)1058 2427 y FD(:)15 b(:)g(:)i(G)1252 2441 y Ft(k)q Fw(\000)p FC(2)1377 2427 y FB($)1422 2441 y Ft(k)q Fw(\000)p FC(2)1548 2427 y FD(G)1620 2441 y Ft(k)q Fw(\000)p FC(1)1746 2427 y FF(.)-275 2527 y(That)30 b(is,)g FB($)70 2541 y FC(0)108 2527 y FD(;)15 b(:)g(:)g(:)h(;)f FB($)354 2541 y Ft(k)q Fw(\000)p FC(2)511 2527 y FF(are)30 b(used)f(to)h (separate)f(the)h(sequences)-275 2627 y(in)k(the)g(concatenation)e FD(S)5 b FF(.)34 b FB($)649 2641 y Ft(k)q Fw(\000)p FC(1)810 2627 y FF(will)h(be)f(used)f(as)h(a)g(sentinel)-275 2727 y(attached)20 b(to)i(the)f(end)g(of)g FD(S)5 b FF(,)22 b(see)f(belo)n(w)-6 b(.)-203 2835 y(Let)22 b FD(n)j FB(=)g FA(j)p FD(S)5 b FA(j)26 b FB(=)f FD(k)e FA(\000)c FB(1)i(+)660 2767 y Fq(P)756 2788 y Ft(k)q Fw(\000)p FC(1)756 2862 y Ft(q)r FC(=0)897 2835 y FA(j)p FD(G)994 2849 y Ft(q)1031 2835 y FA(j)p FF(.)g(F)o(or)h(an)o(y)e FD(i)26 b FA(2)f FB([0)p FD(;)15 b(n)p FB(])p FF(,)-275 2950 y(let)35 b FD(S)-97 2964 y Ft(i)-18 2950 y FB(=)51 b FD(S)5 b FB([)p FD(i)15 b(:)g(:)g(:)h(n)31 b FA(\000)f FB(1]$)659 2964 y Ft(k)q Fw(\000)p FC(1)821 2950 y FF(denote)k(the)g FD(i)p FF(th)i(non-empty)-275 3050 y(suf)n(\002x)21 b(of)h FD(S)5 b FB($)144 3064 y Ft(k)q Fw(\000)p FC(1)270 3050 y FF(.)21 b(Hence)g FD(S)614 3064 y Ft(n)684 3050 y FB(=)k($)825 3064 y Ft(k)q Fw(\000)p FC(1)951 3050 y FF(.)-203 3149 y(De\002ne)d FD(t)85 3163 y FC(0)148 3149 y FB(=)j(0)e FF(and)e FD(t)493 3163 y Ft(q)556 3149 y FB(=)k FD(t)685 3163 y Ft(q)r Fw(\000)p FC(1)827 3149 y FB(+)20 b FA(j)p FD(G)1015 3163 y Ft(q)r Fw(\000)p FC(1)1137 3149 y FA(j)h FB(+)f(1)i FF(for)g(an)o(y)f FD(q)29 b FA(2)-275 3249 y FB([1)p FD(;)15 b(k)s FB(])p FF(.)22 b FD(t)-13 3263 y Ft(q)43 3249 y FF(is)f(the)f(start)g(position)g(of)g FD(G)886 3263 y Ft(q)942 3249 y FF(in)g FD(S)26 b FF(for)20 b FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)j FA(\000)d FB(1])p FF(.)-275 3349 y(Let)27 b FD(i)36 b FA(2)f FB([0)p FD(;)15 b(n)25 b FA(\000)f FB(1])k FF(such)d(that)i FD(S)5 b FB([)p FD(i)p FB(])47 b FD(=)-55 b FA(2)35 b(f)p FB($)1123 3363 y FC(0)1161 3349 y FD(;)15 b(:)g(:)g(:)h(;)f FB($)1407 3363 y Ft(k)q Fw(\000)p FC(2)1534 3349 y FA(g)p FF(.)27 b(W)-7 b(e)-275 3449 y(de\002ne)21 b(tw)o(o)g(functions)g FD(\033)k FF(and)20 b FD(\032)i FF(as)g(follo)n(ws:)p Black -275 3616 a FA(\017)p Black 79 w FD(\033)s FB(\()p FD(i)p FB(\))27 b(=)e FD(q)g FF(if)d(and)e(only)h(if)h FD(t)701 3630 y Ft(q)763 3616 y FA(\024)j FD(i)g(<)g(t)1044 3630 y Ft(q)r FC(+1)1185 3616 y FA(\000)20 b FB(1)p Black -275 3784 a FA(\017)p Black 79 w FD(\032)p FB(\()p FD(i)p FB(\))27 b(=)e FD(i)20 b FA(\000)g FD(t)295 3798 y Ft(\033)r FC(\()p Ft(i)p FC(\))-275 3951 y FF(That)43 b(is,)g(position)e FD(i)j FF(in)f FD(S)48 b FF(is)43 b(identi\002ed)f(with)h(the)f(relati) n(v)o(e)-275 4051 y(position)21 b FD(\032)p FB(\()p FD(i)p FB(\))h FF(in)g(sequence)d FD(G)701 4065 y Ft(\033)r FC(\()p Ft(i)p FC(\))821 4051 y FF(.)-203 4151 y(W)-7 b(e)43 b(consider)f(trees)g(whose)g(edges)g(are)g(labeled)g(by)h(non-) -275 4250 y(empty)e(sequences.)e(F)o(or)j(each)f(character)g FD(a)p FF(,)h(e)n(v)o(ery)e(node)h FD(\013)-275 4350 y FF(in)35 b(these)f(trees)g(has)g(at)h(most)g(one)e FD(a)p FF(-edge)h FD(\013)1213 4323 y Ft(av)p 1206 4332 110 4 v 1232 4330 a Fp(-)1331 4350 y FD(\014)40 b FF(for)34 b(some)-275 4450 y(sequence)27 b FD(v)34 b FF(and)29 b(some)g(node)f FD(\014)5 b FF(.)30 b(Consider)f(a)h(tree)f FD(T)43 b FF(and)29 b(let)-275 4550 y FD(\013)f FF(be)f(a)g(node)f(in)h FD(T)13 b FF(.)27 b(W)-7 b(e)28 b(denote)e FD(\013)i FF(by)p 997 4499 68 4 v 27 w FD(w)i FF(if)d(and)g(only)f(if)i FD(w)i FF(is)-275 4649 y(the)25 b(concatenation)f(of)h(the)h(edge)e (labels)i(on)f(the)g(path)g(from)h(the)-275 4749 y Fo(ro)s(ot)21 b FF(of)f FD(T)33 b FF(to)20 b FD(\013)p FF(.)h(A)f(sequence)e FD(w)23 b FE(occur)o(s)18 b FF(in)j FD(T)33 b FF(if)20 b(and)g(only)f(if)i FD(T)-275 4849 y FF(contains)j(a)i(node)p 301 4799 115 4 v 24 w FD(w)r(v)t FF(,)f(for)h(some)e(sequence)g FD(v)s FF(.)i(The)f FE(suf)n(\002x)g(tr)m(ee)-275 4948 y FF(for)34 b FD(S)5 b FF(,)35 b(denoted)e(by)h Fo(ST)-8 b FF(,)35 b(is)g(the)f(tree)h FD(T)47 b FF(with)35 b(the)g(follo)n (wing)-275 5048 y(properties:)f(\(1\))h(each)g(node)f(is)h(either)g (the)g Fo(ro)s(ot)q FF(,)g(a)g(leaf)g(or)h(a)-275 5148 y(branching)23 b(node,)h(and)h(\(2\))h(a)f(sequence)e FD(w)29 b FF(occurs)24 b(in)i FD(T)38 b FF(if)26 b(and)-275 5248 y(only)21 b(if)h FD(w)i FF(is)e(a)g(substring)e(of)h FD(S)5 b FB($)748 5262 y Ft(k)q Fw(\000)p FC(1)875 5248 y FF(.)-203 5347 y(There)53 b(is)h(a)g(one-to-one)e(correspondence)d (between)k(the)-275 5447 y(lea)n(v)o(es)37 b(of)h(the)g(suf)n(\002x)g (tree)g(and)f(the)h(non-empty)f(suf)n(\002x)o(es)g(of)1892 187 y FD(S)5 b FB($)1998 201 y Ft(k)q Fw(\000)p FC(1)2124 187 y FF(:)31 b(Leaf)p 2369 114 84 4 v 30 w FD(S)2425 201 y Ft(i)2483 187 y FF(corresponds)c(to)j(suf)n(\002x)g FD(S)3315 201 y Ft(i)3373 187 y FF(and)f(vice)h(v)o(ersa.)1892 296 y(F)o(or)20 b(this)g(reason,)e(we)i(sometimes)f(denote)p 3215 223 V 19 w FD(S)3271 310 y Ft(i)3318 296 y FF(by)h FD(`)p FB(\()p FD(i)p FB(\))p FF(.)g(It)h(is)f(well)1892 397 y(kno)n(wn)k(that)i(a)f(suf)n(\002x)g(tree)h(can)f(be)g (constructed)f(in)i(linear)f(time)1892 497 y(and)20 b(linear)i(space)e (\(W)-7 b(einer,)21 b(1973;)g(McCreight,)g(1976\).)1964 597 y(F)o(or)27 b(an)o(y)e(node)p 2458 547 53 4 v 25 w FD(u)i FF(of)g Fo(ST)19 b FF(\(including)25 b(the)h(lea)n(v)o(es\),)f (let)i FA(P)p 3756 577 44 3 v 14 x Ft(u)3827 597 y FF(be)1892 697 y(the)22 b(set)h(of)g(positions)f FD(i)h FF(such)f(that)h FD(u)g FF(is)g(a)g(pre\002x)f(of)h FD(S)3562 711 y Ft(i)3590 697 y FF(.)f(In)h(other)1892 798 y(w)o(ords,)f FA(P)p 2212 778 V 13 x Ft(u)2280 798 y FF(is)h(the)h(set)f(of)g(positions)g (in)g FD(S)29 b FF(where)23 b(the)g(sequence)1892 898 y FD(u)32 b FF(starts.)g(W)-7 b(e)33 b(di)n(vide)e FA(P)p 2672 878 V 14 x Ft(u)2748 898 y FF(into)h(disjoint)g(and)f(possibly)g (empty)1892 998 y(position)26 b(sets)h(according)e(to)i FD(\033)s FF(:)h(F)o(or)f(an)o(y)f FD(q)39 b FA(2)d FB([0)p FD(;)15 b(k)29 b FA(\000)24 b FB(1])p FF(,)k(we)1892 1099 y(de\002ne)18 b FA(P)p 2187 1078 V 13 x Ft(u)2230 1099 y FB(\()p FD(q)s FB(\))26 b(=)f FA(f)p FD(i)h FA(2)f(P)p 2717 1078 V 13 x Ft(u)2786 1099 y FA(j)g FD(\033)s FB(\()p FD(i)p FB(\))i(=)e FD(q)s FA(g)p FF(,)19 b(i.e.)f FA(P)p 3433 1078 V 13 x Ft(u)3477 1099 y FB(\()p FD(q)s FB(\))h FF(is)g(the)f(set)1892 1199 y(of)27 b(position)f FD(i)h FF(in)g FD(S)32 b FF(where)27 b FD(u)g FF(starts)g(and)f FD(i)i FF(occurs)d(in)i(genome)1892 1299 y FD(G)1964 1313 y Ft(q)2000 1299 y FF(.)1964 1400 y(W)-7 b(e)45 b(no)n(w)e(describe)g(an)h(algorithm)g(to)g(compute)f(all)h FE(mul-)1892 1500 y(tiMEM)s FF(s,)54 b(using)e(the)i(suf)n(\002x)f (tree)g(for)g FD(S)5 b FF(.)54 b(Our)f(algorithm)1892 1600 y(computes)39 b(position)h(sets)g(by)h(processing)d(the)j(edges)e (of)i(the)1892 1701 y(suf)n(\002x)46 b(tree)g(in)g(a)h(bottom-up)d (strate)o(gy)-6 b(.)46 b(That)g(is,)h(the)f(edge)1892 1801 y(leading)25 b(to)i(node)p 2466 1751 53 4 v 25 w FD(u)g FF(is)g(processed)d(only)i(after)h(all)g(edges)e(in)i(the)1892 1901 y(subtree)20 b(belo)n(w)p 2398 1851 V 21 w FD(u)i FF(ha)n(v)o(e)e(been)h(processed.)1964 2001 y(If)p 2054 1951 V 32 w FD(u)32 b FF(is)h(a)e(leaf,)h(say)f FD(`)p FB(\()p FD(i)p FB(\))p FF(,)i(then)e(compute)g FA(P)3404 2015 y Ft(`)p FC(\()p Ft(i)p FC(\))3511 2001 y FB(\()p FD(q)s FB(\))46 b(=)f FA(f)p FD(i)p FA(g)1892 2102 y FF(if)29 b FD(\033)s FB(\()p FD(i)p FB(\))41 b(=)f FD(q)s FF(,)29 b(and)f FA(P)2595 2116 y Ft(`)p FC(\()p Ft(i)p FC(\))2702 2102 y FB(\()p FD(q)s FB(\))41 b(=)e FA(;)30 b FF(otherwise.)e(No)n(w)g(suppose)p 1892 2152 V 1892 2202 a FD(u)35 b FF(is)h(a)g(branching)d(node.)h(The)h(edges)f (outgoing)g(from)p 3715 2152 V 35 w FD(u)i FF(are)1892 2302 y(processed)e(from)i(left)g(to)g(right.)g(Consider)f(an)h(edge)p 3628 2252 V 35 w FD(u)p 3695 2284 110 4 v 3722 2282 a Fp(-)p 3820 2252 68 4 v 3820 2302 a FD(w)r FF(.)1892 2403 y(Due)18 b(to)h(the)g(bottom-up)e(strate)o(gy)-6 b(,)19 b FA(P)p 3025 2382 54 3 v 13 x Ft(w)3078 2403 y FB(\()p FD(q)s FB(\))h FF(is)g(already)d(computed)1892 2503 y(for)g(an)o(y)e FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)5 b FA(\000)r FB(1])p FF(.)19 b(Ho)n(we)n(v)o(er)m(,)14 b(only)i(a)h(subset)f(of)h FA(P)p 3618 2483 44 3 v 14 x Ft(u)3661 2503 y FB(\()p FD(q)s FB(\))h FF(has)1892 2603 y(been)23 b(computed)f(since)i(only)g(the)g(\002rst,)h(say)f FD(j)5 b FF(,)25 b(edges)e(outgoing)1892 2704 y(from)p 2080 2654 53 4 v 18 w FD(u)c FF(ha)n(v)o(e)f(been)g(processed.)e(W)-7 b(e)19 b(denote)f(the)h(corresponding)1892 2812 y(subset)54 b(of)i FA(P)p 2357 2792 44 3 v 13 x Ft(u)2401 2812 y FB(\()p FD(q)s FB(\))g FF(by)f FA(P)2784 2769 y Ft(j)p 2777 2801 V 2777 2835 a(u)2820 2812 y FB(\()p FD(q)s FB(\))p FF(.)p 3013 2762 53 4 v 57 w FD(u)p 3080 2794 110 4 v 3107 2792 a Fp(-)p 3205 2762 68 4 v 3205 2812 a FD(w)j FF(is)e(processed)d(in)1892 2912 y(the)43 b(follo)n(wing)g(w)o (ay:)g(At)h(\002rst)h FE(multiMEM)s FF(s)f(are)f(output)g(by)1892 3020 y(combining)29 b FA(P)2366 2978 y Ft(j)p 2359 3010 44 3 v 2359 3043 a(u)2433 3020 y FF(with)i FA(P)p 2682 3000 54 3 v 14 x Ft(w)2736 3020 y FF(.)g(In)g(particular)m(,)e(all)i FB(\()p FD(k)24 b FB(+)c(1\))p FF(-tuples)1892 3121 y FB(\()p FD(l)r(;)15 b(p)2042 3135 y FC(0)2079 3121 y FD(;)g(p)2165 3135 y FC(1)2203 3121 y FD(;)g(:)g(:)g(:)h(;)f(p)2450 3135 y Ft(k)q Fw(\000)p FC(1)2576 3121 y FB(\))39 b FF(satisfying)e (the)g(follo)n(wing)g(conditions)1892 3221 y(are)21 b(enumerated:)p Black 1942 3395 a FB(\(1\))p Black 42 w FD(l)28 b FB(=)c FA(j)p FD(u)p FA(j)p Black 1942 3547 a FB(\(2\))p Black 42 w FD(p)2145 3561 y Ft(q)2207 3547 y FA(2)h(P)2363 3504 y Ft(j)p 2356 3536 44 3 v 2356 3570 a(u)2399 3547 y FB(\()p FD(q)s FB(\))c FA([)f(P)p 2678 3526 54 3 v 13 x Ft(w)2732 3547 y FB(\()p FD(q)s FB(\))i FF(for)g(an)o(y)e FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)25 b FA(\000)20 b FB(1])p Black 1942 3701 a(\(3\))p Black 42 w FD(p)2145 3715 y Ft(q)2207 3701 y FA(2)25 b(P)2363 3658 y Ft(j)p 2356 3690 44 3 v 2356 3724 a(u)2399 3701 y FB(\()p FD(q)s FB(\))e FF(for)e(at)h(least)g(one)e FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)25 b FA(\000)20 b FB(1])p FF(.)p Black 1942 3841 a FB(\(4\))p Black 42 w FD(p)2145 3855 y Ft(q)2207 3841 y FA(2)25 b(P)p 2356 3821 54 3 v 14 x Ft(w)2410 3841 y FB(\()p FD(q)s FB(\))d FF(for)g(at)f(least)h(one)f FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)24 b FA(\000)c FB(1])p FF(.)1892 4015 y(By)77 b(de\002nition)f(of)h FA(P)p 2695 3995 44 3 v 13 x Ft(u)2738 4015 y FF(,)g FD(u)g FF(occurs)f(at)h(the)f (positions)1892 4115 y FD(p)1938 4129 y FC(0)1975 4115 y FD(;)15 b(p)2061 4129 y FC(1)2098 4115 y FD(;)g(:)g(:)g(:)i(;)e(p) 2346 4129 y Ft(k)q Fw(\000)p FC(1)2495 4115 y FF(in)23 b FD(S)5 b FF(.)23 b(Moreo)o(v)o(er)m(,)d(for)j(each)f FD(q)31 b FA(2)c FB([0)p FD(;)15 b(k)26 b FA(\000)21 b FB(1])p FF(,)1892 4215 y FD(\032)p FB(\()p FD(p)2020 4229 y Ft(q)2057 4215 y FB(\))71 b FF(is)f(a)h(relati)n(v)o(e)f (position)f(of)i FD(u)f FF(in)h FD(G)3558 4229 y Ft(q)3594 4215 y FF(.)g(Hence)1892 4316 y FB(\()p FD(l)r(;)15 b(\032)p FB(\()p FD(p)2124 4330 y FC(0)2162 4316 y FB(\))p FD(;)g(\032)p FB(\()p FD(p)2365 4330 y FC(1)2403 4316 y FB(\))p FD(;)g(:)g(:)g(:)i(;) e(\032)p FB(\()p FD(p)2768 4330 y Ft(k)q Fw(\000)p FC(1)2894 4316 y FB(\)\))94 b FF(is)g(a)f(multiple)h(e)o(xact)1892 4416 y(match.)30 b(Conditions)h(\(3\))g(and)g(\(4\))h(guarantee)d(that) j(not)f(all)h(po-)1892 4524 y(sitions)27 b(are)f(e)o(xclusi)n(v)o(ely)f (tak)o(en)h(from)g FA(P)3181 4482 y Ft(j)p 3174 4513 V 3174 4547 a(u)3218 4524 y FB(\()p FD(q)s FB(\))i FF(or)e(from)h FA(P)p 3719 4504 54 3 v 14 x Ft(w)3773 4524 y FB(\()p FD(q)s FB(\))p FF(.)1892 4625 y(Hence)e(at)h(least)g(tw)o(o)g(of)g(the) f(positions)g(in)h FA(f)p FD(p)3329 4639 y FC(0)3367 4625 y FD(;)15 b(p)3453 4639 y FC(1)3490 4625 y FD(;)g(:)g(:)g(:)i(;)e (p)3738 4639 y Ft(k)q Fw(\000)p FC(1)3864 4625 y FA(g)1892 4725 y FF(are)51 b(tak)o(en)f(from)h(dif)n(ferent)f(subtrees)h(of)p 3321 4675 53 4 v 51 w FD(u)p FF(.)g(This)g(implies)1892 4825 y(right)63 b(maximality)-6 b(.)62 b(T)-7 b(o)63 b(guarantee)f(left)h(maximality)-6 b(,)63 b(we)1892 4925 y(reject)48 b FB(\()p FD(l)r(;)15 b(\032)p FB(\()p FD(p)2366 4939 y FC(0)2404 4925 y FB(\))p FD(;)g(\032)p FB(\()p FD(p)2607 4939 y FC(1)2645 4925 y FB(\))p FD(;)g(:)g(:)g(:)i(;)e(\032)p FB(\()p FD(p)3010 4939 y Ft(k)q Fw(\000)p FC(1)3137 4925 y FB(\)\))p FF(,)49 b(if)g FD(p)3426 4939 y FC(0)3541 4925 y FD(>)77 b FB(0)49 b FF(and)1892 5026 y FD(S)5 b FB([)p FD(p)2024 5040 y FC(0)2081 5026 y FA(\000)20 b FB(1])26 b(=)f FD(S)5 b FB([)p FD(p)2496 5040 y FC(1)2553 5026 y FA(\000)20 b FB(1])26 b(=)f FA(\001)15 b(\001)g(\001)27 b FB(=)e FD(S)5 b FB([)p FD(p)3196 5040 y Ft(k)q Fw(\000)p FC(1)3342 5026 y FA(\000)19 b FB(1])p FF(.)1964 5126 y(As)k(soon)f(as)h(for)g(the)g(current)f(edge)p 3081 5076 V 22 w FD(u)p 3148 5108 110 4 v 3175 5106 a Fp(-)p 3273 5076 68 4 v 3273 5126 a FD(w)k FF(the)d FE(multiMEM)s FF(s)1892 5234 y(are)34 b(enumerated,)e(our)j(algorithm)e(adds)h FA(P)p 3279 5214 54 3 v 14 x Ft(w)3333 5234 y FB(\()p FD(q)s FB(\))i FF(to)e FA(P)3655 5192 y Ft(j)p 3648 5224 44 3 v 3648 5257 a(u)3692 5234 y FB(\()p FD(q)s FB(\))h FF(to)1892 5347 y(obtain)18 b(position)g(sets)h FA(P)2649 5304 y Ft(j)s FC(+1)p 2642 5336 V 2642 5370 a Ft(u)2769 5347 y FB(\()p FD(q)s FB(\))h FF(for)f(all)g FD(q)28 b FA(2)d FB([0)p FD(;)15 b(k)e FA(\000)e FB(1])p FF(.)21 b(That)e(is,)1892 5447 y(the)28 b(position)f(sets)h(are)g(inherited)f (from)h(node)p 3364 5397 68 4 v 27 w FD(w)j FF(to)d(the)g(parent)p Black -275 5630 4185 4 v -275 5729 a Fu(4)p Black eop %%Page: 5 5 5 4 bop Black -275 -76 4185 4 v Black -275 175 a FF(node)p -72 125 53 4 v 32 w FD(u)p FF(.)33 b(Finally)-6 b(,)34 b FA(P)p 395 155 44 3 v 14 x Ft(u)439 175 y FB(\()p FD(q)s FB(\))g FF(is)g(obtained)d(as)j(soon)e(as)h(all)h(edges)-275 276 y(outgoing)20 b(from)p 248 226 53 4 v 21 w FD(u)i FF(are)f(processed.)-203 376 y(T)-7 b(o)28 b(analyze)e(the)h(ef)n (\002cienc)o(y)f(of)i(our)f(algorithm)f(we)i(describe)-275 477 y(ho)n(w)18 b(to)h(implement)f(position)g(sets)h(and)f(ho)n(w)g(to) h(accomplish)e(the)-275 578 y(bottom-up)j(tra)n(v)o(ersal.)-275 748 y FE(Implementation)49 b(of)i(P)-7 b(osition)51 b(Sets.)87 b FF(Our)50 b(algorithm)h(per)n(-)-275 849 y(forms)39 b(tw)o(o)g(operations)e(on)i(position)f(sets:)h(Enumeration)f(of)-275 950 y(multiple)f(e)o(xact)f(matches)g(by)g(combining)f(position)h(sets) h(and)-275 1050 y(adding)22 b(up)g(position)h(sets.)g(A)g(position)f (set)i FA(P)p 1151 1030 44 3 v 14 x Ft(u)1194 1050 y FB(\()p FD(q)s FB(\))g FF(is)g(the)f(union)-275 1151 y(of)37 b(position)f(sets)g(from)h(the)f(subtrees)g(belo)n(w)p 1241 1101 53 4 v 36 w FD(u)p FF(.)h(Recall)g(that)-275 1252 y(we)d(considered)e(processing)g(an)h(edge)p 995 1202 V 33 w FD(u)p 1062 1234 110 4 v 1089 1232 a Fp(-)p 1187 1202 68 4 v 1187 1252 a FD(w)s FF(.)h(If)g(the)g(edges)-275 1352 y(to)j(the)g(children)g(of)p 408 1302 V 37 w FD(w)j FF(ha)n(v)o(e)c(been)g(processed,)f(the)i(position)-275 1453 y(sets)27 b(of)g(the)f(children)g(are)h(obsolete.)e(Hence)h(it)i (is)f(not)g(required)-275 1554 y(to)h(cop)o(y)f(position)g(sets.)g(At)i (an)o(y)d(time)i(of)g(the)g(algorithm,)f(each)-275 1654 y(position)g(is)i(included)d(in)i(e)o(xactly)f(one)g(position)h(set.)g (F)o(or)g(each)-275 1755 y(node)f(we)i(store)f FD(k)33 b FF(references)27 b(to)i FD(k)j FF(possibly)27 b(empty)h(position)-275 1856 y(sets.)34 b(Hence,)g(the)g(space)g(requirement)f(for)h(the)h (position)f(sets)-275 1957 y(is)e FD(O)s FB(\()p FD(k)s(n)p FB(\))p FF(.)g(The)f(union)f(operation)g(for)i(the)f(position)g(sets)g (can)-275 2057 y(be)h(implemented)f(in)h(constant)g(time,)g(if)h(we)f (use)g(link)o(ed)g(lists.)-275 2158 y(F)o(or)39 b(each)f(node,)f(we)i (ha)n(v)o(e)f FD(O)s FB(\()p FD(k)s FB(\))i FF(union)e(operations.)f (Since)-275 2259 y(there)23 b(are)g FD(O)s FB(\()p FD(n)p FB(\))h FF(edges)e(in)i(the)f(suf)n(\002x)g(tree,)g(the)h(union)e(and)g (add)-275 2359 y(operations)e(thus)h(require)g FD(O)s FB(\()p FD(k)s(n)p FB(\))h FF(time.)-203 2460 y(Each)d(combination)f (of)h(position)g(sets)h(requires)f(to)g(enumerate)-275 2561 y(the)i(Cartesian)g(product)-275 2735 y Ft(k)q Fw(\000)p FC(1)-261 2820 y Fn(\002)-273 2872 y Ft(q)r FC(=0)-138 2813 y FB(\()p FA(P)p -40 2793 44 3 v 14 x Ft(u)4 2813 y FB(\()p FD(q)s FB(\))f FA([)g(P)p 282 2793 54 3 v 14 x Ft(w)336 2813 y FB(\()p FD(q)s FB(\)\))q FA(n)531 2685 y Fq(\022)q(\022)665 2735 y Ft(k)q Fw(\000)p FC(1)680 2820 y Fn(\002)668 2872 y Ft(q)r FC(=0)787 2813 y FA(P)p 850 2793 44 3 v 14 x Ft(u)894 2813 y FB(\()p FD(q)s FB(\))1008 2685 y Fq(\023)1095 2813 y FA([)1176 2685 y Fq(\022)1243 2735 y Ft(k)q Fw(\000)p FC(1)1258 2820 y Fn(\002)1246 2872 y Ft(q)r FC(=0)1365 2813 y FA(P)p 1428 2793 54 3 v 14 x Ft(w)1482 2813 y FB(\()p FD(q)s FB(\))1596 2685 y Fq(\023\023)1730 2813 y FD(:)-275 3061 y FF(This)j(can)f(be)g(done)f (in)i(time)f(proportional)f(to)i(its)g(size.)f(W)m(ith)h(the)-275 3162 y(enumeration)17 b(of)j(the)f(Cartesian)g(product)f(we)i(maintain) e(the)i(size)-275 3263 y(of)43 b(the)g(set)g FD(C)196 3277 y FC(left)320 3263 y FB(=)25 b FA(f)p FD(S)5 b FB([)p FD(p)593 3277 y Ft(q)650 3263 y FA(\000)20 b FB(1])26 b FA(j)g FD(q)i FA(2)d FB([0)p FD(;)15 b(k)24 b FA(\000)c FB(1])p FD(;)15 b(p)1471 3277 y Ft(q)1534 3263 y FD(>)25 b FB(0)p FA(g)p FF(.)-275 3363 y(This)52 b(tak)o(es)f(constant)f(time)i (per)f(enumeration)e(step.)i(No)n(w)-275 3464 y(an)61 b(enumerated)f(right)i(maximal)f(multiple)h(e)o(xact)e(match)-275 3565 y FB(\()p FD(l)r(;)15 b(\032)p FB(\()p FD(p)-43 3579 y FC(0)-5 3565 y FB(\))p FD(;)g(\032)p FB(\()p FD(p)198 3579 y FC(1)236 3565 y FB(\))p FD(;)g(:)g(:)g(:)i(;)e(\032)p FB(\()p FD(p)601 3579 y Ft(k)q Fw(\000)p FC(1)727 3565 y FB(\)\))58 b FF(is)f(left)h(maximal)e(if)h(and)-275 3666 y(only)28 b(if)h FD(p)37 3680 y FC(0)114 3666 y FB(=)39 b(0)30 b FF(or)e FA(j)p FD(C)490 3680 y FC(left)590 3666 y FA(j)39 b(\025)g FB(2)p FF(.)30 b(Thus)e(the)h(left)g (maximality)-275 3766 y(can)43 b(be)h(decided)f(in)h(constant)f(e)o (xtra)g(time.)i(Altogether)e(the)-275 3867 y(position)f(sets)g(are)g (maintained)f(and)h(repeats)g(are)g(output)g(in)-275 3968 y FD(O)s FB(\()p FD(k)s(n)21 b FB(+)g FD(r)s FB(\))i FF(time,)g(where)e FD(r)26 b FF(is)d(the)g(number)e(of)i(right)f (maximal)-275 4068 y(multiple)33 b(e)o(xact)f(matches.)g(This)i(time)f (bound)f(can)g(be)h(further)-275 4169 y(impro)o(v)o(ed)26 b(by)h(di)n(viding)g(each)g FA(P)p 768 4149 44 3 v 14 x Ft(u)812 4169 y FB(\()p FD(q)s FB(\))i FF(into)e(subsets)h(according) -275 4270 y(to)g(the)f(character)g(to)h(the)f(left)i(of)e(the)h (corresponding)d(position.)-275 4370 y(This)36 b(leads)f(to)h(an)f (algorithm)g(that)g(enumerates)f FE(multiMEM)s FF(s)-275 4471 y(directly)52 b(without)h(an)o(y)e(further)h(test)h(for)g(left)g (maximality)-6 b(,)-275 4572 y(using)36 b FD(O)s FB(\()p FA(j)p FB(\006)p FA(j)p FD(k)s(n)d FB(+)e FD(m)p FB(\))38 b FF(time)f(where)g FD(m)g FF(is)g(the)g(number)f(of)-275 4673 y FE(multiMEM)s FF(s)22 b(and)e FB(\006)i FF(is)g(the)f(alphabet.) -275 4843 y FE(Implementation)36 b(of)j(the)f(Bottom-Up)f(T)-5 b(r)o(aver)o(sal.)86 b FF(W)-7 b(e)39 b(ha)n(v)o(e)-275 4944 y(described)f(our)i(algorithm)g(based)f(on)h(suf)n(\002x)g(trees,) f(because)-275 5044 y(these)22 b(are)h(widely)g(kno)n(wn)e(in)i(the)g (bioinformatics)f(community)-6 b(.)-275 5145 y(Ho)n(we)n(v)o(er)m(,)49 b(we)i(actually)g(implemented)f(our)g(algorithm)h(on)-275 5246 y(\223virtual)32 b(suf)n(\002x)g(trees\224,)g(introduced)f(in)h (\(Kasai)g FE(et)h(al.)p FF(,)f(2001\).)-275 5346 y(This)25 b(ne)n(w)g(data)f(structure)h(consists)f(of)h(tw)o(o)g(tables)g Fo(suftab)f FF(and)-275 5447 y Fo(lcptab)o FF(,)c(which)e(allo)n(w)h (to)h(simulate)e(the)h(bottom-up)f(tra)n(v)o(ersal)h(of)1892 169 y(the)32 b(suf)n(\002x)f(tree)h(for)g FD(S)5 b FF(,)32 b(as)g(required)e(for)i(our)g(algorithm.)f(The)1892 269 y(tw)o(o)21 b(tables)h(are)f(de\002ned)f(as)i(follo)n(ws:)p Black 1892 438 a FA(\017)p Black 79 w Fo(suftab)41 b FF(is)h(a)f(table)g(of)h(length)e FD(n)35 b FB(+)g(1)43 b FF(inde)o(x)o(ed)c(from)i(0)2016 537 y(to)61 b FD(n)g FF(such)e(that)i FD(S)2729 551 y Fm(suftab)o FC([0])2962 537 y FD(;)15 b(S)3058 551 y Fm(suftab)o FC([1])3291 537 y FD(;)g(:)g(:)g(:)i(;)e(S)3549 551 y Fm(suftab)o FC([)p Ft(n)p FC(])3851 537 y FF(is)2016 637 y(the)58 b(sequence)d(of)j(suf)n(\002x)o(es)e(of)i FD(S)5 b FB($)3251 651 y Ft(k)q Fw(\000)p FC(1)3435 637 y FF(in)58 b(ascending)2016 737 y(le)o(xicographic)19 b(order)-5 b(.)p Black 1892 908 a FA(\017)p Black 79 w Fo(lcptab)23 b FF(is)g(a)g(table)g(of)g (length)f FD(n)h FF(inde)o(x)o(ed)d(from)j FB(1)h FF(to)f FD(n)f FF(such)2016 1008 y(that,)28 b(for)h(an)o(y)e FD(i)38 b FA(2)g FB([1)p FD(;)15 b(n)p FB(])p FF(,)29 b Fo(lcptab)p FB([)p FD(i)p FB(])g FF(is)g(the)f(length)g(of)g(the)2016 1108 y(longest)f(common)f(pre\002x)h(of)h(the)g(suf)n(\002x)o(es)e FD(S)3447 1122 y Fm(suftab)o FC([)p Ft(i)p Fw(\000)p FC(1])3783 1108 y FF(and)2016 1208 y FD(S)2072 1222 y Fm(suftab)o FC([)p Ft(i)p FC(])2296 1208 y FF(.)1892 1377 y(T)-7 b(able)55 b Fo(suftab)f FF(is)i(also)e(called)h(suf)n (\002x)g(array)f(\(Manber)g(&)1892 1477 y(Myers,)28 b(1993\).)f(The)h (simulation)g(algorithm)g(of)h(\(Kasai)f FE(et)h(al.)p FF(,)1892 1577 y(2001\))44 b(runs)h(in)h FD(O)s FB(\()p FD(n)p FB(\))g FF(time.)g(The)f(same)g(time)h(bound)e(can)1892 1676 y(be)32 b(achie)n(v)o(ed)f(for)i(a)g(bottom-up)f(tra)n(v)o(ersal)g (of)h(the)g(suf)n(\002x)g(tree.)1892 1776 y(More)25 b(importantly)-6 b(,)24 b(the)g(tw)o(o)h(tables)g(require)f(much)g(less)h(space)1892 1876 y(than)j(the)g(suf)n(\002x)h(tree.)f(T)-7 b(able)29 b Fo(suftab)f FF(can)g(be)g(implemented)f(in)1892 1976 y FB(4\()p FD(n)f FB(+)f(1\))k FF(bytes.)e(T)-7 b(able)28 b Fo(lcptab)g FF(only)g(requires)f FD(n)h FF(bytes,)f(due)1892 2076 y(to)37 b(the)g(f)o(act)g(that)g(the)f(v)n(alues)g(in)h(this)g (table)g(are)g(e)o(xpected)d(to)1892 2176 y(be)25 b(small.)h(T)-7 b(ables)25 b Fo(suftab)h FF(and)e Fo(lcptab)i FF(can)f(be)g (constructed)f(in)1892 2276 y FD(O)s FB(\()p FD(k)s(n)p FB(\))29 b FF(time)g(and)f(space)g(using)g(a)h(suf)n(\002x)f(tree,)h (see)f(\(Gus\002eld,)1892 2376 y(1997\).)1964 2475 y(Altogether)g(our)h (algorithm)f(runs)g(in)h FD(O)s FB(\()p FD(k)s(n)d FB(+)g FD(r)s FB(\))j FF(time)g(and)1892 2575 y FD(O)s FB(\()p FD(k)s(n)p FB(\))36 b FF(space,)f(where)g FD(r)j FF(is)f(the)e(number)g (of)g(right)h(maximal)1892 2675 y(multiple)17 b(e)o(xact)f(matches.)g (Note)h(that)h(for)f FD(k)29 b FB(=)c(2)p FF(,)17 b(our)g(algorithm) 1892 2775 y(is)30 b(v)o(ery)f(similar)h(to)g(the)f(algorithm)g(of)h (\(Gus\002eld,)f(1997,)g(page)1892 2875 y(147\))20 b(to)i(compute)e (maximal)h(repeated)f(pairs.)1892 3051 y Fr(Selecting)i(an)g(Optimal)h (Set)g(of)g Fv(multiMEM)s Fr(s)1892 3175 y FF(This)56 b(problem)f(is)h(an)g(instance)f(of)h(the)g(follo)n(wing)f(more)1892 3275 y(general)30 b(problem)g(from)i(computational)d(geometry)-6 b(.)30 b(Let)i(a)g FD(k)s FF(-)1892 3375 y(dimensional)25 b(Euclidean)g(space)h(with)g(rectangular)f(coordinate)1892 3475 y(system)j(be)g(gi)n(v)o(en.)f(W)-7 b(e)29 b(consider)f FD(k)s FF(-dimensional)f(rectangular)1892 3575 y(solids,)50 b(in)g(which)g(the)g(edges)f(of)h(the)h(solids)f(are)g(parallel)1892 3675 y(with)29 b(the)g(coordinates.)d(Each)j(such)f(rectangular)f (solid)i(can)f(be)1892 3775 y(characterized)19 b(by)i(a)h(point)f FD(p)26 b FB(=)f(\()p FD(p)2998 3789 y FC(1)3035 3775 y FD(;)15 b(:)g(:)g(:)i(;)e(p)3283 3789 y Ft(k)3324 3775 y FB(\))22 b FF(and)f(the)g(lengths)1892 3875 y FD(l)1919 3889 y FC(1)1956 3875 y FD(;)15 b(:)g(:)g(:)i(;)e(l)2185 3889 y Ft(k)2266 3875 y FF(of)39 b(its)h(edges.)e(\(In)i(the)f(plane,)f FD(p)60 b FB(=)f(\()p FD(p)3615 3889 y FC(1)3653 3875 y FD(;)15 b(p)3739 3889 y FC(2)3776 3875 y FB(\))40 b FF(is)1892 3974 y(the)d(lo)n(wer)n(-left)g(corner)g(of)g(a)g (rectangle,)f FD(l)3266 3988 y FC(1)3341 3974 y FF(is)i(the)f(length)g (of)1892 4074 y(the)43 b(edge)g(parallel)h(with)g(the)g FD(x)p FF(-coordinate,)e(and)h FD(l)3619 4088 y FC(2)3700 4074 y FF(is)i(the)1892 4174 y(length)21 b(of)h(the)g(edge)f(parallel)h (with)h(the)f FD(y)s FF(-coordinate.\))e(Thus,)i(a)1892 4274 y(rectangular)g(solid)j FD(r)-13 b(s)24 b FF(consists)g(of)g FB(2)p FD(k)k FF(components,)22 b(viz.)i FD(r)-13 b(s)31 b FB(=)1892 4374 y(\()p FD(p)1973 4388 y FC(1)2010 4374 y FD(;)15 b(:)g(:)g(:)i(;)e(p)2258 4388 y Ft(k)2299 4374 y FD(;)g(l)2366 4388 y FC(1)2403 4374 y FD(;)g(:)g(:)g(:)i(;)e(l)2632 4388 y Ft(k)2673 4374 y FB(\))p FF(.)30 b(Moreo)o(v)o(er)m(,)d(a)i (rectangular)f(solid)h FD(r)-13 b(s)1892 4474 y FF(has)17 b(an)h(associated)e(weight)i FD(w)r FB(\()p FD(r)-13 b(s)p FB(\))p FF(,)19 b(which,)e(for)h(e)o(xample,)f(could)1892 4574 y(be)k(the)g(v)n(olume)g(of)g FD(r)-13 b(s)p FF(.)1964 4674 y(F)o(or)22 b(tw)o(o)f(rectangular)f(solids)2314 4856 y FD(r)-13 b(s)45 b FB(=)21 b(\()p FD(p)2603 4870 y FC(1)2641 4856 y FD(;)15 b(:)g(:)g(:)h(;)f(p)2888 4870 y Ft(k)2929 4856 y FD(;)g(l)2996 4870 y FC(1)3034 4856 y FD(;)g(:)g(:)g(:)i(;)e(l)3263 4870 y Ft(k)3304 4856 y FB(\))22 b FF(and)2314 4956 y FD(r)-13 b(s)2385 4923 y Fw(0)2430 4956 y FB(=)21 b(\()p FD(p)2603 4923 y Fw(0)2603 4978 y FC(1)2641 4956 y FD(;)15 b(:)g(:)g(:)h(;)f(p)2888 4923 y Fw(0)2888 4978 y Ft(k)2929 4956 y FD(;)g(l)2998 4923 y Fw(0)2996 4978 y FC(1)3034 4956 y FD(;)g(:)g(:)g(:)i(;)e(l)3265 4923 y Fw(0)3263 4978 y Ft(k)3304 4956 y FB(\))1892 5147 y FF(we)32 b(de\002ne)f FD(r)-13 b(s)46 b FA(\036)f FD(r)-13 b(s)2575 5114 y Fw(0)2631 5147 y FF(if)32 b(and)f(only)h(if)g(for)g (all)h FD(i)46 b FA(2)f FB([1)p FD(;)15 b(k)s FB(])34 b FF(the)1892 5247 y(inequality)20 b FD(p)2308 5261 y Ft(i)2356 5247 y FB(+)g FD(l)2474 5261 y Ft(i)2527 5247 y FD(<)25 b(p)2669 5214 y Fw(0)2669 5270 y Ft(i)2718 5247 y FF(holds.)1964 5347 y(In)66 b(what)g(follo)n(ws,)f(let)i(a)f (set)g(of)g(rectangular)f(solids)1892 5447 y FA(f)p FD(r)-13 b(s)2008 5461 y FC(1)2045 5447 y FD(;)15 b(:)g(:)g(:)i(;)e(r)-13 b(s)2318 5461 y Ft(m)2382 5447 y FA(g)27 b FF(be)g(gi)n(v)o(en.)f(A)h (subset)f FD(C)43 b FB(=)36 b FA(f)p FD(r)-13 b(s)3470 5461 y Ft(i)3493 5469 y Fl(1)3530 5447 y FD(;)15 b(:)g(:)g(:)i(;)e(r) -13 b(s)3803 5461 y Ft(i)3826 5469 y Fk(q)3864 5447 y FA(g)p Black -275 5630 4185 4 v 3868 5729 a Fu(5)p Black eop %%Page: 6 6 6 5 bop Black -275 -76 4185 4 v Black Black Black Black -247 2068 a @beginspecial 0 @llx 0 @lly 523 @urx 523 @ury 2353 @rwi @setspecial %%BeginDocument: mwiisVShis.eps %!PS-Adobe-2.0 EPSF-2.0 %%Title: mwiisVShis.eps %%Creator: fig2dev Version 3.2 Patchlevel 1 %%CreationDate: Tue Jan 22 19:46:22 2002 %%For: mhoehl@teak (Michael Hoehl) %%Orientation: Portrait %%BoundingBox: 0 0 523 523 %%Pages: 0 %%BeginSetup %%EndSetup %%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 -36.0 576.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 %%EndProlog $F2psBegin 10 setmiterlimit n -1000 10600 m -1000 -1000 l 10312 -1000 l 10312 10600 l cp clip 0.06000 0.06000 sc % Polyline 7.500 slw gs clippath 870 1020 m 900 900 l 930 1020 l 930 885 l 870 885 l cp clip n 900 9300 m 900 900 l gs col0 s gr gr % arrowhead n 870 1020 m 900 900 l 930 1020 l 900 1020 l 870 1020 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 9180 9270 m 9300 9300 l 9180 9330 l 9315 9330 l 9315 9270 l cp clip n 900 9300 m 9300 9300 l gs col0 s gr gr % arrowhead n 9180 9270 m 9300 9300 l 9180 9330 l 9180 9300 l 9180 9270 l cp gs 0.00 setgray ef gr col0 s % Polyline n 1500 7800 m 2400 7800 l 2400 6900 l 1500 6900 l cp gs col0 s gr % Polyline n 1800 5100 m 3000 5100 l 3000 3900 l 1800 3900 l cp gs col0 s gr % Polyline n 3300 4800 m 4500 4800 l 4500 3600 l 3300 3600 l cp gs col0 s gr % Polyline [15 45] 45 sd n 1500 7800 m 1800 7800 l 1800 7500 l 1500 7500 l cp gs col0 s gr [] 0 sd % Polyline [15 45] 45 sd n 1800 5100 m 2100 5100 l 2100 4800 l 1800 4800 l cp gs col0 s gr [] 0 sd % Polyline [15 45] 45 sd gs clippath 3180 4770 m 3300 4800 l 3180 4830 l 3315 4830 l 3315 4770 l cp clip n 2100 4800 m 3300 4800 l gs col0 s gr gr [] 0 sd % arrowhead n 3180 4770 m 3300 4800 l 3180 4830 l 3180 4800 l 3180 4770 l cp gs 0.00 setgray ef gr col0 s % Polyline [60] 0 sd gs clippath 1757 5216 m 1800 5100 l 1817 5223 l 1831 5088 l 1772 5082 l cp clip n 1500 7800 m 1800 5100 l gs col0 s gr gr [] 0 sd % arrowhead n 1757 5216 m 1800 5100 l 1817 5223 l 1787 5219 l 1757 5216 l cp gs 0.00 setgray ef gr col0 s % Polyline [60] 0 sd gs clippath 3176 4794 m 3300 4800 l 3188 4853 l 3321 4826 l 3309 4768 l cp clip n 1800 5100 m 3300 4800 l gs col0 s gr gr [] 0 sd % arrowhead n 3176 4794 m 3300 4800 l 3188 4853 l 3182 4824 l 3176 4794 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 3225 4898 m 3300 4800 l 3280 4922 l 3333 4798 l 3278 4774 l cp clip n 2400 6900 m 3300 4800 l gs col0 s gr gr % arrowhead n 3225 4898 m 3300 4800 l 3280 4922 l 3253 4910 l 3225 4898 l cp gs 0.00 setgray ef gr col0 s % Polyline [15 45] 45 sd gs clippath 1770 5220 m 1800 5100 l 1830 5220 l 1830 5085 l 1770 5085 l cp clip n 1800 7500 m 1800 5100 l gs col0 s gr gr [] 0 sd % arrowhead n 1770 5220 m 1800 5100 l 1830 5220 l 1800 5220 l 1770 5220 l cp gs 0.00 setgray ef gr col0 s % Polyline n 6900 2700 m 7500 2700 l 7500 3300 l 6900 3300 l cp gs col0 s gr % Polyline n 9000 1800 m 8400 1800 l 8400 2400 l 9000 2400 l cp gs col0 s gr % Polyline gs clippath 6777 3285 m 6900 3300 l 6785 3345 l 6919 3328 l 6911 3268 l cp clip n 4500 3600 m 6900 3300 l gs col0 s gr gr % arrowhead n 6777 3285 m 6900 3300 l 6785 3345 l 6781 3315 l 6777 3285 l cp gs 0.00 setgray ef gr col0 s % Polyline gs clippath 8277 2409 m 8400 2400 l 8296 2466 l 8424 2424 l 8405 2367 l cp clip n 7500 2700 m 8400 2400 l gs col0 s gr gr % arrowhead n 8277 2409 m 8400 2400 l 8296 2466 l 8286 2438 l 8277 2409 l cp gs 0.00 setgray ef gr col0 s % Polyline n 6000 5400 m 7200 5400 l 7200 6600 l 6000 6600 l cp gs col0 s gr % Polyline n 3300 8700 m 3900 8700 l 3900 8100 l 3300 8100 l cp gs col0 s gr % Polyline n 5100 7500 m 5400 7500 l 5400 7800 l 5100 7800 l cp gs col0 s gr % Polyline [60] 0 sd gs clippath 6778 3318 m 6900 3300 l 6801 3374 l 6925 3322 l 6902 3267 l cp clip n 3300 4800 m 6900 3300 l gs col0 s gr gr [] 0 sd % arrowhead n 6778 3318 m 6900 3300 l 6801 3374 l 6789 3346 l 6778 3318 l cp gs 0.00 setgray ef gr col0 s % Polyline [60] 0 sd gs clippath 8282 2436 m 8400 2400 l 8313 2487 l 8428 2418 l 8397 2367 l cp clip n 6900 3300 m 8400 2400 l gs col0 s gr gr [] 0 sd % arrowhead n 8282 2436 m 8400 2400 l 8313 2487 l 8297 2462 l 8282 2436 l cp gs 0.00 setgray ef gr col0 s % Polyline [90 36 15 27 15 27 15 36 ] 0 sd gs clippath 4976 7800 m 5100 7800 l 4991 7858 l 5122 7825 l 5107 7767 l cp clip n 3900 8100 m 5100 7800 l gs col0 s gr gr [] 0 sd % arrowhead n 4976 7800 m 5100 7800 l 4991 7858 l 4984 7829 l 4976 7800 l cp gs 0.00 setgray ef gr col0 s % Polyline [90 36 15 27 15 27 15 36 ] 0 sd gs clippath 5908 6683 m 6000 6600 l 5958 6716 l 6033 6604 l 5983 6571 l cp clip n 5400 7500 m 6000 6600 l gs col0 s gr gr [] 0 sd % arrowhead n 5908 6683 m 6000 6600 l 5958 6716 l 5933 6700 l 5908 6683 l cp gs 0.00 setgray ef gr col0 s % Polyline [90 36 15 27 15 27 15 36 ] 0 sd gs clippath 8328 2500 m 8400 2400 l 8383 2523 l 8433 2397 l 8378 2375 l cp clip n 7200 5400 m 8400 2400 l gs col0 s gr gr [] 0 sd % arrowhead n 8328 2500 m 8400 2400 l 8383 2523 l 8355 2511 l 8328 2500 l cp gs 0.00 setgray ef gr col0 s % Polyline n 6600 1200 m 5700 1200 l 5700 2100 l 6600 2100 l cp gs col0 s gr /Times-Roman ff 180.00 scf sf 600 1200 m gs 1 -1 sc (Y) col0 sh gr /Times-Roman ff 180.00 scf sf 9000 9600 m gs 1 -1 sc (X) col0 sh gr $F2psEnd rs %%EndDocument @endspecial -275 2392 a Fj(Fig)o(.)17 b(1.)h Fi(A)g(maximum)h(weight)f (chain)h(\(dra)o(wn)f(by)h(solid)f(arro)n(ws\))g(of)g Fh(MEM)s Fi(s)-275 2483 y(\(represented)29 b(by)g(squares\))g(as)f (deli)n(v)o(ered)h(by)g(the)g(algorithm)f(applied)h(in)-275 2574 y(phase)g(\(2\))e(of)h Fh(MGA)p Fi(.)f(The)h(rightmost)g(chain)h (\(dra)o(wn)f(by)g(dashed-dotted)-275 2666 y(arro)n(ws\))38 b(is)h(suboptimal.)g(Not)f(all)g(chains)h(are)g(sho)n(wn.)g(Suppose)g (that)-275 2757 y(all)28 b Fh(MEM)s Fi(s)g(are)g Fh(MUM)s Fi(s.)g(A)g(HIS-chain)g(of)h(these)f Fh(MUM)s Fi(s)h(\(depicted)g(by) -275 2848 y(dashed)20 b(arro)n(ws\),)f(as)f(computed)j(by)e Fh(MUMmer)r Fi(,)g(consists)g(of)g(\002)n(v)o(e)g(squares.)-275 2940 y(The)34 b(HIS-chain)g(includes)h(a)f(square)h(that)f(o)o(v)o (erlaps)h(with)f(the)g(squares)-275 3031 y(belo)n(w)22 b(it)g(and)g(to)g(its)f(right-hand)i(side.)f(T)-6 b(o)22 b(guarantee)h(that)e(the)h(alignment)-275 3122 y(is)k(consistent,)h Fh(MUMmer)i Fi(remo)o(v)o(es)f(the)f(o)o(v)o(erlaps,)g(retaining)g (shortened)-275 3214 y(matches)39 b(\(dra)o(wn)g(as)g(dotted)g (squares\).)g(As)g(a)f(result,)g(the)h(HIS-chain)-275 3305 y(containing)20 b(shortened)g(matches)g(is)e(suboptimal.)p Black -275 3621 a FF(of)37 b FA(f)p FD(r)-13 b(s)-49 3635 y FC(1)-12 3621 y FD(;)15 b(:)g(:)g(:)i(;)e(r)-13 b(s)261 3635 y Ft(m)325 3621 y FA(g)37 b FF(satisfying)g FD(r)-13 b(s)855 3635 y Ft(i)878 3643 y Fl(1)940 3621 y FA(\036)25 b FD(r)-13 b(s)1107 3635 y Ft(i)1130 3643 y Fl(2)1192 3621 y FA(\036)25 b(\001)15 b(\001)g(\001)26 b(\036)f FD(r)-13 b(s)1586 3635 y Ft(i)1609 3643 y Fk(q)1684 3621 y FF(is)-275 3732 y(called)29 b(a)h FE(c)o(hain)p FF(.)f(The)h(weight)f(of)h(chain)f FD(C)37 b FF(is)1223 3664 y Fq(P)1318 3684 y Ft(q)1318 3759 y(j)s FC(=1)1453 3732 y FD(w)r FB(\()p FD(r)-13 b(s)1626 3746 y Ft(i)1649 3754 y Fk(j)1685 3732 y FB(\))p FF(.)-275 3833 y(W)-7 b(e)70 b(w)o(ant)f(to)h(\002nd)f(a)g(chain)g(with)h(maximum)e(weight) -275 3934 y(among)47 b(all)h(chains.)f(T)-7 b(o)49 b(do)e(so,)h(we)g (transform)g(the)g(prob-)-275 4035 y(lem)d(into)g(a)f(graph)g (theoretical)g(problem.)g(W)-7 b(e)45 b(construct)f(a)-275 4135 y(weighted)49 b(directed)f(graph)h FD(G)79 b FB(=)h(\()p FD(V)5 b(;)15 b(E)5 b FB(\))51 b FF(with)g(v)o(ertices)-275 4236 y FD(V)56 b FB(=)36 b FA(f)p FD(star)s(t;)15 b(r)-13 b(s)298 4250 y FC(1)335 4236 y FD(;)15 b(:)g(:)g(:)i(;)e(r)-13 b(s)608 4250 y Ft(m)671 4236 y FD(;)15 b(stop)p FA(g)p FF(.)27 b(The)g(set)h(of)f(edges)e FD(E)33 b FF(is)-275 4337 y(characterized)27 b(as)j(follo)n(ws:)g(There)f(is)h(an)f(edge)g FD(star)s(t)39 b FA(!)i FD(r)-13 b(s)1707 4351 y Ft(j)-275 4438 y FF(with)32 b(weight)g FB(0)g FF(for)g FD(j)51 b FA(2)45 b FB([1)p FD(;)15 b(m)p FB(])p FF(,)33 b(an)f(edge)f FD(r)-13 b(s)1240 4452 y Ft(i)1313 4438 y FA(!)45 b FD(r)-13 b(s)1520 4452 y Ft(j)1587 4438 y FF(with)-275 4539 y(weight)23 b FD(w)r FB(\()p FD(r)-13 b(s)159 4553 y Ft(i)188 4539 y FB(\))24 b FF(if)g FD(r)-13 b(s)395 4553 y Ft(i)453 4539 y FA(\036)29 b FD(r)-13 b(s)624 4553 y Ft(j)659 4539 y FF(,)24 b(and)f(an)g(edge)f FD(r)-13 b(s)1220 4553 y Ft(i)1278 4539 y FA(!)29 b FD(stop)23 b FF(with)-275 4640 y(weight)39 b FD(w)r FB(\()p FD(r)-13 b(s)175 4654 y Ft(i)203 4640 y FB(\))40 b FF(for)f FD(i)60 b FA(2)f FB([1)p FD(;)15 b(m)p FB(])p FF(.)41 b(Constructing)d(the)h(graph)-275 4741 y(tak)o(es)30 b FD(O)s FB(\()p FD(k)h FA(\001)c FD(m)251 4708 y FC(2)289 4741 y FB(\))k FF(time.)g(Note)f(that)h(the)f (graph)g(is)h(ac)o(yclic.)e(A)-275 4842 y(maximum)23 b(weight)h(chain)g(of)g(rectangular)f(solids)h(corresponds)-275 4943 y(to)40 b(a)g(path)f(with)i(maximum)e(weight)g(from)h(v)o(erte)o (x)e FD(star)s(t)i FF(to)-275 5044 y(v)o(erte)o(x)34 b FD(stop)h FF(in)g(the)h(graph.)e(Because)g(the)h(graph)f(is)i(ac)o (yclic,)-275 5144 y(such)44 b(a)h(path)g(can)f(be)h(computed)e(in)i FB(\002\()p FA(j)p FD(V)21 b FA(j)39 b FB(+)f FA(j)p FD(E)5 b FA(j)p FB(\))46 b FF(time)-275 5245 y(\(La)o(wler,)25 b(1976;)e(Cormen)h FE(et)i(al.)p FF(,)e(1990,)g(Section)g(25.4\).)g (All)i(in)-275 5346 y(all,)35 b(a)h(chain)e(with)i(maximum)e(weight)h (can)f(be)h(computed)f(in)-275 5447 y FD(O)s FB(\()p FD(k)24 b FA(\001)c FD(m)28 5414 y FC(2)65 5447 y FB(\))i FF(time)g(because)e FA(j)p FD(V)g FA(j)h FB(+)f FA(j)p FD(E)5 b FA(j)26 b(2)e FD(O)s FB(\()p FD(m)1252 5414 y FC(2)1290 5447 y FB(\))p FF(.)1964 175 y(V)-5 b(ie)n(wing)31 b(a)i FE(multiMEM)i FB(\()p FD(l)r(;)15 b(p)2924 189 y FC(0)2962 175 y FD(;)g(:)g(:)g(:)i(;)e(p)3210 189 y Ft(k)q Fw(\000)p FC(1)3336 175 y FB(\))33 b FF(as)f(a)g(rectangu-)1892 275 y(lar)20 b(solid)g FB(\()p FD(p)2275 289 y FC(0)2313 275 y FD(;)15 b(:)g(:)g(:)h(;)f(p)2560 289 y Ft(k)q Fw(\000)p FC(1)2686 275 y FD(;)g(l)r(;)g(:)g(:)g(:)i(;)e(l)r FB(\))21 b FF(in)f(the)g FD(k)s FF(-dimensional)f(Eu-)1892 375 y(clidean)30 b(space)g(with)i(associated)e(weight)h FD(l)r FF(,)g(the)g(longest)f(non-)1892 474 y(o)o(v)o(erlapping)18 b(set)k(of)g(matches)e(that)i(occur)e(in)i(the)g(same)f(order)f(in)1892 574 y(e)n(v)o(ery)k(genome)g FD(G)2482 588 y FC(0)2518 574 y FD(;)15 b(:)g(:)g(:)i(;)e(G)2792 588 y Ft(k)q Fw(\000)p FC(1)2944 574 y FF(can)25 b(be)g(determined)f(by)h(com-)1892 674 y(puting)c(a)h(chain)f(with)i(maximum)e(weight)g(among)g(all)h (chains)g(of)1892 774 y(rectangular)30 b(solids,)h(see)g(Figure)g(1)g (for)h(the)f(case)g FD(k)47 b FB(=)d(2)p FF(.)32 b(As)1892 874 y(a)23 b(consequence,)c(the)k(second)e(phase)h(of)h(algorithm)f FE(MGA)h FF(tak)o(es)1892 974 y FD(O)s FB(\()p FD(k)g FA(\001)e FD(m)2195 941 y FC(2)2232 974 y FB(\))p FF(,)h(where)f FD(m)g FF(is)h(the)f(number)g(of)g FE(multiMEM)s FF(s.)1964 1073 y(A)42 b(more)f(ef)n(\002cient)h(chaining)e(algorithm)h(w)o(as)h (de)n(vised)e(by)1892 1184 y(\(Myers)31 b(&)g(Miller,)h(1995\).)e(It)h (runs)g(in)g FD(O)s FB(\()p FD(m)c FA(\001)h FB(log)3552 1141 y Ft(k)3608 1184 y FD(m)p FB(\))j FF(time)1892 1298 y(and)h FD(O)s FB(\()p FD(k)s(m)e FA(\001)f FB(log)2490 1255 y Ft(k)q Fw(\000)p FC(1)2631 1298 y FD(m)p FB(\))34 b FF(space,)e(pro)o(vided)f FD(k)51 b(<)d FB(log)17 b FD(m)p FF(.)33 b(It)1892 1397 y(remains)15 b(unclear)g(whether)h(this)g (algorithm)g(will)h(gi)n(v)o(e)e(a)i(speedup)1892 1497 y(in)k(practice.)1892 1673 y Fr(Closing)h(the)h(Gaps)1892 1798 y FF(In)47 b(the)g(third)h(phase,)d(one)i(has)g(to)g(close)g(the)g (gaps)f(in)i(the)1892 1897 y(alignment)30 b(by)h(computing)e(a)j (multiple)f(sequence)e(alignment.)1892 1997 y(W)-7 b(e)18 b(choose)f(the)h(program)f FE(ClustalW)25 b FF(\(Thompson)16 b FE(et)j(al.)p FF(,)f(1994\))1892 2097 y(for)31 b(this)h(task.)f FE(ClustalW)38 b FF(is)32 b(a)g(widely)f(used)g(implementation)1892 2197 y(of)23 b(pro\002le-based)e(progressi)n(v)o(e)g(multiple)i (alignment.)f(It)i(is)f(easy)1892 2297 y(to)32 b(interf)o(ace)f(other)h (multiple)g(alignment)f(programs)g(with)h(our)1892 2397 y(softw)o(are.)1892 2605 y FG(EXPERIMENT)-8 b(AL)24 b(RESUL)-8 b(TS)1892 2730 y FF(W)h(e)41 b(used)g(the)g(follo)n(wing)f(sets)h(of)g (DN)m(A)h(sequences)d(in)i(our)1892 2830 y(e)o(xperiments:)p Black 1892 2998 a Fg(Human/Mouse:)p Black 41 w FF(These)i(are)f(tw)o(o) h(sequences)d(from)i FE(Homo)2099 3098 y(Sapiens)16 b FF(and)g FE(Mus)g(musculus)f FF(consisting)h(of)h(222,930)d(bp.)2099 3198 y(and)25 b(227,538)e(bp.,)h(respecti)n(v)o(ely)-6 b(.)23 b(The)j(GenBank)d(acces-)2099 3298 y(sion)e(numbers)f(are)i Ff(U47924)e FF(and)h Ff(AC002397)p FF(.)p Black 1892 3468 a Fg(Mycoplasma:)p Black 40 w FF(The)47 b(complete)f(genomes)f(of) i FE(Mycoplasma)2099 3568 y(pneumoniae)36 b FF(M129)h(\(816,394)f(bp.,) h Ff(NC)p 3424 3568 23 4 v 27 w(000912)p FF(\))g(and)2099 3668 y(of)65 b FE(Mycoplasma)e(g)o(enitalium)h FF(G37)h(\(580,074)d (bp.,)2099 3767 y Ff(L43967)p FF(\).)p Black 1892 3938 a Fg(T)-8 b(uber)n(culosis:)p Black 42 w FF(The)56 b(complete)f (genomes)f(of)i(tw)o(o)h(strains)2099 4038 y(of)65 b FE(Mycobacterium)c(tuber)m(culosis)i FF(\(4,411,529)e(bp.,)2099 4137 y Ff(AL123456)p FF(;)21 b(4,403,836)e(bp.,)h Ff(AE000516)p FF(\).)p Black 1892 4308 a Fg(Str)n(eptococcus:)p Black 41 w FF(The)46 b(complete)g(genomes)f(of)i(tw)o(o)g(strains)2099 4408 y(of)79 b FE(Str)m(eptococcus)d(pneumoniae)h FF(\(2,160,837)e (bp.,)2099 4507 y Ff(NC)p 2193 4507 V 27 w(003028.1)p FF(;)21 b(2,038,615)d(bp.,)j Ff(NC)p 3238 4507 V 26 w(003098.1)p FF(\).)p Black 1892 4678 a Fg(E.)h(coli)f(2:)p Black 41 w FF(The)63 b(complete)f(genomes)g(of)h(tw)o(o)g(strains)h(of)2099 4778 y FE(Esc)o(heric)o(hia)46 b(coli)i FF(\(K-12)g(MG1655,)f (4,639,221)d(bp.,)2099 4877 y Ff(U00096.1)p FF(;)21 b(O157:H7,)f (5,528,445)f(bp.,)h Ff(AE005174.1)p FF(\).)p Black 1892 5048 a Fg(Adeno)o(virus)i(6:)p Black 41 w FF(Six)49 b(complete)f (genomes)f(of)i(human)e(ade-)2099 5148 y(no)o(viruses)40 b(\(35,937)f(bp.,)h Ff(NC)p 3050 5148 V 27 w(001405.1)p FF(;)g(35,935)f(bp.,)2099 5247 y Ff(NC)p 2193 5247 V 27 w(001406.1)p FF(;)15 b(34,214)g(bp.,)g Ff(NC)p 3113 5247 V 27 w(001454.1)p FF(;)g(34,125)f(bp.,)2099 5347 y Ff(NC)p 2193 5347 V 27 w(001460.1)p FF(;)h(35,100)g(bp.,)g Ff(NC)p 3113 5347 V 27 w(002067.1)p FF(;)g(36,521)f(bp.,)2099 5447 y Ff(NC)p 2193 5447 V 27 w(003266.1)p FF(\).)p Black -275 5630 4185 4 v -275 5729 a Fu(6)p Black eop %%Page: 7 7 7 6 bop Black -275 -76 4185 4 v Black Black -275 167 a Fg(E.)22 b(coli)f(3:)p Black 41 w FF(E.)46 b(coli)g(2)g(plus)f(the)h (complete)e(genome)g(of)i(an-)-68 267 y(other)d(strain)g(of)g(E.)h (coli)f(\(O157:H7,)e(5,498,450)g(bp.,)-68 367 y Ff(BA000007)p FF(\).)p Black -275 539 a Fg(C.)21 b(pneumoniae)i(3:)p Black 41 w FF(The)76 b(complete)g(genomes)f(of)h(three)-68 638 y(strains)17 b(of)f FE(Chlamydophila)e(pneumoniae)g FF(\(1,229,853)f(bp.,)-68 738 y Ff(AE002161)p FF(;)j(1,226,565)e(bp.,)i Ff(BA000008)p FF(;)g(1,230,230)e(bp.,)-68 838 y Ff(NC)p 26 838 23 4 v 27 w(000922.1)p FF(\).)p Black -275 1010 a Fg(S.)22 b(aur)n(eus)g(3:)p Black 41 w FF(The)60 b(complete)e (genomes)g(of)i(three)f(strains)-68 1110 y(of)47 b FE(Staphylococcus)d (aur)m(eus)i FF(\(N315,)g(2,813,641)e(bp.,)-68 1210 y Ff(NC)p 26 1210 V 27 w(002745.1)p FF(;)24 b(Mu50,)h(2,878,040)d(bp.,)i Ff(NC)p 1337 1210 V 26 w(002758.1)p FF(;)-68 1310 y(EMRSA-16)90 b(strain)f(252,)f(2,902,619)e(bp.,)i(ftp:)-68 1410 y(//ftp.sanger)-5 b(.ac.uk/pub/pathogens/sa/MRSA.dbs\).)p Black -275 1582 a Fg(S.)22 b(aur)n(eus)g(4:)p Black 41 w FF(S.)59 b(aureus)e(3)h(plus)f (the)h(complete)f(genome)-68 1681 y(of)65 b(another)e(strain)i(of)f(S.) h(aureus)f(\(NCTC)h(8325,)-68 1781 y(2,821,905)19 b(bp.,)i (ftp://ftp.genome.ou.edu/pub/staph/\).)-203 1950 y(The)45 b(\002rst)g(three)g(sets)g(of)f(sequences)f(were)h(also)h(used)f(in) -275 2050 y(\(Delcher)21 b FE(et)g(al.)p FF(,)h(1999\))e(to)h(e)n(v)n (aluate)f FE(MUMmer)r FF(.)-203 2150 y(In)33 b(a)g(\002rst)h(e)o (xperiment,)d(we)i(applied)f FE(MUMmer)i FF(and)f FE(MGA)-275 2250 y FF(to)c(the)g(\002rst)h(\002)n(v)o(e)f(sets)g(of)g(sequences.)e (F)o(or)i(a)g(f)o(air)h(comparison,)-275 2350 y(we)f(used)g(options)g (of)g FE(MGA)h FF(which)f(reproduce)f(the)h(results)h(of)-275 2450 y FE(MUMmer)r FF(.)24 b(In)i(particular)m(,)e FE(MGA)h FF(also)h(computed)d FE(MUM)s FF(s)i(and)-275 2550 y(did)40 b(not)h(apply)e(the)i(recursi)n(v)o(e)e(strate)o(gy)h(to)h(close)f(the) g(gaps.)-275 2650 y(Both)25 b(tools)h(aligned)f(a)g(gap)g(only)g(if)h (its)g(length)f(did)g(not)h(e)o(xceed)-275 2750 y(1,000)k(bp.)h FE(MGA)h FF(basically)f(deli)n(v)o(ered)f(the)i(same)f(alignments)-275 2850 y(as)d FE(MUMmer)h FF(and)e(so)h(we)g(do)g(not)g(comment)f(on)g (them.)h(Small)-275 2950 y(dif)n(ferences)21 b(in)i(the)g(alignments)f (\(if)i(the)o(y)e(occurred\))f(are)i(due)g(to)-275 3049 y(the)28 b(ad)g(hoc)g(handling)f(of)h(o)o(v)o(erlapping)e FE(MUM)s FF(s)i(in)h FE(MUMmer)r FF(,)-275 3149 y(see)42 b(Figure)h(1.)f(W)-7 b(e)43 b(report)f(on)g(the)g(co)o(v)o(erage,)e (the)i(running)-275 3249 y(time)29 b(for)g(the)f(three)h(phases)e(of)i (the)g(programs,)e(and)h(the)h(space)-275 3349 y(requirement)i(\(only)h (for)g(the)g(\002rst)i(phase,)d(since)h(this)h(requires)-275 3449 y(most)20 b(of)g(the)f(space\).)g(The)h(co)o(v)o(erage)d(is)j(the) g(percentage)e(of)i(each)-275 3549 y(sequence,)c(appearing)i(in)h(the)f (deli)n(v)o(ered)g(alignment)g(\(recall)h(that)-275 3649 y(the)40 b(tools)h(lea)n(v)o(e)f(parts)g(of)h(the)g(sequences)d (unaligned\).)h(The)-275 3749 y(co)o(v)o(erage)31 b(is)k(only)e (reported)f(once,)h(since)g(it)i(is)g(the)e(same)h(for)-275 3849 y(both)21 b(tools.)-203 3949 y(The)43 b(running)f(time)h(\(user)g (time)h(plus)e(system)h(time\))h(w)o(as)-275 4048 y(measured)33 b(on)h(a)h(SUN-Solaris)g(computer)e(with)i(a)g(750)e(MHz)-275 4148 y(SP)-8 b(ARC-CPU)28 b(and)d(4)h(GB)g(of)g(main)g(memory)-6 b(.)25 b(The)h(results)g(are)-275 4248 y(sho)n(wn)20 b(in)i(T)-7 b(ables)21 b(1)g(and)g(2.)-203 4348 y(Our)44 b(e)o(xperiment)f(sho)n(ws)g(that)h FE(MGA)h FF(is)f(by)g(f)o(ar)h (superior)-275 4448 y(to)35 b FE(MUMmer)h FF(in)f(terms)g(of)g(space)f (requirement.)g(In)h(the)g(\002rst)-275 4548 y(phase,)d FE(MGA)h FF(only)f(requires)h(between)f(8\045)g(and)h(17\045)f(of)h (the)-275 4648 y(space.)e(Thus)i FE(MGA)f FF(o)o(v)o(ercomes)e(the)j (memory)f(bottleneck)f(of)-275 4748 y FE(MUMmer)r FF(,)36 b(b)n(ut)h(still)i(has)d(a)i(running)d(time)j(adv)n(antage.)c(This)-275 4848 y(adv)n(antage)29 b(can)j(e.g.)f(be)h(seen)f(in)h(the)g(chaining)f (phase:)g(Since)-275 4948 y FE(MUMmer)36 b FF(applies)e(an)g FD(O)s FB(\()p FD(m)692 4915 y FC(2)729 4948 y FB(\))i FF(algorithm)e(to)h FD(m)f FE(MUM)s FF(s,)h(it)-275 5047 y(does)25 b(not)g(scale)h(for)f FE(Str)m(eptococcus)e FF(and)i FE(E.)i(coli)e(2)p FF(,)h(due)f(to)h(the)-275 5147 y(lar)n(ge)g(number)e(of)i FE(MUM)s FF(s.)g(The)g(co)o(v)o(erage)d (of)j(Mycoplasma)e(is)-275 5247 y(small,)k(due)g(to)h(the)f(lar)n(ge)g (dif)n(ference)f(in)i(the)f(genome)f(lengths,)-275 5347 y(the)33 b(lack)g(of)g(long)g(identical)f(matches,)g(and)h(the)g(f)o (act)g(that)h(we)-275 5447 y(closed)19 b(gaps)g(only)h(if)h(the)o(y)e (are)h(at)g(most)h(of)f(length)f(1,000)g(bp.)g(\(to)1892 166 y(mak)o(e)f(the)i(results)f(comparable\).)e(Increasing)h(the)h (maximal)g(gap)1892 267 y(length)28 b(to)i(5,000)e(bp.)g(impro)o(v)o (es)g(the)h(co)o(v)o(erage)e(to)i(38.8\045)f(and)1892 368 y(51.4\045,)20 b(respecti)n(v)o(ely)-6 b(.)1964 469 y(In)27 b(our)f(second)f(e)o(xperiment,)g(we)i(applied)f FE(MGA)h FF(to)g(the)g(\002rst)1892 570 y(\002)n(v)o(e)h(sequence)f (pairs)i(taking)f FE(MEM)s FF(s)h(as)f(anchors.)g(Gaps)g(were)1892 670 y(closed)i(only)h(if)h(the)g(sequences)d(in)i(the)h(gaps)e(had)h (an)g(identity)1892 771 y(of)41 b(at)g(least)g(60\045.)f(The)g(running) g(time)h(of)g(all)g(three)g(phases)1892 872 y(w)o(as)46 b(almost)h(the)f(same)g(as)h(in)f(e)o(xperiment)f(one)h(\(data)g(not) 1892 973 y(sho)n(wn\).)31 b(Due)i(to)g(the)g(dif)n(ferent)f(strate)o (gy)g(in)h(phase)f(\(3\),)h(gaps)1892 1074 y(consisting)d(of)i (unconserv)o(ed)c(sequences)h(are)i(not)g(forced)g(into)1892 1174 y(an)26 b(alignment.)f(On)h(the)g(other)g(hand,)f(similar)i(lar)n (ge)f(sequences)1892 1275 y(in)50 b(gaps)f(are)g(aligned)g(v)o(ery)g (ef)n(\002ciently)-6 b(.)50 b(F)o(or)g(e)o(xample,)e(in)1892 1376 y(T)l(uberculosis)29 b(we)i(found)f(a)h(gap)e(consisting)h(of)h (sequences)e(of)1892 1477 y(length)f(10722)g(and)g(10721)g(with)i(edit) f(distance)f(2.)i(These)e(had)1892 1578 y(been)34 b(e)o(xcluded)f(from) i(a)g(maximal)g(chain,)f(because)f(the)o(y)i(are)1892 1679 y(part)d(of)g(a)g FE(MEM)k FF(of)c(length)f(10724)g(which)h(o)o(v) o(erlaps)e(another)1892 1779 y FE(MEM)25 b FF(of)c(length)g(17543.)1964 1880 y(In)57 b(our)f(third)h(e)o(xperiment,)e(we)i(applied)f FE(MGA)h FF(to)g(the)1892 1981 y(sets)49 b(Adeno)o(virus)e(6,)i(E.)h (coli)g(3,)f(C.)g(pneumoniae)e(3,)i(and)1892 2082 y(S.)55 b(aureus)f(3/4,)g(see)h(T)-7 b(able)55 b(3.)f(The)h(times)g(reported)f (are)1892 2183 y(user)38 b(times)g(plus)h(system)f(times)g(in)h (minutes.)e(The)i(time)g(for)1892 2284 y(constructing)54 b(the)h(virtual)h(suf)n(\002x)g(trees)f(of)h(the)g(sequence)1892 2384 y(sets)e(is)h(not)f(included.)f(This)i(al)o(w)o(ays)f(requires)g (less)g(than)1892 2485 y(10)48 b(minutes,)g(and)g(only)g(has)g(to)h(be) f(done)f(once)h(for)h(each)1892 2586 y(sequence)35 b(set.)i(The)h (fourth)e(column)g(of)i(T)-7 b(able)37 b(3)g(sho)n(ws)g(the)1892 2687 y(total)45 b(running)f(time)h(including)f(ClustalW)-8 b(,)46 b(while)f(the)g(\002fth)1892 2788 y(column)29 b(gi)n(v)o(es)h(the)g(running)f(times)i(e)o(xcluding)e(ClustalW)-8 b(,)31 b(i.e.)1892 2889 y(the)47 b(time)h(for)f(computing)f(the)h FE(multiMEM)s FF(s)g(and)g(chaining)1892 2989 y(them.)33 b(F)o(or)h(Adeno)o(virus)e(6,)h(the)h(alignment)f(w)o(as)g(constructed) 1892 3090 y(by)44 b(recursi)n(v)o(ely)f(applying)g FE(MGA)h FF(to)h(compute)e FE(multiMEM)s FF(s)1892 3191 y(of)e(minimal)g(size)h FB(10)p FD(;)15 b FB(9)p FD(;)g(:)g(:)g(:)j(;)d FB(4)p FF(.)42 b(Gaps)f(of)g(size)h(lar)n(ger)f(than)1892 3292 y(1,000)53 b(bp.)i(remained)e(unaligned.)g(F)o(or)i(E.)h(coli)f(3,)f FE(MGA)1892 3393 y FF(constructed)23 b(the)h(alignment)g(by)g(\002rst)h (computing)e FE(multiMEM)s FF(s)1892 3493 y(of)33 b(length)f(at)i (least)f(1,000,)f(and)g(then)h(proceeded)d(recursi)n(v)o(ely)1892 3594 y(with)40 b FE(multiMEM)s FF(s)g(of)g(minimum)f(length)g(20)h(bp.) f(Note)g(that)1892 3695 y(most)k(of)h(the)g(computation)e(time)i(w)o (as)g(used)f(by)g(ClustalW)-8 b(.)1892 3796 y(F)o(or)30 b(C.)h(pneumoniae)d(3,)j(the)f(alignment)g(w)o(as)g(constructed)f(by) 1892 3897 y(recursi)n(v)o(ely)45 b(applying)g FE(MGA)i FF(to)h(compute)d FE(multiMEM)s FF(s)j(of)1892 3998 y(minimal)25 b(size)g FB(15)p FD(;)15 b FB(9)p FD(;)g FB(4)p FF(.)29 b(Note)c(that)g(most)h(of)f(the)g(running)f(time)1892 4098 y(w)o(as)k(used)f(by)h(the)g(\002rst)h(tw)o(o)f(phases)f(of)h FE(MGA)p FF(.)g(This)g(is)h(due)e(to)1892 4199 y(lack)34 b(of)g(long)f FE(multiMEM)s FF(s)i(and)e(the)i(lar)n(ge)f(number)f(of)h (short)1892 4300 y FE(multiMEM)s FF(s)39 b(in)f(the)h(genomes.)d(F)o (or)j(S.)g(aureus)e(3)i(the)f(same)1892 4401 y(length)19 b(thresholds)f(were)h(used)g(as)h(in)f(E.)h(coli)g(3.)f(F)o(or)h(S.)g (aureus)f(4)1892 4502 y(the)i(lar)n(ge)g(number)f(of)i FE(multiMEM)s FF(s)f(requires)g(to)g(use)g(the)g(length)1892 4603 y(threshold)g(of)h(25)g(in)h(the)f(recursi)n(v)o(e)f(calls.)i (This)g(in)f(turn)g(leads)g(to)1892 4703 y(a)e(reduced)e(running)g (time)i(for)g(phases)f(\(1\))h(and)f(\(2\))g(compared)f(to)1892 4804 y(S.)24 b(aureus)e(3.)h(The)g(co)o(v)o(erage)d(remains)j(high,)f (due)h(to)g(the)g(strong)1892 4905 y(similarity)f(in)f(the)h(four)f (Staphylococcus)d(strains.)1892 5120 y FG(FUTURE)24 b(W)n(ORK)1892 5245 y FF(Of)40 b(course,)e FE(MGA)i FF(should)f(be)g(supplemented)e (with)j(a)g(good)1892 5346 y(interacti)n(v)o(e)22 b(visualization)f (component.)g(This)i(is)g(a)g(challenging)1892 5447 y(task,)38 b(see)g(the)h(discussion)e(in)i(\(Miller,)g(2001\).)f(Ev)o(en)f(for)i (an)p Black -275 5630 4185 4 v 3868 5729 a Fu(7)p Black eop %%Page: 8 8 8 7 bop Black -275 -76 4185 4 v Black Black Black Black 405 161 2825 5 v 1236 269 a Fe(Phase)18 b(\(1\):)g(Computing)g Fd(MUM)s Fe(s)f(of)g(length)h Fy(\025)i Fc(`)p 405 348 V 455 455 a Fe(sequence)f(set)161 b(total)19 b(length)275 b Fc(`)330 b Fe(time)18 b(\(seconds\))345 b(memory)17 b(\(me)o(gabytes\))p 405 534 V 1805 642 a Fd(MGA)116 b(MUMmer)322 b(MGA)124 b(MUMmer)p 405 721 V 455 829 a Fe(Human/Mouse)186 b(450,468)237 b(15)314 b(0.2)297 b(1.6)430 b(4)321 b(23)455 912 y(Mycoplasma)188 b(1,396,468)237 b(20)314 b(0.9)302 b(7)475 b(8)321 b(68)455 995 y(T)m(uberculosis)191 b(8,815,365)237 b(50)286 b(32)314 b(52)441 b(36)289 b(422)455 1078 y(Streptococcus)160 b(4,199,452)237 b(20)319 b(3)314 b(22)441 b(19)289 b(202)455 1161 y(E.coli)17 b(2)290 b(10,167,666)237 b(20)286 b(13)314 b(68)441 b(39)289 b(487)p 405 1240 V -275 1493 a Fb(T)-6 b(able)24 b(1.)e Fe(Comparison)i(of)f Fd(MGA)f Fe(and)h Fd(MUMmer)i Fe(for)e(the)g (\002rst)g(\002)n(v)o(e)g(sequence)i(pairs.)e(W)-5 b(e)23 b(report)h(the)f(running)h(time)g(and)f(the)g(space)h(requirement)i (when)d(both)g(programs)-275 1572 y(compute)18 b(all)g Fd(MUM)s Fe(s)f(of)g(length)i(at)e(least)h Fc(`)p Fe(.)p Black Black Black Black 288 1875 3059 5 v 337 1983 a(sequence)h(set)363 b(Phase)18 b(\(2\):)f(Chaining)486 b(Phase)18 b(\(3\):)f(Closing)i (Gaps)286 b(Co)o(v)o(erage)p 288 2062 V 848 2170 a(#)p Fd(MUM)s Fe(s)117 b Fd(MGA)f(MUMmer)388 b(MGA)116 b(MUMmer)289 b Fe(seq1)150 b(seq2)p 288 2249 V 337 2357 a(Human/Mouse)189 b(1,037)145 b(0.02)263 b(0.04)447 b(1.9)297 b(2.3)236 b(40.4\045)100 b(37.7\045)337 2440 y(Mycoplasma)291 b(433)145 b(0.01)263 b(0.01)447 b(0.7)297 b(2.9)269 b(7.4\045)100 b(10.5\045)337 2523 y(T)m(uberculosis)244 b(1,448)145 b(0.03)263 b(0.09)447 b(0.3)297 b(2.9)236 b(93.7\045)100 b(93.9\045)337 2606 y(Streptococcus)213 b(9,351)145 b(0.27)263 b(4.1)480 b(1.0)297 b(3.0)236 b(88.6\045)100 b(93.7\045)337 2689 y(E.coli)18 b(2)342 b(35,501)145 b(1.1)269 b(60)524 b(3.1)297 b(7.1)236 b(82.8\045)100 b(69.4\045)p 288 2768 V -275 3021 a Fb(T)-6 b(able)16 b(2.)e Fe(Comparison)j(of)d Fd(MGA)h Fe(and)g Fd(MUMmer)i Fe(for)f(the)f(\002rst)g(\002)n(v)o(e)h (sequence)h(pairs.)e(W)-5 b(e)15 b(report)h(the)g(number)f(of)g Fd(MUM)s Fe(s,)f(the)i(running)g(time)g(used)f(for)g(the)h(the)g (chaining)h(phase,)-275 3100 y(and)i(the)g(running)h(time)f(for)f (closing)i(the)f(gaps.)f(The)g(last)i(tw)o(o)f(columns)g(sho)n(w)f(the) h(co)o(v)o(erage)i(for)d(the)i(sequences,)f(i.e.)g(the)g(percentage)i (of)e(bases,)f(appearing)j(in)e(the)g(deli)n(v)o(ered)-275 3179 y(alignment.)g(Since)f(both)g(tools)f(apply)i(the)e(same)g(strate) o(gy)l(,)i(their)f(co)o(v)o(erage)h(does)f(not)f(dif)n(fer)i(and)e(we)g (only)h(report)g(it)g(once.)p Black -275 3554 a FF(alignment)30 b(of)g FE(two)h FF(genomes,)e(the)i(e)o(xisting)f(solutions)f(to)i (this)-275 3653 y(problem)c(are)i(not)f(fully)h(satisf)o(actory)-6 b(.)28 b(Ho)n(we)n(v)o(er)m(,)e(it)k(should)d(be)-275 3753 y(possible)33 b(to)i(adapt)e(the)h(visualization)f(techniques)f (emplo)o(yed)-275 3853 y(in)27 b(the)g FE(REPuter)r FF(-program)e(\(K)o (urtz)i FE(et)g(al.)p FF(,)f(2001\))g(to)h(obtain)f(an)-275 3952 y(alignment)21 b(bro)n(wsing)g(system,)g(which)g(gi)n(v)o(es)g(a)h (good)f(o)o(v)o(ervie)n(w)-275 4052 y(of)16 b(an)g(entire)g FE(pairwise)g FF(alignment)g(of)g(lar)n(ge)g(sequences)e(and)i(also) -275 4152 y(allo)n(ws)22 b(zooming)e(in)j(and)e(out)h(on)g(re)o(gions)f (of)h(interest.)g(Another)-275 4251 y(research)29 b(topic)h(to)g(be)g (addressed)e(is)i(the)g(e)n(v)n(aluation)e(of)j FE(MGA)-275 4351 y FF(from)40 b(a)g(biological)e(point)i(of)g(vie)n(w)-6 b(.)39 b(Ho)n(we)n(v)o(er)m(,)f(we)i(ha)n(v)o(e)f(to)-275 4451 y(postpone)29 b(measurements)h(of)h(the)g(quality)f(of)i(the)f (alignments)-275 4550 y(deli)n(v)o(ered)37 b(by)i FE(MGA)h FF(until)f(manually)g(curated)f(datasets)g(and)-275 4650 y(protocols)20 b(for)i(such)e(an)h(e)n(v)n(aluation)f(will)i(become)e (a)n(v)n(ailable.)-275 4824 y Fr(Ackno)o(wledgements)-275 4949 y FF(S.K.)29 b(w)o(as)f(partially)h(supported)e(by)h(grant)g(KU)14 b(1257/1-2)27 b(from)-275 5049 y(the)d(Deutsche)f(F)o (orschungsgemeinschaft.)c(Robert)24 b(Gie)o(gerich,)-275 5148 y(Mohamed)47 b(Ibrahim)h(Abouelhoda,)d(and)i(Gordon)g(Gremme)-275 5248 y(carefully)62 b(read)h(pre)n(vious)f(v)o(ersions)g(of)h(the)g (manuscript.)-275 5347 y(J)7 b(\250)-36 b(orn)38 b(Clausen)f(and)h (Rainer)g(Orth)g(were)h(v)o(ery)e(helpful)h(when)-275 5447 y(performing)20 b(the)h(e)o(xperiments.)f(All)i(this)g(help)e(is)i (appreciated.)1892 3562 y FG(REFERENCES)p Black Black 1892 3678 a Fi(Altschul,)d(S.,)g(Madden,)i(T)-6 b(.,)19 b(Sch)t(\250)-29 b(af)n(fer)m(,)20 b(A.,)f(Zhang,)h(J.,)f(Zhang,)h(Z.,) f(Miller)m(,)1983 3770 y(W)-7 b(.)22 b(&)i(Lipman,)f(D.)g(\(1997\).)42 b(Gapped)25 b(BLAST)c(and)k(PSI-BLAST)l(:)20 b(A)1983 3861 y(Ne)n(w)i(Generation)g(of)g(Protein)g(Database)g(Search)g (Programs.)37 b Fh(Nucleic)1983 3952 y(Acids)18 b(Res.)p Fi(,)g Fj(25)p Fi(,)h(3389\2263402.)p Black Black 1892 4044 a(Arkin,)e(E.)g(&)g(Silv)o(erber)o(g,)g(E.)g(\(1987\).)25 b(Scheduling)18 b(Jobs)g(with)g(Fix)o(ed)f(Start)1983 4135 y(and)i(End)g(T)m(imes.)27 b Fh(Discr)m(ete)19 b(Applied)g (Mathematics)p Fi(,)h Fj(18)p Fi(,)f(1\2268.)p Black Black 1892 4226 a(Batzoglu,)37 b(S.,)e(P)o(achter)m(,)h(L.,)g(Mesiro)o (v)-5 b(,)37 b(J.,)f(Ber)o(ger)m(,)g(B.)g(&)g(Lander)m(,)h(E.)1983 4317 y(\(2000\).)114 b(Human)47 b(and)f(Mouse)h(Gene)g(Structure:)e (Comparati)n(v)o(e)1983 4409 y(Analysis)17 b(and)g(Application)g(to)g (Exon)g(Prediction.)22 b Fh(Genome)17 b(Resear)m(c)o(h)p Fi(,)1983 4500 y Fj(10)p Fi(,)i(950\226958.)p Black Black 1892 4591 a(Buhler)m(,)24 b(J.)g(\(2001\).)46 b(Ef)n(\002cient)24 b(Lar)o(ge-Scale)g(Sequence)i(Comparison)f(by)1983 4683 y(Locality-Sensiti)n(v)o(e)18 b(Hashing.)28 b Fh(Bioinformatics)p Fi(,)18 b Fj(17)p Fi(,)i(419\226428.)p Black Black 1892 4774 a(Cormen,)32 b(T)-6 b(.,)31 b(Leiserson,)h(C.)g(&)g(Ri)n(v)o(est,) f(R.)h(\(1990\).)70 b(Introduction)33 b(to)1983 4865 y(Algorithms.)27 b(MIT)18 b(Press,)g(Cambridge,)i(MA.)p Black Black 1892 4957 a(Delcher)m(,)25 b(A.,)g(Kasif,)f(S.,)h (Fleischmann,)g(R.,)g(Peterson,)g(J.,)g(White,)f(O.)h(&)1983 5048 y(Salzber)o(g,)j(S.)g(\(1999\).)59 b(Alignment)29 b(of)g(Whole)g(Genomes.)59 b Fh(Nucleic)1983 5139 y(Acids)18 b(Res.)p Fi(,)g Fj(27)p Fi(,)h(2369\2262376.)p Black Black 1892 5231 a(Durbin,)f(R.,)f(Eddy)-5 b(,)18 b(S.,)f(Krogh,)i(A.)e (&)h(Mitchison,)g(G.)g(\(1998\).)26 b(Biological)1983 5322 y(Sequence)20 b(Analysis.)27 b(Cambridge)20 b(Uni)n(v)o(ersity)f (Press.)p Black Black 1892 5413 a(Gus\002eld,)i(D.)g(\(1997\).)37 b(Algorithms)21 b(on)i(Strings,)d(T)m(rees,)i(and)g(Sequences.)p Black -275 5630 4185 4 v -275 5729 a Fu(8)p Black eop %%Page: 9 9 9 8 bop Black -275 -76 4185 4 v Black Black Black Black -94 161 3823 5 v -44 269 a Fe(sequence)19 b(set)218 b(total)19 b(length)549 b Fc(`)101 b Fe(total)19 b(time)101 b(Phases)17 b Fa(\(1\))g(+)e(\(2\))270 b Fe(Space)493 b(Co)o(v)o(erage)1483 352 y(\(minutes\))311 b(\(minutes\))101 b(\(me)o(gabytes\))292 b Fa(min)176 b Fe(a)o(vg)140 b Fa(max)p -94 431 V -44 539 a Fe(Adeno)o(virus)18 b(6)278 b(211,832)101 b(10;)17 b(9;)g(8;)h(7;)f(6;)g(5;)h(4)236 b(2:39)447 b(1:06)361 b(46)236 b(83.1\045)101 b(85.1\045)f(86.8\045)-44 622 y(E.)16 b(coli)i(3)330 b(15,666,116)c(1,000;)17 b(20)204 b(30:29)447 b(3:17)328 b(151)236 b(70.0\045)101 b(74.2\045)f(83.7\045) -44 705 y(C.)16 b(pneumoniae)k(3)134 b(3,686,648)374 b(15;)17 b(9;)h(4)203 b(93:59)413 b(61:16)329 b(110)236 b(72.7\045)101 b(80.1\045)f(83.9\045)-44 788 y(S.)16 b(aureus)i(3)293 b(8,594,300)326 b(1,000;)17 b(20)204 b(22:14)447 b(1:47)361 b(75)236 b(91.4\045)101 b(92.6\045)f(94.3\045) -44 871 y(S.)16 b(aureus)i(4)260 b(11,416,205)326 b(1,000;)17 b(25)204 b(27:45)447 b(1:17)328 b(116)236 b(87.4\045)101 b(88.9\045)f(90.2\045)p -94 949 V -275 1203 a Fb(T)-6 b(able)22 b(3.)e Fe(Application)k(of)d Fd(MGA)f Fe(to)h(the)g(Multiple) j(Genome)d(Sets.)g(The)g(third)g(column)h(sho)n(ws)f(the)g(length)i (thresholds)f(for)f(the)h Fd(multiMEM)s Fe(s)f(in)g(the)h(recursi)n(v)o (e)h(applications)-275 1282 y(of)18 b Fd(MGA)p Fe(.)f(The)h(times)h (reported)h(are)e(user)h(times)f(plus)h(system)f(times)g(in)h(minutes.) f(The)g(fourth)h(column)g(sho)n(ws)f(the)h(total)h(running)f(time)g (including)h(ClustalW)-6 b(,)19 b(while)h(the)e(\002fth)-275 1361 y(column)f(gi)n(v)o(es)h(the)f(running)h(times)f(e)o(xcluding)i (ClustalW)-6 b(,)17 b(i.e.)f(the)i(time)f(for)f(computing)i(the)g Fd(multiMEM)s Fe(s)f(and)g(chaining)i(them.)d(The)g(last)i(three)g (columns)f(sho)n(w)f(the)i(co)o(v)o(erage)-275 1439 y(for)f(the)h (sequences,)g(i.e.)f(the)h(percentage)i(of)d(bases,)g(appearing)i(in)f (the)f(deli)n(v)o(ered)k(alignment.)p Black -184 1806 a Fi(Cambridge)f(Uni)n(v)o(ersity)f(Press,)f(Ne)n(w)h(Y)-8 b(ork.)p Black Black -275 1897 a(Jacobson,)41 b(G.)f(&)g(V)-10 b(o,)40 b(K.)f(\(1992\).)95 b(Hea)o(viest)40 b(Increasing/Common)-184 1989 y(Subsequence)35 b(Problems.)74 b(In)34 b Fh(Pr)m(oceedings)h(of)e (the)h(Thir)m(d)f(Annual)-184 2080 y(Symposium)h(on)g(Combinatorial)h (P)-6 b(attern)33 b(Matc)o(hing)o(,)h(T)l(ucson,)g(Ari-)-184 2171 y(zona,)23 b(April/May)g(1992,)g(Lectur)m(e)g(Notes)g(in)g (Computer)g(Science)h(644,)-184 2262 y(Spring)o(er)c(V)-8 b(erla)o(g)p Fi(.)19 b(pp.)g(52\22666.)p Black Black -275 2354 a(Joseph,)47 b(D.,)f(Meidanis,)h(J.)f(&)g(T)m(iw)o(ari,)g(P) -8 b(.)45 b(\(1992\).)117 b(Determining)-184 2445 y(DN)m(A)38 b(Sequence)h(Similarity)e(Using)h(Maximum)i(Independent)g(Set)-184 2536 y(Algorithms)32 b(for)f(Interv)n(al)h(Graphs.)69 b(In)32 b Fh(Pr)m(oceedings)g(of)g(the)g(Thir)m(d)-184 2628 y(Scandinavian)h(W)-7 b(orkshop)33 b(on)e(Algorithm)g(Theory)l(,)g (Helsinki,)f(1992)p Fi(.)-184 2719 y(Lecture)g(Notes)g(in)g(Computer)h (Science)f(621,)h(Springer)f(V)-8 b(erlag,)30 b(pp.)-184 2810 y(326\226337.)p Black Black -275 2902 a(Kasai,)g(T)-6 b(.,)29 b(Lee,)g(G.,)h(Arimura,)f(H.,)h(Arika)o(w)o(a,)f(S.)h(&)g(P)o (ark,)f(K.)g(\(2001\).)-184 2993 y(Linear)o(-T)m(ime)43 b(Longest-Common-Pre\002x)j(Computation)f(in)g(Suf)n(\002x)-184 3084 y(Arrays)22 b(and)h(its)f(Applications.)38 b(In)22 b Fh(Pr)m(oceedings)h(of)f(the)h(12th)f(Annual)-184 3176 y(Symposium)46 b(on)g(Combinatorial)h(P)-6 b(attern)45 b(Matc)o(hing)o(,)h(J)n(erusalem,)-184 3267 y(Isr)o(ael,)37 b(J)m(uly)g(2001,)i(Lectur)m(e)e(Notes)g(in)g(Computer)h(Science)g (2089,)-184 3358 y(Spring)o(er)20 b(V)-8 b(erla)o(g)p Fi(.)19 b(pp.)g(181\226192.)p Black Black -275 3450 a(K)n(ent,)j(W)-7 b(.)22 b(&)h(Zahler)m(,)f(A.)g(\(2000\).)39 b(Conserv)n(ation,)24 b(Re)o(gulation,)f(Synten)o(y)-5 b(,)-184 3541 y(and)39 b(Introns)f(in)g(Lar)o(ge-Scale)g(C.)f(briggsae\226C.)i(ele)o(gans)f (Genomic)-184 3632 y(Alignment.)27 b Fh(Genome)20 b(Resear)m(c)o(h)p Fi(,)f Fj(10)p Fi(,)g(1115\2261125.)p Black Black -275 3724 a(K)o(urtz,)i(S.,)f(Choudhuri,)j(J.,)e(Ohleb)o(usch,)h(E.,)e (Schleiermacher)m(,)i(C.,)e(Sto)o(ye,)-184 3815 y(J.)g(&)g(Gie)o (gerich,)g(R.)g(\(2001\).)32 b(REPuter:)19 b(The)h(Manifold)h (Applications)-184 3906 y(of)e(Repeat)h(Analysis)f(on)h(a)f(Genomic)h (Scale.)28 b Fh(Nucleic)19 b(Acids)h(Res.)p Fi(,)e Fj(29)p Fi(,)-184 3998 y(4633\2264642.)p Black Black -275 4089 a(La)o(wler)m(,)35 b(E.)h(\(1976\).)84 b(Combinatorial)37 b(Optimization:)f(Netw)o(orks)h(and)-184 4180 y(Matroids.)27 b(Holt,)18 b(Rinehart,)h(and)h(W)m(inston,)e(Ne)n(w)h(Y)-8 b(ork.)p Black Black -275 4272 a(Manber)m(,)30 b(U.)e(&)h(Myers,)g(E.)f (\(1993\).)59 b(Suf)n(\002x)29 b(Arrays:)g(A)f(Ne)n(w)h(Method)-184 4363 y(for)23 b(On-Line)g(String)f(Searches.)40 b Fh(SIAM)23 b(J)n(ournal)i(on)e(Computing)p Fi(,)h Fj(22)p Fi(,)-184 4454 y(935\226948.)p Black Black -275 4546 a(McCreight,)e(E.)g (\(1976\).)38 b(A)22 b(Space-Economical)h(Suf)n(\002x)e(T)m(ree)i (Construc-)-184 4637 y(tion)c(Algorithm.)27 b Fh(J)n(ournal)20 b(of)f(the)g(A)n(CM)s Fi(,)f Fj(23)p Fi(,)h(262\226272.)p Black Black -275 4728 a(Miller)m(,)38 b(W)-7 b(.)37 b(\(2001\).)90 b(Comparison)39 b(of)g(Genomic)g(DN)m(A)f(Sequences:)-184 4820 y(Solv)o(ed)19 b(and)h(Unsolv)o(ed)f(Problems.)27 b Fh(Bioinformatics)p Fi(,)19 b Fj(17)p Fi(,)g(391\226397.)p Black Black -275 4911 a(Myers,)37 b(E.)g(&)g(Miller)m(,)f(W)-7 b(.)36 b(\(1995\).)86 b(Chaining)38 b(Multiple-Alignment)-184 5002 y(Fragments)24 b(in)g(Sub-Quadratic)h(T)m(ime.)44 b(In)24 b Fh(Pr)m(oceedings)h(of)g(the)f(Sixth)-184 5094 y(A)n(CM-SIAM)e(Symposium)j(on)f(Discr)m(ete)f(Algorithms)p Fi(.)g(San)g(Francisco,)-184 5185 y(pp.)c(38\22647.)p Black Black -275 5276 a(Needleman,)d(S.)f(&)g(W)l(unsch,)i(C.)e (\(1970\).)20 b(A)c(General)g(Method)g(Applicable)-184 5367 y(to)30 b(the)f(Search)h(for)g(Similarities)e(in)i(the)g (Amino-Acid)g(Sequence)h(of)1983 1806 y(T)-6 b(w)o(o)19 b(Proteins.)26 b Fh(J)n(.)19 b(Mol.)g(Biol.)p Fi(,)e Fj(48)p Fi(,)i(443\226453.)p Black Black 1892 1898 a(Thompson,)34 b(J.,)f(Higgins,)h(D.)f(&)g(Gibson,)h(T)-6 b(.)33 b(\(1994\).)75 b Fh(CLUST)l(AL)11 b(W)5 b Fi(:)1983 1989 y(Impro)o(ving)43 b(the)f(Sensiti)n(vity)g(of)g(Progressi)n(v)o(e)h(Multiple)f(Sequence) 1983 2080 y(Alignment)25 b(through)i(Sequence)f(W)-6 b(eighting,)25 b(Position)g(Speci\002c)g(Gap)1983 2172 y(Penalties)k(and)h(W)-6 b(eight)30 b(Matrix)g(Choice.)62 b Fh(Nucleic)30 b(Acids)f(Res.)p Fi(,)g Fj(22)p Fi(,)1983 2263 y(4673\2264680.)p Black Black 1892 2354 a(Ukk)o(onen,)20 b(E.)d(\(1985\).)26 b(Algorithms)19 b(for)f(Approximate)h(String)f (Matching.)1983 2446 y Fh(Information)h(and)h(Contr)m(ol)p Fi(,)f Fj(64)p Fi(,)g(100\226118.)p Black Black 1892 2537 a(V)l(ingron,)30 b(M.)f(&)h(Ar)o(gos,)f(P)-8 b(.)29 b(\(1989\).)62 b(A)30 b(F)o(ast)f(and)h(Sensiti)n(v)o(e)g(Multiple)1983 2628 y(Alignment)19 b(Algorithm.)27 b Fh(Comp.)19 b(Appl.)f(Biosci.)p Fi(,)g Fj(5)p Fi(,)h(115\226121.)p Black Black 1892 2720 a(W)-6 b(einer)m(,)41 b(P)-8 b(.)40 b(\(1973\).)100 b(Linear)41 b(P)o(attern)g(Matching)i(Algorithms.)99 b(In)1983 2811 y Fh(Pr)m(oceedings)24 b(of)g(the)g(14th)g(IEEE)e(Annual)j(Symposium)f (on)h(Switc)o(hing)1983 2902 y(and)19 b(A)o(utomata)g(Theory)p Fi(.)g(The)g(Uni)n(v)o(ersity)g(of)g(Io)n(w)o(a,)g(pp.)g(1\22611.)p Black -275 5630 4185 4 v 3868 5729 a Fu(9)p Black eop %%Trailer end userdict /end-hook known{end-hook}if %%EOF