I nd o ne s ia n J o urna l o f   E lect rica l En g ineering   a nd   Co m p u t er   Science   Vo l.   9 ,   No .   1 J an u ar y   201 8 ,   p p .   2 3 4 ~ 2 4 2   I SS N:  2502 - 4752 ,   DOI : 1 0 . 1 1 5 9 1 / i j ee cs . v 9 . i1 . p p 2 3 4 - 2 42           234       J o ur na l ho m ep a g e h ttp : //ia e s co r e. co m/jo u r n a ls /in d ex . p h p / ijeec s   Para lleli z a tion o Pairw ise Alig nm e nt  a nd  Neig hbo r - J o ining   Alg o rith m  in  Pro g ress iv e Multiple  Sequence  Align ment       Ag un g   Widy o   Ut o m o Wis n u Ana nta   K us u m a * Sri Wa hjuni   De p a rtme n o f   Co m p u ter S c ien c e ,   F a c u lt y   o f   M a th e m a ti c   a n d   Na tu ra S c ien c e   Bo g o A g ricu lt u ra Un iv e rsity ,   B o g o r,   W e st Ja v a ,   In d o n e sia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   Sep   11 ,   2 0 1 7   R ev i s ed   No v   2 7 ,   2 0 1 7   A cc ep ted   Dec   1 0 ,   2 0 1 7       A   P ro g re ss iv e   m u lt ip le  se q u e n c e   a li g n m e n Clu sta lW   is  a   wid e ly   u se d   h e u risti c   m e th o d   f o c o m p u ti n g   m u lt ip le  se q u e n c e   a li g n m e n (M S A ).   It  h a s   th re e   sta g e s:  d istan c e   m a tri x   c o m p u tatio n   u sin g   p a irw ise   a li g n m e n t,   g u id e   tree   re c o n stru c ti o n   u sin g   n e ig h b o r - jo i n i n g   a n d   p ro g re ss iv e   a li g n m e n t.   T o   a c c e ler a te  c o m p u ti n g   f o larg e   d a ta,  th e   p r o g re ss iv e   M S A   a lg o rit h m   n e e d to   b e   p a ra ll e li z e d .   T h is  re se a rc h   a i m to   id e n ti fy ,   d e c o m p o se   a n d   im p le m e n th e   p a irw ise   a li g n m e n a n d   n e ig h b o r - jo in i n g   in   p r o g re ss iv e   M S A   Clu sta lW   u si ng  m e ss a g e   p a ss in g ,   sh a re d   m e m o r y   a n d   h y b rid   p r o g ra m m in g   m o d e in   th e   c o m p u ter  c lu ste r.   T h e   e x p e ri m e n tal  re su lt o b tain e d   sh a re d   m e m o r y   p ro g ra m m in g   m o d e a th e   b e st  sc e n a rio   im p le m e n tatio n   w it h   sp e e d   u p   u p   t o   1 2   t im e s .   K ey w o r d s :   C lu s talW   H y b r id     M ess a g e   p ass i n g   M u ltip le   s eq u en ce   ali g n m en t   S h ar ed   m e m o r y   Co p y rig h ©   2 0 1 8   In stit u te o A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e   Al rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   W is n u   A n a n ta  K u s u m a   Dep ar t m en t o f   C o m p u ter   Scie n ce ,   Facu l t y   o f   Ma th e m atic  a n d   Natu r al  Scien ce ,   B o g o r   A g r ic u lt u r al  Un i v er s it y ,   B o g o r ,   W est J av a,   I n d o n esia .     E m ail:  a n an ta @ ap p s . ip b . ac . id       1.   I NT RO D UCT I O N   Mu ltip le  Seq u e n ce   A li g n m e n t   ( MSA )   is   b asic  p r o b lem   i n   B io in f o r m atics  t h at  ai m s   to   alig n   m o r th an   t w o   b io lo g ical   s eq u e n ce s   to   f in d   s i m ilar it y   r eg io n s .   M S A   i s   u s ed   f o r   p h y l o g en etic   an al y s is ,   id en ti f icatio n   o f   co n s er v ed   m o tif s   i n   f a m il y   o f   p r o tein s   an d   3 h o m o lo g y   m o d elin g   [ 1 ] .   T h m o s o p ti m a p air w i s alig n m e n al g o r ith m   is   d y n a m i p r o g r am m i n g ,   b u w h e n   d o n o n   th e   MS A   th co m p le x it y   is     O( L N )   w h er L   is   th le n g th   o f   th s eq u en ce   a n d   is   th n u m b er   o f   s eq u en ce   t h at  is   th NP - C o m p le te  p r o b le m   [ 1 ] .   T o   o v er co m e   th is   p r o b lem ,   h eu r i s tic  m et h o d   is   u s ed ,   o n o f   w h ich   is   p r o g r ess iv MS A   C l u s ta lW   [ 2 ]   u s i n g   g u id tr ee   as a   g u id i n   co m b i n i n g   all  p air w i s alig n m en t.   I n   ad d itio n   to   th co m p lex it y   is s u e,   th b ig   d ata  o f   s eq u en c m a k es  ch al len g in   ap p l y i n g   MS A.   O n   J u n 2 0 1 7 ,   it  is   k n o w n   t h at  th er ar 2 3 4   b illi o n   b ases   an d   2 0 1   m illi o n   s eq u en ce s   r ec o r d ed   in   Gen B an k   NC B I .   T h is   c h alle n g e   m ak e s   th e   MS al g o r ith m   n ee d s   t o   b p ar allelize d   to   i m p r o v e   th eir   p er f o r m a n ce .   So m s t u d ies  r elate d   to   p ar all eliza tio n   o f   MS A   i n cl u d C lu s talW - MP I   [ 3 ]   w h ic h   p ar alleliz th f ir s a n d   th ir d   s tag e s   o f   C lu s talW   o n   1 6   p r o ce s s o r s   u s i n g   MP I   o b tain ed   s p ee d   u p   4 . 3   ti m es   o n   p r o g r ess iv e   ali g n m e n t.   DI AL I GN - T [ 1 ]   g ain ed   3 . 1 3   tim es  s p ee d   u p   u s i n g   MP I   an d   O p en MP   h y b r id   s y s te m s   o n   2 8   co r es  h eter o g e n eo u s   m u l tico r clu s t er s   [ 4 ]   g et s   s p ee d   u p   t h r ee   ti m es  u s i n g   Star   alg o r it h m   o n   M P I   s y s te m   w it h   f i v e   co m p u ter   u n it s .   I m p le m e n tatio n   o f   p ar allel  al g o r ith m s   ca n   b d o n p ar tiall y   t o   r ed u ce   o v er all  co m p u tatio n   t i m e.   T h is   is   d o n b y   [ 3 ]   in   p ar allelizin g   th f ir s an d   th i r d   s ta g es  o f   C lu s talW   u s i n g   MP I   [ 5 ] - [ 6 ]   o n l y   p ar allelize   th e   n eig h b o r - j o in in g   w h ic h   is   t h s ec o n d   s ta g o f   C l u s talW   u s in g   th GP U   [ 7 ]   p ar allelize   th p air w is al ig n m en t   w h ic h   is   C lu s talW ' s   f ir s s tag e   u s i n g   Op e n MP .   T h is   r esear ch   ai m s   to   p ar alleli ze   in   th f ir s an d   s ec o n d   s t ag es  o f   t h p r o g r ess iv M S C lu s talW   alg o r ith m   u s in g   t h m a s s a g p ass in g ,   s h ar ed   m e m o r y ,   a n d   h y b r id   p r o g r a m m i n g   m o d el.   T h s elec tio n   o f   t h e   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       P a r a lleliz a tio n   o f P a ir w is A li g n men t a n d   N eig h b o r - Jo in in g   A lg o r ith m…   ( A g u n g   W id yo   Uto mo )   235   f ir s a n d   s ec o n d   s ta g es  is   b ase d   o n   co m p lex it y   a n al y s i s   an d   test   r esu l ts   o f   C lu s talW   al g o r i th m   [ 5 ] .   Fro m   th e   d ata  p r esen ted   b y   th r esear ch   [ 5 ] ,   it  is   k n o w n   th a th co m p lex it y   a n d   th co m p u tatio n   ti m o f   th f ir s s ta g e   ( p air w is al ig n m en t)   a n d   t h e   s ec o n d   s ta g ( n e ig h b o r - j o in i n g )   i s   g r ea ter   th a n   t h co m p l ex it y   an d   t h t h ir d   s tag co m p u ti n g   ti m ( p r o g r ess iv ali g n m en t) .   T h b en ef it s   o f   t h i s   r esear c h   ar e x p ec ted   to   i m p r o v th p er f o r m an ce   o f   p r o g r ess iv M S C lu s talW   alg o r it h m ,   esp ec iall y   p air w i s ali g n m e n an d   n eig h b o r - j o in in g   s o   th at  i ca n   s u p p o r B i o in f o r m at ics   r esear ch   th at  r eq u ir e s   MS A   r e s u lt s .       2.   RE S E ARCH   M E T H O D   E x p lain i n g   T h m et h o d   in   t h is   r esear ch   ad o p ted   th s tep s   i n   th d ec o m p o s itio n   o f     t h   p r o g r a m     f o r       p ar alleliza tio n   [ 8 ] .     T h m e th o d   is   d iv id ed   in to   f o u r   s ta g e s   th at  ca n   b s ee n   i n   Fi g u r e   1.           Fig u r 1 .    R esear ch   m eth o d       2 . 1 .   I dentif ica t io n   A th i s   s ta g w id en ti f y   th e   ca lcu latio n   co m p o n e n ts   th at   ca n   b r u n   in   p ar allel  f o r   th f ir s a n d   s ec o n d   s ta g es  o f   t h p r o g r es s iv M S A   C l u s talW   alg o r it h m   [ 8 ] .   I d en tif icatio n   is   d o n e   b y   e x a m in in g   t h p s eu d o   co d o f   b o th   s tag e s   o f   th e   al g o r ith m .   T h f ir s t   s tag e   o f   p r o g r es s i v M S A   C l u s tal W   is   co m p u ti n g   t h e   d is tan ce   m atr i x   u s in g   p air w i s alig n m en t.  I n   th is   r e s ea r ch ,   th d y n a m ic   p r o g r a m m in g   alg o r ith m   Nee d le m a n - W u n s c h   [ 9 ]   is   u s ed   as  t h o p ti m al  g lo b al  alig n m e n o f   t h t w o   s eq u e n ce s   [ 1 0 ] .   T h alg o r ith m   h a s   th r ee   s tag e s i n itia lizatio n ,   s co r in g   m atr i x   ca lc u latio n ,   an d   tr ac eb ac k .   T h s co r in g   m atr ix   v alu i s   o b tain ed   b y   f i n d in g   th m ax i m u m   v al u o f   th ce ll  o n   t h lef t,  t h to p   a n d   th d iag o n al  o f   t h in ten d e d   ce ll.  T h d is tan ce   v alu b et w ee n   th ese  s eq u en ce s   is   ca lcu lated   u s in g   E q u atio n   1 .   T h d is tan ce   v alu e s   b et w ee n   th s eq u e n ce s   ar e   s to r ed   in   th d is ta n ce   m atr ix .         ( 1 )       T h s ec o n d   s tag is   m ak in g   a   g u id tr ee   u s i n g   n e ig h b o r - j o in in g   al g o r ith m   [ 8 ] .   T h is   alg o r ith m   u s es   d is tan ce   m atr i x   f r o m   p ai r w i s ali g n m e n a s   t h in p u v al u e,   w h er e   D ( i,j )   i s   t h e   d is tan ce   b et w ee n   s eq u en ce s / n o d es  an d   j .   B asi ca ll y ,   th i s   alg o r it h m   s e lects  n o d es  i   an d     an d   m er g e s   th e m   in to   n e w   n o d es  i n   ea ch   iter atio n   u n ti l le a v in g   s in g le  n o d [ 1 2 ] .   P air s   an d   a r s elec ted   b y   m i n i m izi n g   Q ( i, j)   a s   i n   E q u atio n   2 .   W h ile  th v al u o f   u ( l )   is   o b tai n ed   ac co r d in g   to   E q u atio n   3 .       ( 2 )         ( 3 )       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l 9 ,   No .   1 J an u ar y   201 8   :   234     2 42   236   No tatio n   r   is   th n u m b er   o f   r e m ai n in g   n o d es.  T h m a tr ix   w il b u p d ated   b y   d eletin g   t h i - t h   r o w   an d   th j - t h   co lu m n   w h en   th m i n i m u m   Q( i,j )   i s   f o u n d .   Ne w   r o w s   a n d   co lu m n s   ar ad d ed   to   th m atr i x .   T h e   d is tan ce   b et w ee n   th n e w   n o d an d   th r e m ai n i n g   n o d k   is   d escr ib ed   in   E q u atio n   4 .       ( 4 )       2 . 2 .   Dec o m po s it io n   A t   t h is   s ta g e,   t h id e n ti f icatio n   r es u lt s   ar d ec o m p o s ed   a n d   d esig n ed   f o r   i m p le m e n tatio n   s ce n ar io s .   Dec o m p o s itio n   o f   p ar allel  co m p o n en t s   is   d o n b y   a n al y zin g   th p o ten t ial  o f   p ar allel   w h et h er   it  ca n   b e   d ir ec tl y   p ar alleled   o r   r eq u ir s p ec ial  tech n iq u e s .   Dec o m p o s itio n   r esu lts   ar u s ed   to   s elec t   th p r o g r a m m in g   m o d el  f o r   d esig n i n g   t h i m p le m en tatio n   s ce n ar io .   P ar allel  p r o g r a m m in g   m o d el   u s ed   is   m es s ag p as s in g ,   s h ar ed   m e m o r y   a n d   h y b r id .   I n   m e s s a g e   p ass in g   co m p u ta tio n   co n s i s t s   o f   o n o r   m o r p r o ce s s es   th at  co m m u n icate   w it h   ea c h   o t h er   b y   s en d i n g   an d   r ec eiv in g   m es s ag e s   [ 8 ] I m p l e m en tatio n   o f   m ess a g p as s i n g   is   d o n o n   d i s tr ib u ted   m e m o r y   s y s te m   u s in g   Me s s a g P ass in g   I n ter f ac ( MP I ) .   I n   th s h ar ed   m e m o r y   m o d el,   all  p r o ce s s es  s h ar e   th s a m m e m o r y   b ec au s it   is   d o n o n   o n co m p u ter .   I m p le m en ta tio n   o f   s h ar ed   m e m o r y   i s   d o n u s in g   Op e n   M u lti - P r o ce s s in g   ( Op en MP ) .   T h h y b r id   m o d e co m b i n es  t h p r o g r a m m in g   an d   i m p le m en ta tio n   m o d el s   o f   m e s s a g p ass i n g   an d   s h ar ed   m e m o r y .     2 . 3 .   I m ple m ent a t io n   T h r esu lt  o f   s eq u e n tial  p air wis ali g n m e n al g o r ith m   i s   v er if ied   u s i n g   E MB OSS  Nee d le  f r o m   E B I   UK   an d   Glo b al  A li g n m e n t - B L A ST   f r o m   NC B I   US .   B o th   o f   th e m   u s Nee d le m a n - W u n s c h   alg o r it h m .   Ver if icatio n   is   d o n t w ice  u s i n g   DN A   s eq u e n ce s .   T h f ir s v er i f icatio n   u s es  A n cy lo s to ma   d u o d en a le   mito ch o n d r io n   ( NC _ 0 0 3 4 1 5 . 1 )   an d   N ec a to r   a merica n u s   mito ch o n d r io n   ( NC _ 0 0 3 4 1 6 . 2 ) .   T h s ec o n d   v er if ica tio n   u s e s   Hu ma n   P a p illo ma viru s   typ 1 3 2   ( NC _ 0 1 4 9 5 5 . 1 )   an d   Hu ma n   p a p il lo ma viru s   typ 1 3 4   ( NC _ 0 1 4 9 5 6 . 1 ) .   T h m etr ic  u s ed   to   co m p ar th i s   al g o r ith m   is   s i m i lar it y .   T h s i m ilar it y   i s   th e   p er ce n tag e   o f   th n u m b er   o f   m atc h i n g   c h ar a ct er s   co m p ar ed   to   th len g t h   o f   th al ig n m en t f o r m ed .     T h r esu lt  o f   t h n ei g h b o r - j o in in g   al g o r ith m   is   v er if ied   u s in g   NJ   s o f t w ar f r o m   UQ A C an ad an d   th g u id tr ee   o f   C lu s ta lW   s o f t w ar f r o m   DDB J   J ap an .   C lu s talW   is   v is u alize d   u s in g   Dr a w T r ee   f r o m   P h y lo g e n y . f r   Fra n ce .   B o th   o f   th e m   u s n ei g h b o r - j o in in g   al g o r ith m .   T h is   Ver i f icatio n   u s es  th s a m o f   d ata  s eq u en ce s   i n   p air w i s ali g n m en v er if icatio n .   Ver i f icat io n   is   d o n u s i n g   v is u aliza t io n   d ata  f r o m   n ei g h b o r - j o in in g   s o f t w ar o u tp u t.   A th i s   s tag e,   t h s ce n ar io   i s   i m p le m en ted   in   th co m p u t er   clu s ter   te s ti n g   en v ir o n m e n t.  I n   ea ch   s ce n ar io ,   b o th   alg o r it h m s   ar r u n   u s i n g   v ar iatio n   o f   4   p r o ce s s o r s ,   8   p r o ce s s o r s   a n d   2 0   p r o ce s s o r s .   As  t h e   in p u t   d ata  ar u s ed   r a n d o m l y   g e n er ated   DN s eq u e n ce s   with   a n   av er a g s eq u en ce   le n g t h   o f   6 0 0   b p .   E ac h   s ce n ar io   r u n s   o n   v ar iet y   o f   s eq u en ce s   o f   2 0 ,   6 0 ,   1 8 0   an d   5 4 0   p iece s   o f   DN A   s eq u e n ce s .   T esti n g   i s   d o n as   m u c h   as  1 0   r ep etitio n s   f o r   e ac h   s ce n ar io ,   v ar iatio n s   o f   m u ltip le  co r es  ar u s ed ,   an d   v ar iatio n s   in   m a n y   s eq u en ce s .     2 . 4 .   P er f o r m a n ce  E v a lua t io   T h last   s ta g is   to   co m p ar th p er f o r m a n ce   o f   p ar allel  p r o g r a m s   f o r   ea ch   s ce n ar io .   P er f o r m a n ce   co m p ar is o n   is   d o n u s i n g   s p ee d   u p .   s p ee d   u p   is   th r atio   o f   ex ec u t io n   ti m to   s o lv t h p r o b lem   i n   s eq u en tia l   to   ex ec u tio n   ti m to   s o lv t h s a m p r o b le m   in   p ar allel.   A   p er f o r m an ce   co m p ar i s o n   is   u s e d   to   s elec th b est   p ar allel  s ce n ar io .   T h p air w is alig n m en t,  n ei g h b o r - j o in in g   an d   co m b i n ed   alg o r it h m   ar r etested   w it h   t h r ee   v ar iatio n s   o f   s eq u en ce   le n g t h   an d   th n u m b er   o f   s eq u en ce s   n a m ed   L o n g S m all,   Av g Me d iu m ,   an d   S h o r tL ar g e   as sh o w n   i n   T ab le  1 .       T ab le  1 .   T h Var iatio n   o f   Seq u en ce   L e n g th   a n d   Nu m b er   o f   Seq u en ce s                     A t t r i b u t e   L o n g S mal l   A v g M e d i u m   S h o r t L a r g e   S e q u e n c e   L e n g t h   1 4 0 0   3 5 0   90   N u mb e r   o f   S e q u e n c e s   1 0 0   3 0 0   7 0 0   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       P a r a lleliz a tio n   o f P a ir w is A li g n men t a n d   N eig h b o r - Jo in in g   A lg o r ith m…   ( A g u n g   W id yo   Uto mo )   237   2 . 5 .   T esting   E nv iro n m ent     T h is   r esear ch   u s ed   a   co m p u ter   clu s ter   co n s is ti n g   o f   o n e   u n it  8   co r es,  t w o   u n its   4   co r es  a n d   t w o   u n its   o f   2 0   co r es.  T h n o d th at  u s es  8   co r es  is   th h ea d   n o d e.   E ac h   n o d u s e s   an   I n tel®  Xe o n ®  C P E 5 - 2680  ( 2 . 7 0   GHz )   p r o ce s s o r   w it h   3 2   GB   R A r u n n i n g   o n   th   L i n u x   Ub u n t u   1 4 . 0 4   L T o p er atin g   s y s te m .   T h e   s p ee d   o f   d ata  tr an s f er   b et w ee n   n o d es  u p   to   1 0   Gb / s .   T h s o f t w ar u s ed   i s   Op en MP I   1 . 8 . 3   an d   G C C   4 . 8 . 2   co m p iler   w h ic h   s u p p o r ts   Op en MP   3 . 1 .       3.   RE SU L T A ND  AN AL Y SI S   3 . 1 .      I dentif ica t io n   3 . 1 . 1   P a ir w is Alig n m ent   P s eu d o co d o f   p air w i s alig n m en t Cl u s ta lW   ca n   b s ee n   i n   Fig u r e   2.           Fig u r e   2 .   P s eu d o co d o f   p air w is alig n m e n t   alg o r it h m       T h clu s talW - p air w is e A l ig n m en t( )   f u n c tio n   i s   a n   i n d ep en d en f u n c tio n   u s ed   to   s e t   s eq u e n ce   co m b i n atio n s   in   p air w is e Alig n m e n t( )   f u n c t io n .   T h p air w i s e A li g n m e n t( )   f u n ctio n   r etu r n s   th v alu o f   t h e   d is tan ce   b et w ee n   s eq u e n ce s   s u ch   a s   E q u atio n   1   t h at  w ill  b s to r ed   in   th d is ta n ce   m a tr i x .   T h is   f u n c tio n   h as  d ata  d ep en d en cies  in   s co r in g   m atr i x   co m p u tatio n   ( lin n u m b er   7   to   1 2   in   Fig u r e   2 )   r eq u ir ed   ce ll  d ata  o n   th e   lef t,  to p   an d   d iag o n al  s o   w h en   p ar alleled   n ee d   th s p ec ial  tech n iq u to   av o id   r ac e   co n d itio n .   A   r ac e   co n d itio n   i s   a   co n d itio n   w h er t w o   o r   m o r e   p r o ce s s es  ac ce s s   s h ar ed   m e m o r y   a t h s a m ti m e,   s o   th e   f in al   r esu lt  d ep en d s   o n   th la s e x e cu ti n g   p r o ce s s .   T h is   m a k es  al g o r ith m s   t h at  h a v d ata  d ep en d en cies  m o r li k el y   to   b r is k y   to   p ar allelize .     3 . 1 . 2   Neig hb o r - J o ini ng     P s eu d o co d o f   n eig h b o r - j o in i n g   ca n   b s ee n   i n   Fi g u r e   3 .   T h n eig h b o r - j o in in g   alg o r it h m   u s es  t h e   d is tan ce   m atr i x   o f   p air w is a li g n m e n t a s   th i n p u t v al u e.   T h id en ti f icatio n   r e s u l t o f   t h p s eu d o co d is   k n o w n   th at  t h n ei g h b o r - j o in i n g   al g o r ith m   h as  m a n y   lo o p   co n s tr u c ts   t h at  h av e   d ata  d ep en d en cie s .   I n   Fig u r e   3   li n e   n u m b er   3   to   8   ( r e p r esen tin g   E q u atio n   3 ) ,   th s u m   v ar iab l ad d s   o n ce ll  lin in   th d is tan ce   m atr i x   an d   d iv id es  it  b y   t h r e m ain in g   n o d to   g et  t h v alu e   o f   o n   t h e   i - th   r o w .   T h p r o ce s s o r s   w ill  b s i m u lta n eo u s l y   s u m m i n g   i n   p ar allel,   s o   th at  t h r esu lt is   t h las t o n s u m m i n g   u p   ( b ein g   r ac co n d itio n ) .   R ac co n d iti o n s   w ill  also   o cc u r   if   th li n n u m b er   9   to   1 5   an d   lin n u m b er   1 7   to   2 2     ar e   p a r allelize d .   T h is   is   b ec au s th p r o ce s s o r s   s ea r ch   th m i n i m u m   v alu i n   p ar allel  s o   th at  r esu lt in g   lo ca m in i m u m .   On l y   th li n n u m b er   25   an d   26   ( r ep r esen tin g   E q u atio n   4 )   is   th o n l y   in d ep en d e n p ar ts   o f   t h is   al g o r ith m .   Ho w e v er ,   b ec au s t h lo o p   co n s tr u ct io n   u s e s   o n l y   o n d i m en s io n t h e n   th e f f ec i s   n o s ig n i f ica n i f   co m p ar ed   to   th p r ev io u s   p ar ts .   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l 9 ,   No .   1 J an u ar y   201 8   :   234     2 42   238       Fig u r e   3 .   P s eu d o co d o f   n eig h b o r - j o in in g   al g o r ith m       3 . 2 .         Dec o m po s it io n   3 . 2 . 1 .    P a ir w is Alig n m e nt   T h r esu lt  o f   id e n ti f icatio n   i n d icate s   t h at  cl u s ta lW - p air w is e A li g n m en t( )   f u n c tio n   ca n   b p ar allelize d   w it h o u an y   p r o b le m   b ec au s e   it  h as  n o   d ata  d ep en d en cies.   T h en   in   p air w is e Alig n m e n t( )   f u n ctio n   n ee d s   a   s p ec ial  tech n iq u to   p ar alleli z b ec au s it   h a s   d ata  d ep en d en cies.  B ased   o n   t h ese  t w o   th i n g s   w ill b m ad f iv e   i m p le m en ta tio n   s ce n ar io s .   T h f i v s ce n ar io s   ar n a m ed   p u r eM P I ,   p u r eOp en MP ,   o m p I n n er ,   m p iO m p I n n er ,   an d   m p iO m p Ou ter .   T h p u r eM P I   s ce n ar io   d iv id e s   t h o u ter   lo o p   task   in   th e   clu s ta lW - p air w is e Alig n m e n t( )   f u n c tio n   u s i n g   MP I .   E ac h   ta s k   w ill  b s en t   to   d if f er e n p r o ce s s o r   b y   MP I ,   s o   th e   p air w is e A li g n m en t( )   f u n c tio n   f o r   ea ch   p air   co m b i n atio n   ca n   r u n   i n   p ar allel.   Data   p ar titi o n i n g   is   d o n b y   d iv id i n g   th e   n u m b er   o f   s eq u e n ce s   b y   th n u m b er   o f   p r o ce s s o r s .   T h d ata  h av b ee n   d iv id ed   is   p r o ce s s ed   b y   ea ch   p r o ce s s o r   w ith i n   ea ch   n o d e,   s o   th at  r eq u ir ed   in ter - n o d co m m u n ica tio n .   T h p u r eOp en MP   s ce n ar io   d iv id es  th e   o u ter   lo o p   tas k   in   t h clu s talW - p air w i s e A li g n m e n t ( )   f u n ctio n   u s i n g   Op en MP   s o   th at  ea c h   p air w i s e A li g n m e n t( )   f u n ctio n   f o r   ea ch   p air   co m b in atio n   is   e x ec u ted   p ar allel  b y   th th r ea d s   w i th i n   n o d e.   Par titi o n   d ata  is   d o n b y   d iv id in g   t h n u m b er   o f   s eq u e n ce s   b y   t h n u m b er   o f   th r ea d s   u s ed .   T h o m p I n n er   s ce n ar io   p a r allels  d ir ec tl y   o n   t h p air w i s e A li g n m en t( )   f u n ctio n   u s i n g   t h s h ar ed   m e m o r y   p r o g r a m m i n g   m o d e l.  T h r is k   o f   d ata  d ep en d en c y   is   ad d r ess ed   b y   s y n ch r o n izin g   [ 7 ] .   T h s y n ch r o n izatio n   i s   d o n in   t h e   f o r m   o f   ch ec k i n g   th ce ll s   r eq u ir ed   in   th ca lc u latio n .   I f   th e   r eq u ir ed   ce ll  v alu e   is   av ai lab le,   th e n   th th r ea d   ca n   co n ti n u its   w o r k .   B u t i f   t h r eq u ir ed   ce ll is   n o t a v ailab le,   t h en   t h t h r ea d   w ill  w ait  u n t il  th at  v a lu is   av a ila b le.   T h is   d ata  d e p en d en c y   ca u s e s   th is   s ce n ar io   to   b s lo w e r   th an   th p r ev io u s   in d ep en d e n s ce n ar io .   T h d at p ar titi o n   u s ed   in   th i s   s t u d y   u s e s   r o w - w i s s c h e m w h ic h   is   o n o f   th b est   s ch e m es i n   i m p le m e n ti n g   p air w i s e - A li g n m e n t( )   u s in g   Op en MP .   T h m p iO m p I n n er   h y b r id   s ce n ar io   co m b i n es  t h p u r eM P I   s ce n ar io   w it h   t h o m p I n n er   s ce n ar io .   T h o u te r   lo o p   task   in   th e   cl u s tal W - p air w i s e A li g n m e n t( )   f u n cti o n   is   d iv id ed   i n to   t h p r o ce s s o r   u s i n g   MP I ,   th e n   ea ch   p r o ce s s o r   p er f o r m s   th p air w is e Alig n m e n t( )   f u n ct io n   th at  h a s   b ee n   p ar alleled   u s i n g   Op e n MP   as  th e   o m p I n n er   s ce n ar io .   T h last   s ce n ar io   is   m p i O m p Ou ter .   I is   h y b r id   s ce n ar io   th at  f o cu s es  o n   th o u ter   lo o p   o f   th clu s ta lW - p air w is e Alig n m e n t( )   f u n ctio n .   T h is   s ce n ar io   d iv i d es  th n u m b er   o f   s eq u e n ce s   b y   t h n u m b er   o f   p r o ce s s o r s   an d   d is tr ib u tes   th e m   to   t h co m p u te  n o d u s i n g   MP I .   T h r esu lti n g   p ar tit io n   d at is   f u r th er   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       P a r a lleliz a tio n   o f P a ir w is A li g n men t a n d   N eig h b o r - Jo in in g   A lg o r ith m…   ( A g u n g   W id yo   Uto mo )   239   s u b d iv id ed   b y   Op en MP   i n to   m u ltip le  t h r ea d s .   T h en d   r es u lt  i s   s e n t   b ac k   i n to   o n e   to   t h h ea d   n o d u s i n g   MP I .     3 . 2 . 2 .    Neig hb o r - J o ini ng     T h id en tif ica tio n   r e s u l o b tain ed   t w o   p ar ts   al g o r ith m   w h ic h   h as  r ac co n d itio n   p r o b lem   a n d   o n e   in d ep en d e n t   p ar t.  B o th   p ar ts   ca n   b h an d led   w i th   p ar all el  r ed u ctio n   th a d iv id es  p ar allel  p r o ce s s i n g   in to   s ev er al  s tep s   r es u lti n g   i n   g l o b al  s o lu tio n .   I m p le m e n tatio n   o f   p ar allel  r e d u ctio n   ca n   b d o n u s i n g   Op e n MP   o n   th s h ar ed   m e m o r y   s y s te m .   T h s elec tio n   o f   Op e n MP   as  n eig h b o r - j o in in g   al g o r ith m   i m p le m en ta tio n   i s   b ased   o n   t w o   t h i n g s .   First,  t h p ar allel  r ed u ctio n   is   m o r s u itab le  f o r   s h ar ed   m e m o r y   s y s te m s ,   an d   Op en MP   h as  p ar allel  r ed u ctio n   f ea tu r th at  is   ea s y   to   i m p le m e n co m p ar ed   to   MP I .   Seco n d ,   t h s tr u c tu r o f   t h e   n eig h b o r - j o in in g   al g o r ith m   c o n s is ts   o f   m a n y   lo o p   co n s tr u cts  w h ic h   ar th co m p u ta tio n al  lo ad   o f   a n   alg o r ith m .   Op e n MP   is   d esi g n e d   to   p ar allelize   lo o p   co n s tr u cti o n   w it h o u t   t h i n k i n g   ab o u t   co m m u n icatio n   i s s u e s   as M P I .     3 . 3 .   I m ple m ent a t io n   3 . 3 . 1   P a ir w i s Alig n m ent   C o m p ar is o n   o f   s i m i lar it y   v alu es  o n   th s eq u en tial  p air w i s alig n m en w i th   b o th   v er if icatio n   s o f t w ar ca n   b s ee n   i n   T ab le  2 .   Si m ilar it y   o f   p air w i s alig n m en o b tain ed   f r o m   b o th   v er i f icatio n   is   n o m u c h   d if f er e n f r o m   E MB O SS   Nee d le  [ 1 4 ]   an d   Glo b al  A l ig n m e n B L A ST   [ 1 5 ] .   I s h o w s   t h s eq u en tial  p air w i s e   alig n m e n t a l g o r ith m   i n   th is   s t u d y   h as  s u cc e s s f u ll y   v er i f ied   w ith   o th er   s o f t w ar e.       T ab le  2 .   C o m p ar is o n   o f   Si m il ar it y   Val u es   V e r i f i c a t i o n   n u m b e r   P a i r w i se   A l i g n me n t   EM B O S S   N e e d l e   G l o b a l   A l i g n me n t   B L A S T   1   8 3 . 7 %   8 3 . 1 %   8 2 . 7 %   2   6 2 . 9 %   5 6 . 8 %   5 9 . 8 %       I m p le m e n tatio n   o f   t h f iv s c en ar io s   is   d o n o n   4 ,   8   an d   2 0   p r o ce s s o r s .   E ac h   s ce n ar io   h as  d if f er en t   co n f i g u r atio n s   to   u s t h ese  t h r ee   v ar iatio n s .   T h p u r eM P I   s ce n ar io   u s i n g   2   n o d es  ×  2   p r o c ess o r s ,   2   n o d es  ×  4   p r o ce s s o r s   an d   2   n o d es  ×  1 0   p r o ce s s o r s   f o r   co n f i g u r atio n .   T h p u r eOp en MP   an d   o m p I n n er   s ce n ar io s   u s 4   th r ea d s   o n   4   co r es  n o d an d   eig h t h r ea d s   o n   8   co r es  n o d e,   2 0   th r ea d s   o n   2 0   co r es  n o d e.   T h m p i O m p I n n e an d   m p i O m p O u ter   s ce n ar io s   u s 2   n o d es ×   1   p r o ce s s o r   ×  2   t h r ea d s ,   2   n o d es ×   2   p r o ce s s o r s   ×  2     th r ea d s   an d   2   n o d es ×   5   p r o ce s s o r s   ×  2   th r ea d s   f o r   co n f i g u r atio n .     3 . 3 . 2 .   Neig hb o r - J o ini ng     I n   th i s   v er if icat io n   o f   n ei g h b o r - j o in in g ,   A n cy lo s to ma   d u o d en a le  mito c h o n d r io n   ( NC _ 0 0 3 4 1 5 . 1 )   is   s y m b o lized   as  s eq 1 ,   N ec a to r   a merica n u s   mito ch o n d r io n   ( NC _ 0 0 3 4 1 6 . 2 )   is   s y m b o lize d   as  s eq 2 ,   Hu ma n   p a p illo ma viru s   typ 1 3 2   ( N C _ 0 1 4 9 5 5 . 1 )   is   s y m b o lized   as  s eq 3   an d   Hu ma n   p a p illo ma viru s   typ 1 3 4   ( NC _ 0 1 4 9 5 6 . 1 )   is   s y m b o lized   as  s eq 4 .   Vis u aliza tio n   tr ee   f r o m   th e   ca lcu la tio n   o f   n e ig h b o r - j o in in g   al g o r ith m   in   t h i s   s t u d y   ca n   b s ee n   i n   Fi g u r 4 .   V is u aliza tio n   tr ee f r o m   NJ   s o f t w ar e   f r o m   UQ AM   C a n ad ca n   b s ee n   i n   Fig u r 5 .   Vis u al izatio n   tr ee   f r o m   C l u s talW   f r o m   DDB J   J ap an   u s in g   Dr a w T r ee   f r o m   P y h l o g en y . f r   Fra n ce   ca n   b s ee n   in   F ig u r 6 .           Fig u r 4 .   Vis u al izatio n   tr ee   f r o m   n ei g h b o r - j o in i n g   i n   t h is   s t u d y       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l 9 ,   No .   1 J an u ar y   201 8   :   234     2 42   240       Fig u r 5 .   Vis u al izatio n   tr ee   f r o m   NJ   So f t w ar e           Fig u r 6 .   Vis u al izatio n   tr ee   f r o m   C l u s talW   u s i n g   Dr a w T r ee       Fro m   th t h r ee   i m a g es  ca n   b s ee n   th a th v is u aliza t io n   o f   th tr ee   in   d i f f er e n p r o g r am s   h as  t h e   s a m s h ap e.   I n   ad d itio n   to   t h e   tr ee   s h ap e,   t h p o s itio n   o f   s e q 1   w it h   s eq 2   an d   s eq 3   w i th   s eq 4   ar in   th s a m lo ca tio n .   I n   Fi g u r 4   a n d   5 ,   it   is   k n o w n   t h at  n o d n u m b er   f iv r ep r ese n ts   th e   n e w   n o d f r o m   t h m er g i n g   o f   n o d s eq 1   an d   n o d e   s eq 2 .   T h e s th r ee   p o in ts   s h o w   t h s eq u e n tial  n e ig h b o r - j o in in g   alg o r it h m   in   t h is   s t u d y   h as   s u cc e s s f u ll y   v er if ied   w it h   o th e r   s o f t w ar e.   I m p le m e n tatio n   o f   n eig h b o r - j o in in g   is   o n l y   d o n u s i n g   Op en MP   o n   th s h ar ed   m e m o r y   s y s te m .   I m p le m e n tat io n   is   d o n u s in g   4   th r ea d s   o n   4   co r es  co m p u ter   n o d an d   8   th r ea d s   o n   eig h t c o r es c o m p u ter   n o d an d   2 0   th r ea d s   o n   2 0   co r es c o m p u ter   n o d es.     3 . 4 .   P er f o r m a nce  E v a lua t io n   3 . 4 . 1   P a ir w is Alig n m ent   A t h i s   s ta g e,   th f i v p air w i s alig n m en i m p le m e n tatio n   s ce n ar io s   w il b co m p ar ed   u s i n g   th p ar allel  p r o g r am   p er f o r m an ce   m etr ics  to   f i n d   t h b est  s ce n ar io s .   T h i m p le m e n tatio n   o f   p ar allel  p air w is e   alig n m e n t   alg o r it h m s   h as   t h r ee   d i m e n s io n s   o f   i m p le m en ta ti o n   v ar iat io n   s ce n ar io s ,   n u m b er   o f   s eq u en ce s   a n d   n u m b er   o f   p r o ce s s o r s .   Fo r   e ase  o f   co m p ar is o n ,   o n v ar i ab le  w ill  b ch o s en   o n v ar iatio n   s o   th at  th e   co m p ar is o n   b ec o m es t w o   d i m en s io n s .   I n   th e   u s o f   2 0   p r o ce s s o r   d ata  as  s h o w n   i n   Fi g u r 7 ,   it  c an   b s ee n   t h at  t h e   o m p I n n er   an d   m p i O m p I n n er   s ce n ar io s   ca n   n o co m p lete  t h w o r k   w h en   u s i n g   5 4 0   s eq u en ce s .   T h is   is   b ec au s b o th   s ce n ar io s   p ar allelize   p ar th at  h a s   d ata  d ep en d en c y   an d   it  r eq u ir es  lo o f   s y n c h r o n izatio n   th a o v er lo ad s   th e   o p er atin g   s y s te m .     I n   Fig u r 7   is   also   k n o w n   th a th p u r eOp en MP   s ce n ar io   h as  m u c h   b etter   s p ee d   u p   im p r o v e m en t h an   t h e   o th er   f o u r   s ce n ar io s .   B ased   o n   th at  co n s id er atio n ,   th p u r eO p en MP   s ce n ar io   is   ch o s e n   as t h b est s ce n ar io .           Fig u r 7 .   C o m p ar is o n   o f   s p ee d   u p   in   p ar allel  p air w is ali g n m en t u s in g   2 0   co r es c o m p u ter   Evaluation Warning : The document was created with Spire.PDF for Python.
I n d o n esia n   J   E lec  E n g   &   C o m p   Sci     I SS N:  2502 - 4752       P a r a lleliz a tio n   o f P a ir w is A li g n men t a n d   N eig h b o r - Jo in in g   A lg o r ith m…   ( A g u n g   W id yo   Uto mo )   241   3 . 4 . 2 .   Neig hb o r - J o ini ng     T h r esu lt  o f   t h p ar allel  n e ig h b o r - j o in i n g   a lg o r it h m   i m p le m e n tatio n   ca n   b s ee n   in   Fig u r 8 .   I m p r o v e m e n o f   s p ee d   u p   o cc u r s   w h e n   u s i n g   1 8 0   s eq u en ce s .   T h is   h ap p en s   b ec au s t h lo a d   o n   ea ch   th r ea d   is   t o o   s m all  i n   th n u m b er   o f   s e q u en ce s   2 0   an d   6 0 .   T h co m p u tatio n   ti m b ec o m e s   lo n g er   th an   t h s eq u en t ial   i m p le m en ta tio n   d u to   t h co s t o f   s y n c h r o n izatio n   b et w ee n   t h r ea d s   in   p ar allel  r ed u ctio n .     3 . 4 . 3 .   T he  Co m bin e d Alg o rit h m   T h p air w is e   ali g n m e n t,  n ei g h b o r - j o in in g ,   a n d   th e   co m b i n e d   alg o r ith m   o f   b o t h   te s ted   u s i n g   v ar y i n g   d ata  to   d eter m in e   t h c h ar ac ter is tics   a n d   r o b u s t n es s   o f   t h al g o r ith m .   F ig u r 9   s h o w s   th e   c o m p ar is o n   o f   s p ee d   u p   o n   th r ee   al g o r it h m s   u s i n g   L o n g S m all,   A v g Me d i u m   a n d   S h o r tL ar g d ata.   T h g r ap h   s h o w s   th at   t h e   co m b i n ed   al g o r ith m   i s   s tr o n g l y   i n f lu e n ce d   b y   t h al g o r ith m   p air w is a lig n m e n w it h   t h s p ee d   u p   r ea ch i n g   1 2   ti m es.   T h is   i s   b ec au s t h p air w is e   ali g n m e n a lg o r i th m   h as   lar g er   p o r tio n   o f   co m p u ta tio n   ti m e   co m p ar ed   to   n ei g h b o r - j o in in g .   T h is   d o es  n o m ea n   t h at  p ar a llel  n ei g h b o r - j o in in g   al g o r ith m   d o   n o co n tr ib u te  to   th co m b i n ed   al g o r ith m .   I f   th co m b i n ed   al g o r ith m   u s e s   s eq u en tial   n ei g h b o r - j o in in g ,   t h en   t h s p ee d   u p   o n   th v ar iatio n   o f   Sh o r t L ar g e   w il d ec r ea s to   4 . 7   ti m es.  I m p r o v e m e n t   o f   s p ee d   u p   i n   t h n eig h b o r - j o in in g   alg o r ith m   is   ac h ie v ed   w h e n   t h n u m b er   o f   s eq u en ce s   i s   l ar g e.   T h is   co n tr ib u te s   to   k ee p   r o b u s tn e s s   o f   t h e   co m b i n ed   alg o r it h m   o n   lar g e   n u m b er   o f   s eq u e n ce s .           Fig u r 8 .     C o m p ar is o n   o f   s p ee d   u p   in   p ar allel  n ei g h b o r - j o in i n g           Fig u r 9 .   C o m p ar is o n   o f   s p ee d   u p   in   p air w i s alig n m e n t,  n e ig h b o r - j o in i n g ,   a n d   co m b in ed   alg o r ith m   u s i n g   v ar iatio n   o f   d ata       4.   CO NCLU SI O NS   I n   t h is   r e s ea r ch ,   t h b es s ce n ar io   is   u s in g   a   s h ar ed   m e m o r y   p r o g r a m m in g   m o d el  w i t h   Op e n MP   i m p le m en ta tio n   to   p ar alleliz th e   p air w i s al ig n m en a n d   n e ig h b o r - j o in in g   al g o r ith m s .   T h co m b in ed   alg o r ith m   u s i n g   t h is   s ce n ar i o   o b tain ed   s p ee d - u p   u p   to   1 2   tim es  o n   2 0   co m p u ter   co r es.  T h co m b in ed   alg o r ith m   p r o v ed   r o b u s t in   t h e   v ar iatio n   o f   D N A   s eq u e n ce s .       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 5 0 2 - 4752   I n d o n esia n   J   E lec  E n g   &   C o m p   Sci,   Vo l 9 ,   No .   1 J an u ar y   201 8   :   234     2 42   242   ACK NO WL E D G M E NT   T h au th o r s   w o u ld   lik to   th a n k   t h Ag e n c y   f o r   A s s es s m en an d   A p p licatio n   o f   T ec h n o lo g y   ( B P PT )   f o r   th s c h o lar s h ip   f u n d   an d   t h g r id   co m p u ti n g   f ac ili t y .       RE F E R E NC E S   [1 ]     M a c e d o   EA ,   Bo u k e rc h e   A .   Hy b rid   M PI/ Op e n M stra teg y   fo r   b io lo g ica mu l ti p le  se q u e n c e   a li g n me n wit h   DIAL IGN - T in   h e ter o g e n e o u mu lt ico re   c lu ste rs .   IEE In t e rn a ti o n a P a ra ll e &   Distrib u ted   P r o c e ss in g   S y m p o siu m .   S h a n g h a i .   2 0 1 1 4 1 8 - 4 2 5 .   [2 ]     T h o m p so n   JD ,   Hig g in D G ,   G ib so n   T J.  CL US TAL W i m p ro v in g   th e   se n siti v it y   o f   p ro g re ss iv e   m u lt ip le  se q u e n c e   a li g n m e n th ro u g h   se q u e n c e   we ig h ti n g ,   p o siti o n - sp e c if ic  g a p   p e n a l ti e a n d   we ig h m a tri x   c h o ice .   Nu c leic   Acid Res .   1 9 9 4 2 2 ( 2 2 ) 4 6 7 3 - 4 6 8 0 .   [3 ]     L KB.  Clu sta lW - M P I:  Cl u sta lW   a n a ly sis  u sin g   p a ra ll e a n d   d istri b u ted   c o m p u ti n g .   Bi o i n fo rm a ti c s .   2 0 0 3 1 9 1 5 8 5 1 5 8 6 .   [4 ]     S a tra  R,   Ku s u m a   WA ,   S u k o c o   H.  Ac c e ler a ti n g   c o m p u tatio n   o f   DN A   m u lt ip le  se q u e n c e   a li g n m e n in   d istr ib u ted   e n v iro n m e n t.   T e lko mn ika   In d o n e sia n   J o u rn a o E lec trica En g i n e e rin g .   2 0 1 4 1 2 (1 2 ):  8 2 7 8 8 2 8 5 .   [5 ]     L iu   Y,  S c h m id B,   Do u g las   L M .   Pa r a ll e re c o n str u c ti o n   o n e ig h b o r - jo in i n g   tre e fo la r g e   mu lt ip le  se q u e n c e   a li g n me n ts  u si n g   CUD A.   P r o c e e d in g o f   2 3 r d   IEE In ter n a ti o n a P a ra ll e &   Distrib u ted   P r o c e ss in g   S y m p o siu m .   Ro m e .   2 0 0 9 .   [6 ]     Zh e n g   R,   Zh a n g   Q,   Jin   H,  S h a o   Z,   F e n g   X .   A   G P U - b a se d   p a r a ll e m e th o d   f o e v o lu ti o n a ry   tree   c o n str u c ti o n .   Co mp u ter a n d   El e c trica E n g in e e rin g .   2 0 1 4 ;   4 0 (5 ):   1 5 8 0 1 5 9 1 .   [7 ]     Ak b a A R,   S u k o c o   H,  Ku su m a   WA .   Co m p a riso n   o f   d a ta  p a rti ti o n i n g   sc h e m a   o f   p a ra ll e p a ir w i se   a li g n m e n o n   sh a re d   m e m o r y   s y ste m .   T e lko mn ika   In d o n e si a n   J o u rn a o E lec trica E n g i n e e rin g .   2 0 1 5 1 3 ( 2 ):  6 9 4 - 7 0 2 .   [8 ]     Do n g a rra   J,  F o ste I,   F o x   G ,   G ro p p   W ,   Ke n n e d y   K,  T o rc z o n   L ,   W h it e   A .   S o u rc e   Bo o k   o f   P a ra ll e Co m p u ti n g .   S a n   F ra n c isc o M o rg a n   Ka u fm a n n   P u b li sh e rs.  2 0 0 3 .   [9 ]     Ne e d le m a n   S B,   W u n sc h   CD.  A   g e n e ra m e th o d   a p p li c a b le  to   se a rc h   f o si m il a rit ies   in   t h e   a m in o   a c id   se q u e n c e   o tw o   p ro tein s.   J o u r n a l   o M o lec u la r B io l o g y .   1 9 7 0 ;   4 8 4 4 3 - 4 5 3 .   [1 0 ]     Uto m o   AW ,     Ku su m a   WA .   Pen ja ja ra n   g lo b a se k u e n   DNA   me n g g u n a k a n   a lg o ritme   Ne e d lem a n     W u n sc h .   S e m in a r   Na sio n a d a n   Ra p a T a h u n a n   Bid a n g   M I P A   (S e m irata   2 0 1 4 ) .   Bo g o r.   2 0 1 4 Bo o k   3 :   2 1 0 - 2 1 8 .   [1 1 ]     S a it o u   N,  Ne i   M .   T h e   n e ig h b o r - jo in i n g   m e th o d :   a   n e w   m e th o d   f o re c o n str u c ti n g   p h y lo g e n e ti c   tr e e s.  M o lec u la Bi o lo g y   a n d   Evo l u ti o n .   1 9 8 7   4 (4 ):  4 0 6 - 4 2 5 .   [1 2 ]     S im o n se n   M ,   M a il u n d   T ,   P e d e rs e n   CN.  R a p id   Ne i g h b o u J o i n i n g .   P ro c e e d in g o f   8 th   in t e r n a ti o n a w o rk sh o p   o n   a lg o rit h m s in   b io in f o rm a ti c s.  Be rl in .   2 0 0 8 .     Evaluation Warning : The document was created with Spire.PDF for Python.