《基于多核架构的生物序列比对算法的设计与实现重庆邮电大学》由会员分享，可在线阅读，更多相关《基于多核架构的生物序列比对算法的设计与实现重庆邮电大学（56页珍藏版）》请在金锄头文库上搜索。
1、重庆邮电大学硕士论文摘要摘要生物信息学是计算技术在管理和分析生物信息数据上的应用。在生物信息学中，序列比对是一种计算排列D N A 、R N A 和蛋白质序列的方法，此方法用来划分序列间可能与功能、结构或进化关系有关的相似区域。序列的关系是可以量化的，并且它们之间的相似度也是可以评估的。这种相似度可以用来鉴定一个新发现的序列和一个已知基因之间的进化关系。如果相似度低，除非收集到足够的证据，否则它们的进化关系只能是待定的。序列比对已经成为分子生物学中的一项常规操作。今天，序列可以很容易获得，但是去比对已经得到的序列仍然是分子生物学中复杂的一部分。过去的几十年中，一系列的序列比对程序已经出现。它们
2、中的大多数采用了基于动态规划思想的算法，这个算法由N e e d l e m a n 和W u n s c h 于1 9 7 0 年提出。N e e d l e m a n W u n s c h 算法基于动态规划思想。这个算法的时间复杂度是o ( n 2 ) ，这里的1 1 是输入序列的长度。因为该算法需要执行与序列长度乘积规模相当的一系列操作，所以其计算耗费是相当高的。为了降低算法执行所需要的时间，我们很自然地考虑到这个算法的并行化设计。由于多核架构上编程简易且功能强大，因此适合用作高性能计算。进一步说，此架构有很好的价格性能比率。很多任务都可以基于多核平台执行，并且执行效率显著提升。这篇
3、论文工作的主要动机就是利用现有普通的多核架构的巨大的计算能力，实现一个序列比对的高效解决方案。0 p e n M P 是一个可移植，可扩展的模型，它给基于共享存储器编程的程序员提供一个简单且灵活的接口，以此来开发从桌面到超级计算机平台都适用的并行程序。本文研究了生物序列比对算法及其并行化，主要研究内容如下：1 介绍了多核架构以及O p e n M P 编程模型的一些基本知识。阐述了多核架构的特点，O p e n M P 模型的相关信息。2 对双序列比对算法做了分析，指出了其优点与不足。并用D i a g o n a lW a v e f r o n t算法结合0 p e n M P 模型的特性
4、对N e e d l e m a n - W u n s c h 算法进行了并行化。3 在N e e d l e m a n - W u n s c h 算法并行化的基础上，研究了基于N e e d l e m a n - W u n s c h算法的C l u s t a l 算法的并行化。4 通过比较N e e d l e m a n - W u n s c h 算法和C l u s t a l 算法在单线程和多核系统下多线程并行执行的耗费时间，我们发现当计算的比对序列较长以及比对序列较多时，计算速度有较明显的上升。实验的结果证实了序列比对算法完全可以因并行计算而获得性能提升。实验结果同样
5、说明了这样一个事实：要高效利用多核系统，并行执行重庆邮电大学硕士论文摘要线程的数量以及任务的分解是非常重要的。关键字：生物信息学，序列比对，N e H x l l e m a n - W u n s c h ，多核，研咖H重庆邮电大学硕士论文A b s t r a c tA b s t r a c tB i o i n f o r m a t i c si st h ea p p l i c a t i o no fc o m p u t a t i o n a lt e c h n i q u e st ot h em a n a g e m e n ta n da n a l y s i
6、so fb i o l o g i c a li n f o r m a t i o n I nb i o i n f o r m a t i c s ，as e q u e n c ea l i g n m e n ti saw a yo fa r r a n g i n gt h es e q u e n c e so fD N A , R N A , o rp r o t e i nt oc l a s s i f yr e g i o n so fr e s e m b l a n c et h a tm a yb et h eo u t c o m eo ff u n c t i o
7、 n a l ，s t r u c t u r a l ，o re v o l u t i o n a r yr e l a t i o n s h i p sb e t w e e nt h es e q u e n c e s T h er e l a t i o n s h i pb e t w e e ns e q u e n c e sC a nb eq u a n t i f i e da n dt h e i rs i m i l a r i t yc 觚b ea s s e s s e d T h i ss i m i l a r i t yc a nb eu s e dt o
8、i d e n t i f yt h ee v o l u t i o n a r yr e l a t i o n s h i pb e t w e e nan e w l yd e t e r m i n e ds e q u e n c ea n dak n o w ng c n ef a m i l y W h e nt h ed e g r e eo fs i m i l a r i t yi sl o w ，t h er e l a t i o n s h i pm u s tr e m a i nu n k n o w n , u n t i le v i d e n c eh
9、a sb e e ng a t h e r e d T h i ss e q u e n c ea l i g n m e n th a sb e c o m ear o u t i n ep r o c e d u r ei nM o l e c u l a rB i o l o g y T o d a y ,s e q u e n c e sc a nb eo b t a i n e de a s i l y , b u ta l i g n i n gt h es e q u e n c e sr e m a i n sac o m p l i c a t e da s p e c to
10、 fc o m p a r a t i v em o l e c u l a rb i o l o g y An u m b e ro fn e wp r o g r a m sf o rc o m p u t i n gS e q u e n c eA l i g n m e n th a v eb e e nd e v e l o p e di nt h el a s td e c a d e s T h ea l g o r i t h mu s e db ym o s ts e q u e n c ea l i g n m e n tt o o l si st h ed y n a m
11、 i cp r o g r a m m i n ga l g o r i t h mi n t r o d u c e db yN e e d l e m a na n dW u n s c hi n19 7 0 N e e d l e m a n W u n s c ha l g o r i t h mi sb a s e do nad y n a m i cp r o g r a m m i n ga p p r o a c h T h i sa l g o r i t h mh a sat i m ec o m p l e x i t yo fO ( n 2 ) ，w h e r eni
12、 st h el e n g t ho ft h em p u ts e q u e n c e T h ec o m p u t a t i o n a lc o s tr e q u i r e df o ru s i n gd y n a m i cp r o g r a m m i n gi sv e r yh i g ha si tr e q u i r e san u m b e ro fo p e r a t i o n st h a ta r ep r o p o r t i o n a lt ot h ep r o d u c to ft h el e n g t h so
13、ft h es e q u e n c e s T h u sp a r a l l e l i z i n gt h ea l g o r i t h mi st h en a t u r a ls t e pf o r w a r dt or e d u c et h er u n n i n gt i m er e q u i r e d M u l t i C o r ea r c h i t e c t u r e sc a nb eu s e df o rh i 【g hp e r f o r m a n c ec o m p u t i n ga st h e yf a c i
14、l i t a t ee n h a n c e dp r o g r a m m a b i l i t y F u r t h e r m o r e , t h e yp r o v i d eg o o dp r i c e p e r f o r m a n c er a t i o Aw i d er a n g eo ft a s k s a r ec o m p u t a b l eo nM u l t i C o r ea r c h i t e c t u r e sa n dt h e i rc o m p u t a t i o n a lp o w e rh a s
15、i m p r o v e ds i g n i f i c a n t l y T h em a i nm o t i v a t i o no fo u rw o r ki st oe x p l o i tt h ei n l m e n s oc o m p u t a ：t i o n a lp o w e ro fc o m m o n l ya v m l a b l eM u l t i C o r ea r c h i t e c t u r e s ，t od e v e l o pa l le f f i c i e n ts o l u t i o nf o rP a
16、i r - W i s eS e q u e n c eA l i g n m e n t O p e n M Pi sap o r t a b l e , s c a l a b l em o d e lt h a tg i v e ss h a r e d - m e m o r yp a r a l l e lp r o g r a m m e r sas i m p l ea n df l e x i b l ei n t e r f a c ef o rd e v e l o p i n gp a r a l l e la p p l i c a t i o n sf o rp l a t f o r m sr a n g i n gf i o mt h ed e s k t o pt ot h es u p c r c o m p u t c r T h i sp a p e rs t u d i e sa n dp a r a l l e l i z e sb i o s e q u e n c ea l i
