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 f  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 t  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 l  S c ien c e   Bo g o r  A g ricu lt u ra l  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 t  Clu sta lW   is  a   wid e ly   u se d   h e u risti c   m e th o d   f o r  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 t  (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 r  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 s  to   b e   p a ra ll e li z e d .   T h is  re se a rc h   a i m s  to   id e n ti fy ,   d e c o m p o se   a n d   im p le m e n t  th e   p a irw ise   a li g n m e n t  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 l  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 s  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 l  a s  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 t  ©   2 0 1 8   In stit u te o f  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 l  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   a  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 e  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   a  f a m il y   o f   p r o tein s   an d   3 D  h o m o lo g y   m o d elin g   [ 1 ] .   T h e  m o s t  o p ti m a l  p air w i s e  alig n m e n t  al g o r ith m   is   d y n a m i c  p r o g r am m i n g ,   b u t  w h e n   d o n e  o n   th e   MS A   th e  co m p le x it y   is     O( L N )   w h er e  L   is   th e  le n g th   o f   th e  s eq u en ce   a n d   N  is   th e  n u m b er   o f   s eq u en ce   t h at  is   th e  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 e  o f   w h ich   is   p r o g r ess iv e  MS A   C l u s ta lW   [ 2 ]   u s i n g   g u id e  tr ee   as a   g u id e  i n   co m b i n i n g   all  p air w i s e  alig n m en t.   I n   ad d itio n   to   th e  co m p lex it y   is s u e,   th e  b ig   d ata  o f   s eq u en c e  m a k es  a  ch al len g e  in   ap p l y i n g   MS A.   O n   J u n e  2 0 1 7 ,   it  is   k n o w n   t h at  th er e  ar e  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 A  al g o r ith m   n ee d s   t o   b e  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 e  s t u d ies  r elate d   to   p ar all eliza tio n   o f   MS A   i n cl u d e  C lu s talW - MP I   [ 3 ]   w h ic h   p ar alleliz e  th e  f ir s t  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 X  [ 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 e  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 e  d o n e  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 e  b y   [ 3 ]   in   p ar allelizin g   th e  f ir s t  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 e  s ec o n d   s ta g e  o f   C l u s talW   u s in g   th e  GP U   [ 7 ]   p ar allelize   th e  p air w is e  al ig n m en t   w h ic h   is   C lu s talW ' s   f ir s t  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 e  f ir s t  an d   s ec o n d   s t ag es  o f   t h e  p r o g r ess iv e  M S A  C lu s talW   alg o r ith m   u s in g   t h e  m a s s a g e  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 e  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 e  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 t  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 e  r esear ch   [ 5 ] ,   it  is   k n o w n   th a t  th e  co m p lex it y   a n d   th e  co m p u tatio n   ti m e  o f   th e  f ir s t  s ta g e   ( p air w is e  al ig n m en t)   a n d   t h e   s ec o n d   s ta g e  ( n e ig h b o r - j o in i n g )   i s   g r ea ter   th a n   t h e  co m p l ex it y   an d   t h e  t h ir d   s tag e  co m p u ti n g   ti m e  ( p r o g r ess iv e  ali g n m en t) .   T h e  b en ef it s   o f   t h i s   r esear c h   ar e  e x p ec ted   to   i m p r o v e  th e  p er f o r m an ce   o f   p r o g r ess iv e  M S A  C lu s talW   alg o r it h m ,   esp ec iall y   p air w i s e  ali g n m e n t  an d   n eig h b o r - j o in in g   s o   th at  i t  ca n   s u p p o r t  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 e  m et h o d   in   t h is   r esear ch   ad o p ted   th e  s tep s   i n   th e  d ec o m p o s itio n   o f     t h e    p r o g r a m     f o r       p ar alleliza tio n   [ 8 ] .     T h e  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 e  s ee n   i n   Fi g u r e   1.           Fig u r e  1 .    R esear ch   m eth o d       2 . 1 .   I dentif ica t io n   A t  th i s   s ta g e  w e  id en ti f y   th e   ca lcu latio n   co m p o n e n ts   th at   ca n   b e  r u n   in   p ar allel  f o r   th e  f ir s t  a n d   s ec o n d   s ta g es  o f   t h e  p r o g r es s iv e  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 e  p s eu d o   co d e  o f   b o th   s tag e s   o f   th e   al g o r ith m .   T h e  f ir s t   s tag e   o f   p r o g r es s i v e  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 e  alig n m en t.  I n   th is   r e s ea r ch ,   th e  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 e  o p ti m al  g lo b al  alig n m e n t  o f   t h e  t w o   s eq u e n ce s   [ 1 0 ] .   T h e  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 e  s co r in g   m atr ix   v alu e  i s   o b tain ed   b y   f i n d in g   th e  m ax i m u m   v al u e  o f   th e  ce ll  o n   t h e  lef t,  t h e  to p   a n d   th e  d iag o n al  o f   t h e  in ten d e d   ce ll.  T h e  d is tan ce   v alu e  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 e  d is tan ce   v alu e s   b et w ee n   th e  s eq u e n ce s   ar e   s to r ed   in   th e  d is ta n ce   m atr ix .         ( 1 )       T h e  s ec o n d   s tag e  is   m ak in g   a   g u id e  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   D  f r o m   p ai r w i s e  ali g n m e n t  a s   t h e  in p u t  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  i  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   j    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   a  s in g le  n o d e  [ 1 2 ] .   P air s   i  an d   j  a r e  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 e  v al u e  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 e  n u m b er   o f   r e m ai n in g   n o d es.  T h e  m a tr ix   w il l  b e  u p d ated   b y   d eletin g   t h e  i - t h   r o w   an d   th e  j - t h   co lu m n   w h en   th e  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 e  ad d ed   to   th e  m atr i x .   T h e   d is tan ce   b et w ee n   th e  n e w   n o d e  a  an d   th e  r e m ai n i n g   n o d e  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 e  id e n ti f icatio n   r es u lt s   ar e  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 e  b y   a n al y zin g   th e  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 e  s p ec ial  tech n iq u e s .   Dec o m p o s itio n   r esu lts   ar e  u s ed   to   s elec t   th e  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 e  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 e  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   a  co m p u ta tio n   co n s i s t s   o f   o n e  o r   m o r e  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 e  p as s i n g   is   d o n e  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 e  P ass in g   I n ter f ac e  ( MP I ) .   I n   th e  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 e  s a m e  m e m o r y   b ec au s e  it   is   d o n e  o n   o n e  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 e  u s in g   Op e n   M u lti - P r o ce s s in g   ( Op en MP ) .   T h e  h y b r id   m o d e l  co m b i n es  t h e  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 e  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 e  r esu lt  o f   s eq u e n tial  p air wis e  ali g n m e n t  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 e  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 e  t w ice  u s i n g   DN A   s eq u e n ce s .   T h e  f ir s t  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 e  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 e  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 e  1 3 4   ( NC _ 0 1 4 9 5 6 . 1 ) .   T h e  m etr ic  u s ed   to   co m p ar e  th i s   al g o r ith m   is   a  s i m i lar it y .   T h e  s i m ilar it y   i s   th e   p er ce n tag e   o f   th e  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 e  len g t h   o f   th e  al ig n m en t f o r m ed .     T h e  r esu lt  o f   t h e  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 e  f r o m   UQ A M  C an ad a  an d   th e  g u id e  tr ee   o f   C lu s ta lW   s o f t w ar e  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 e  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 e  s a m e  o f   d ata  s eq u en ce s   i n   p air w i s e  ali g n m en t  v er if icatio n .   Ver i f icat io n   is   d o n e  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 e  o u tp u t.   A t  th i s   s tag e,   t h e  s ce n ar io   i s   i m p le m en ted   in   th e  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 e  r u n   u s i n g   a  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 e  u s ed   r a n d o m l y   g e n er ated   DN A  s eq u e n ce s   with   a n   av er a g e  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   a  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 e  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 e  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 n    T h e  last   s ta g e  is   to   co m p ar e  th e  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 e  u s i n g   s p ee d   u p .   s p ee d   u p   is   th e  r atio   o f   ex ec u t io n   ti m e  to   s o lv e  t h e  p r o b lem   i n   s eq u en tia l   to   ex ec u tio n   ti m e  to   s o lv e  t h e  s a m e  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 t  th e  b est   p ar allel  s ce n ar io .   T h e  p air w is e  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 e  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 e  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 e  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 e  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 e  n o d e  th at  u s es  8   co r es  is   th e  h ea d   n o d e.   E ac h   n o d e  u s e s   an   I n tel®  Xe o n ®  C P U  E 5 - 2680  ( 2 . 7 0   GHz )   p r o ce s s o r   w it h   3 2   GB   R A M  r u n n i n g   o n   th e    L i n u x   Ub u n t u   1 4 . 0 4   L T S  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 e  s o f t w ar e  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 S  A ND  AN AL Y SI S   3 . 1 .      I dentif ica t io n   3 . 1 . 1   P a ir w is e  Alig n m ent   P s eu d o co d e  o f   p air w i s e  alig n m en t Cl u s ta lW   ca n   b e  s ee n   i n   Fig u r e   2.           Fig u r e   2 .   P s eu d o co d e  o f   p air w is e  alig n m e n t   alg o r it h m       T h e  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 t  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 e  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 e  v alu e  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 e  s to r ed   in   th e  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 e  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 e  s p ec ial  tech n iq u e  to   av o id   a  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 e  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  t h e  s a m e  ti m e,   s o   th e   f in al   r esu lt  d ep en d s   o n   th e  la s t  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 e  d ata  d ep en d en cies  m o r e  li k el y   to   b e  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 e  o f   n eig h b o r - j o in i n g   ca n   b e  s ee n   i n   Fi g u r e   3 .   T h e  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 e  a li g n m e n t a s   th e  i n p u t v al u e.   T h e  id en ti f icatio n   r e s u l t o f   t h e  p s eu d o co d e  is   k n o w n   th at  t h e  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 e  s u m   v ar iab l e  ad d s   o n e  ce ll  lin e  in   th e  d is tan ce   m atr i x   an d   d iv id es  it  b y   t h e  r e m ain in g   n o d e  to   g et  t h e  v alu e   o f   u  o n   t h e   i - th   r o w .   T h e  p r o ce s s o r s   w ill  b e  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 e  r esu lt is   t h e  las t o n e  s u m m i n g   u p   ( b ein g   r ac e  co n d itio n ) .   R ac e  co n d iti o n s   w ill  also   o cc u r   if   th e  li n e  n u m b er   9   to   1 5   an d   lin e  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 e  th e  p r o ce s s o r s   s ea r ch   th e  m i n i m u m   v alu e  i n   p ar allel  s o   th at  r esu lt in g   lo ca l  m in i m u m .   On l y   th e  li n e  n u m b er   25   an d   26   ( r ep r esen tin g   E q u atio n   4 )   is   th e  o n l y   in d ep en d e n t  p ar ts   o f   t h is   al g o r ith m .   Ho w e v er ,   b ec au s e  t h e  lo o p   co n s tr u ct io n   u s e s   o n l y   o n e  d i m en s io n ,  t h e n   th e  e f f ec t  i s   n o t  s ig n i f ica n t  i f   co m p ar ed   to   th e  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 e  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 e  Alig n m e nt   T h e  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 e  p ar allelize d   w it h o u t  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 e  to   p ar alleli z e  b ec au s e  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 e  m ad e  f iv e   i m p le m en ta tio n   s ce n ar io s .   T h e  f i v e  s ce n ar io s   ar e  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 e  p u r eM P I   s ce n ar io   d iv id e s   t h e  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 e  s en t   to   a  d if f er e n t  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 e  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 e  n u m b er   o f   p r o ce s s o r s .   T h e  d ata  h av e  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 e  co m m u n ica tio n .   T h e  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 e  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 e  th r ea d s   w i th i n   a  n o d e.   Par titi o n   d ata  is   d o n e  b y   d iv id in g   t h e  n u m b er   o f   s eq u e n ce s   b y   t h e  n u m b er   o f   th r ea d s   u s ed .   T h e  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 e  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 e  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 e  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 e  s y n ch r o n izatio n   i s   d o n e  in   t h e   f o r m   o f   ch ec k i n g   th e  ce ll s   r eq u ir ed   in   th e  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 e  th r ea d   ca n   co n ti n u e  its   w o r k .   B u t i f   t h e  r eq u ir ed   ce ll is   n o t a v ailab le,   t h en   t h e  t h r ea d   w ill  w ait  u n t il  th at  v a lu e  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 e  s lo w e r   th an   th e  p r ev io u s   in d ep en d e n t  s ce n ar io .   T h e  d at a  p ar titi o n   u s ed   in   th i s   s t u d y   u s e s   a  r o w - w i s e  s c h e m e  w h ic h   is   o n e  o f   th e  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 e  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 e  p u r eM P I   s ce n ar io   w it h   t h e  o m p I n n er   s ce n ar io .   T h e  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 e  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 e  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 e  last   s ce n ar io   is   m p i O m p Ou ter .   I t  is   a  h y b r id   s ce n ar io   th at  f o cu s es  o n   th e  o u ter   lo o p   o f   th e  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 e  n u m b er   o f   s eq u e n ce s   b y   t h e  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 e  co m p u te  n o d e  u s i n g   MP I .   T h e  r esu lti n g   p ar tit io n   d at a  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 e  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 e  en d   r es u lt  i s   s e n t   b ac k   i n to   o n e   to   t h e  h ea d   n o d e  u s i n g   MP I .     3 . 2 . 2 .    Neig hb o r - J o ini ng     T h e  id en tif ica tio n   r e s u l t  o b tain ed   t w o   p ar ts   al g o r ith m   w h ic h   h as  a  r ac e  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 e  h an d led   w i th   a  p ar all el  r ed u ctio n   th a t  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   a  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 e  d o n e  u s i n g   Op e n MP   o n   th e  s h ar ed   m e m o r y   s y s te m .   T h e  s elec tio n   o f   Op e n MP   as  a  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 e  p ar allel  r ed u ctio n   is   m o r e  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  a  p ar allel  r ed u ctio n   f ea tu r e  th at  is   ea s y   to   i m p le m e n t  co m p ar ed   to   MP I .   Seco n d ,   t h e  s tr u c tu r e  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 e  th e  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 e  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 e  s eq u en tial  p air w i s e  alig n m en t  w i th   b o th   v er if icatio n   s o f t w ar e  ca n   b e  s ee n   i n   T ab le  2 .   Si m ilar it y   o f   p air w i s e  alig n m en t  o b tain ed   f r o m   b o th   v er i f icatio n   is   n o t  m u c h   d if f er e n t  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 t  B L A ST   [ 1 5 ] .   I t  s h o w s   t h e  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 e  f iv e  s c en ar io s   is   d o n e  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 e  t h ese  t h r ee   v ar iatio n s .   T h e  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 e  p u r eOp en MP   an d   o m p I n n er   s ce n ar io s   u s e  4   th r ea d s   o n   4   co r es  n o d e  an d   eig h t  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 e  m p i O m p I n n e r  an d   m p i O m p O u ter   s ce n ar io s   u s e  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 e  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 e  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 e  s ee n   i n   Fi g u r e  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 a  ca n   b e  s ee n   i n   Fig u r e  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 e  s ee n   in   F ig u r e  6 .           Fig u r e  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 e  5 .   Vis u al izatio n   tr ee   f r o m   NJ   So f t w ar e           Fig u r e  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 e  t h r ee   i m a g es  ca n   b e  s ee n   th a t  th e  v is u aliza t io n   o f   th e  tr ee   in   d i f f er e n t  p r o g r am s   h as  t h e   s a m e  s h ap e.   I n   ad d itio n   to   t h e   tr ee   s h ap e,   t h e  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 e  in   th e  s a m e  lo ca tio n .   I n   Fi g u r e  4   a n d   5 ,   it   is   k n o w n   t h at  n o d e  n u m b er   f iv e  r ep r ese n ts   th e   n e w   n o d e  f r o m   t h e  m er g i n g   o f   n o d e  s eq 1   an d   n o d e   s eq 2 .   T h e s e  th r ee   p o in ts   s h o w   t h e  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 e  u s i n g   Op en MP   o n   th e  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 e  u s in g   4   th r ea d s   o n   4   co r es  co m p u ter   n o d e  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 e  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 e  Alig n m ent   A t  t h i s   s ta g e,   th e  f i v e  p air w i s e  alig n m en t  i m p le m e n tatio n   s ce n ar io s   w il l  b e  co m p ar ed   u s i n g   th e  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 e  b est  s ce n ar io s .   T h e  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 e  v ar i ab le  w ill  b e  ch o s en   o n e  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 e  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 e  7 ,   it  c an   b e  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 t  co m p lete  t h e  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 e  b o th   s ce n ar io s   p ar allelize   a  p ar t  th at  h a s   d ata  d ep en d en c y   an d   it  r eq u ir es  a  lo t  o f   s y n c h r o n izatio n   th a t  o v er lo ad s   th e   o p er atin g   s y s te m .     I n   Fig u r e  7   is   also   k n o w n   th a t  th e  p u r eOp en MP   s ce n ar io   h as  a  m u c h   b etter   s p ee d   u p   im p r o v e m en t  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 e  p u r eO p en MP   s ce n ar io   is   ch o s e n   as t h e  b est s ce n ar io .           Fig u r e  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 e  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 e  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 e  r esu lt  o f   t h e  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 e  s ee n   in   Fig u r e  8 .   I m p r o v e m e n t  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 e  t h e  lo a d   o n   ea ch   th r ea d   is   t o o   s m all  i n   th e  n u m b er   o f   s e q u en ce s   2 0   an d   6 0 .   T h e  co m p u tatio n   ti m e  b ec o m e s   lo n g er   th an   t h e  s eq u en t ial   i m p le m en ta tio n   d u e  to   t h e  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 e  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 e  c h ar ac ter is tics   a n d   r o b u s t n es s   o f   t h e  al g o r ith m .   F ig u r e  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 e  d ata.   T h e  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 e  al g o r ith m   p air w is e  a lig n m e n t  w it h   t h e  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 e  t h e  p air w is e   ali g n m e n t  a lg o r i th m   h as   a  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 t  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 t  co n tr ib u te  to   th e  co m b i n ed   al g o r ith m .   I f   th e  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 e  s p ee d   u p   o n   th e  v ar iatio n   o f   Sh o r t L ar g e   w il l  d ec r ea s e  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 e  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 e  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   a  lar g e   n u m b er   o f   s eq u e n ce s .           Fig u r e  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 e  9 .   C o m p ar is o n   o f   s p ee d   u p   in   p air w i s e  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 e  b es t  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 e  th e   p air w i s e  al ig n m en t  a n d   n e ig h b o r - j o in in g   al g o r ith m s .   T h e  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 e  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 e  au th o r s   w o u ld   lik e  to   th a n k   t h e  Ag e n c y   f o r   A s s es s m en t  an d   A p p licatio n   o f   T ec h n o lo g y   ( B P PT )   f o r   th e  s c h o lar s h ip   f u n d   an d   t h e  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 P  stra teg y   fo r   b io lo g ica l  mu l ti p le  se q u e n c e   a li g n me n t  wit h   DIAL IGN - T X  in   h e ter o g e n e o u s  mu lt ico re   c lu ste rs .   IEE E  In t e rn a ti o n a l  P a ra ll e l  &   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 s  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 t  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 s  a n d   we ig h t  m a tri x   c h o ice .   Nu c leic   Acid s  Res .   1 9 9 4 ;  2 2 ( 2 2 ) :  4 6 7 3 - 4 6 8 0 .   [3 ]     L i  KB.  Clu sta lW - M P I:  Cl u sta lW   a n a ly sis  u sin g   p a ra ll e l  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 t  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 l  o f  E lec trica l  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 t  B,   Do u g las   L M .   Pa r a ll e l  re c o n str u c ti o n   o f  n e ig h b o r - jo in i n g   tre e s  fo r  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 s  o f   2 3 r d   IEE E  In ter n a ti o n a l  P a ra ll e l  &   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 l  m e th o d   f o r  e v o lu ti o n a ry   tree   c o n str u c ti o n .   Co mp u ter s  a n d   El e c trica l  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 r  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 l  p a ir w i se   a li g n m e n t  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 l  o f  E lec trica l  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 r  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 l  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 l  m e th o d   a p p li c a b le  to   se a rc h   f o r  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 f  tw o   p ro tein s.   J o u r n a l   o f  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 l  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 l  d a n   Ra p a t  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 r  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 r  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 r  J o i n i n g .   P ro c e e d in g s  o f   8 th   in t e r n a ti o n a l  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.