《有向基因组的反转和转位排序算法》由会员分享，可在线阅读，更多相关《有向基因组的反转和转位排序算法（54页珍藏版）》请在金锄头文库上搜索。
1、山东大学 硕士学位论文 有向基因组的反转和转位排序算法 姓名：刘光聪 申请学位级别：硕士 专业：计算机软件与理论 指导教师：朱大铭 20090405 山东大学硕士学位论文 摘要 随着快速测序技术的发展，基因组重组排序已经成为计算生物学的一个重要 研究领域。其研究的目标是寻找最短的重组操作序列，将一种基因组转变为另一 种基因组。基于分子生物学家的实验数据表明，基因组重组是生物进化的一种普 遍模式，也是衡量不同生物之间亲缘关系的一种重要手段。 存在三种典型的基因组重组操作：反转( r e v e r s a l ) 、转位( t r a n s p o s i t i o n ) 和移位 ( t
2、r a n s l o c a t i o n ) 。其中，反转与转位操作作用在单条染色体上，而移位操作则作用在 两条染色体上。 过去，人们主要关注于单一重组操作的基因组重组排序问题，而对于多种混 合重组操作的基因组重组排序问题的研究则相对较为缓慢。目前，对于无符号排 列的反转和转位排序问题，娄晓文和朱大铭给出了一个2 2 5 近似度的算法；对于 有向基因组的反转和转位排序问题，H a r t m a n 和S h a r a n 给出了一个1 5 近似度的算 法。 本文首先讨论了经典的有向基因组的反转和转位排序问题，并介绍了H a r t m a n 的1 5 近似度算法。此外，本文考虑重组
3、操作的所花费的费用，引入了有向基因组 重组排序的最小权重问题。其目标为求解花费最少费用的重组操作序列，使一个 基因组转变成另一个基因组。对于该问题，本文给出了一个1 5 后近似度的算法。 本文的创新点主要有4 个： 1 考虑了重组操作的所花费的费用，提出了有向基因组反转和转位排序的最 小权重问题，并分析了该问题的背景和研究价值； 2 对于该问题，证明了一个下界； 3 基于这个下界，给出了该问题的一个1 5 后近似度的算法，其中k 是一个常 数，且k 之1 ； 4 给出了有向基因组反转和转位排序问题的1 5 近似度算法和有向基因组反 转和转位排序的最小权重问题的1 5 露近似度算法的C + +
4、实现。 关键字：基因组重组；反转；转位；反转位：双反转；近似算法 山东大学硕士学位论文 A B S T R A C T W i t ht h ed e v e l o p m e n to ff a s ts e q u e n c i n gt e c h n i q u e s ，t h ep r o b l e mo fs o r t i n gb y g e n o m e sr e a r r a n g e m e n t sh a sb e c o m ea ni m p o r t a n tr e s e a r c ha r e ao fc o m p u t a t i
5、o n a l b i o l o g ya n db i o i n f o r m a t i c s T h eg o a li s t of i n dt h es h o r t e s ts e q u e n c eo fg e n o m e a r r a n g e m e n t so p e r a t i o n st h a tt r a n s f o r mo n eg e n o m ei n t oa n o t h e r B a s e do ne x p e r i m e n t t a ld a t aa c c u m u l a t e db
6、Ym o l e c u l a rb i o l o g y ，i tp r o v e dt h a tg e n o m e sr e a r r a n g e m e n ti sa c o m m o nm o d ef o rb i o l o g i c a le v o l u t i o n ，a n di sv i e w e da sab e t t e re s t i m a t i o no ft h e a f f i n i t yr e l a t i o n sa m o n gs p e c i e s T h e r ea r et h r e ec
7、l a s s i c a lg e n o m e sr e a r r a n g e m e n t so p e r a t i o n s ：r e v e r s a l ，t r a n s p o s i t i o na n dt r a n s l o c a t i o n R e v e r s a la n dt r a n s p o s i t i o no p e r a t i o n sa l w a y sa c to n o n ec h r o m o - s o m e ，w h i l eat r a n s l o c a t i o no p
8、e r a t i o na c t so nt w oc h r o m o s o m e s I nt h ep a s t ，p e o p l em a i n l yp a i da t t e n t i o nt ot h eg e n o m e sr e a r r a n g e m e n t si n v o l v i n g s i n g l er e a r r a n g e m e n to p e r a t i o n ；b u tt h er e s e a r c ho ng e n o m e sr e a r r a n g e m e n t
9、 ss o r t i n gb y c o m b i n e dr e a r r a n g e m e n to p e r a t i o n sW a sr e l a t i v e l ys l o w R e c e n t l y ，f o rt h ep r o b l e mo f s o r t i n gu n s i g n e dg e n o m e sb yr e v e r s a l sa n dt r a n s p o s i t i o n s ，X i a o w e nL o ua n dD a r n i n g Z h ug a v ea2
10、 2 5 - a p p r o x i m a t i o na l g o r i t h m ；f o rt h ep r o b l e mo fs o r t i n gs i g n e dg e n o m e s b yr e v e r s a l sa n dt r a n s p o s i t i o n ，H a r t m a na n dS h a r a ng a v ea1 5 一a p p r o x i m a t i o na l g o r i t h m I nt h i sp a p e r ，w ef i r s t l yd i s c u s
11、 st h ep r o b l e mo fs o r t i n gs i g n e dg e n o m e sb yr e v e r s a l s a n dt r a n s p o s i t i o n s ，a n di n t r o d u c et h eH a r t m a n S1 5 一a p p r o x i m a t i o na l g o r i t h mC o n s i d e r - i n gt h ec o s to ft h er e a r r a n g e m e n t so p e r a t i o n ，w ea l
12、s oi n t o r d u c ean e wp r o b l e m , c a l l e d m i n i m a lw e i g h to fs o r t i n gs i g n e dg e n o m e sb yr e v e r s a l sa n dt r a n s p o s i t i o n s ，a n dt h eg o a l i st oc a l c u l a t et h el e a s tc o s to fg e n o m er e a r r a n g e m e n t so p e r a t i o n st h a
13、tt r a n s f o r mo n e g e n o m ei n t oa n o t h e r I nt h i sp a p e r , w eg i v ea1 5 k - a p p r o x i m a t i o na l g o r i t h mf o rt h i s p r o b l e m T h e r ea lef o u rc r e a t i v ep o i n t si nt h i sp a p e r 1 W ec o n s i d e rt h ec o s to ft h er e a r r a n g e m e n t so
14、 p e r a t i o n ，a n di n t r o d u c ean e w p r o b l e m , c a l l e dm i n i m a lw e i g h to fs o r t i n gs i g n e dg e n o m e sb yr e v e r s a l sa n d t r a n s p o s i t i o n s ，a n ds h o wi t sb a c k g r o u da n dr e s e a r c hv a l u e 2 W e p r o v ean e w l o w e rb o u n df o
15、 rt h i sp r o b l e m 3 B a s e do nt h i sl o w e rb o u n d ，w eg i v ea1 5 k - a p p r o x i m a t i o na l g o r i t h mf o rt h i s p r o b l e m I I 山东大学硕士学位论文 4 W eg i v eaC + + i m p l e m e n to ft h e1 5 - a p p x i t i o na l g o r i t h mf o rs o r t i n gs i g n e d g e n o m e sb yr e
16、 v e r s a l sa n dt r a n s p o s i t i o n sa n dt h e1 5 k - a p p s o x i m a t i o na l g o r i t h m o fm i n i m a lw e i g h tf o rs o r t i n gs i g n e dg e n o m e sb yr e v e r s a l sa n dt r a n s p o s i t i o n s K e y w o r d s ：G e n o m e sR e a r r a n g e m e n t ；R e v e r s a l ；T r a n s p o s i t i o n ；T r a n s r e v e r s a l ； R e v r e v ；A p p r o x i m a t i o nA l g o r i t h m H I 原创性声明和关于论文使用授权的说明 原创性声明 本人郑重声明：所呈交
