（计算机应用技术专业论文）遗传多态性检测中组合优化问题的研究.pdf

摘要 遗传多态性检测是进行遗传多态性研究的关键环节。近年来， 为降低检测成本，以计算手段为辅助的多态性检测已得到广泛应用， 同时，在该研究领域中出现了一系列以提高检测效率和降低检测成 本为目的的组合优化问题。本文主要研究个体单体型检测问题、基 于连锁不平衡的多种群标签s n p s 选择问题及多元聚合酶链反应引 物集设计问题。 本文针对个体单体型检测问题的带权最少字符修改模型，提出 一种启发式算法h a w 。该算法先对每条s n p 片段计算其全局兼容 集，再选出包含片段数最多且交集为空的两个全局兼容集以生成一 对初始单体型，最后通过剩余片段对其扩充完成重建。大量实验结 果表明h a w 算法能快速求解该模型，并获得较目前求解该模型的 算法更高的单体型重建率。 针对个体单体型检测问题的最少片段删除模型，本文提出一种粒 子群优化算法p s o m f r 。该算法利用二进制编码粒子，并重新定义 了粒子位置和速度之间的运算操作。由于利用了s n p 位点杂合率较 低的特性，该算法所引入的编码方式较短，能产生一个较小的解空 间，从而快速地获得好的结果。实验结果表明，p s o m f r 算法是一 种求解该模型的有效方法，能在较短时间内获得较高的单体型重建 率，并得到较f a s th a r e 算法更高的重建率。 针对个体单体型检测问题的最少错误更正模型，本文深入分析 了以往算法在求解该问题时遗失最优解的原因，提出种生成小规 模优化解集合的新研究思路。通过引入较短的染色体编码方式和一 种利用片段信息来修正染色体的重组算子，提出求解最少错误更正 模型的单亲遗传算法p g a m e c 。实验结果表明p g a m e c 算法能有 效求解该模型，在更短的运行时间内获得较以往求解该模型的算法 更高的单体型重建率。进一步，将优化解集合的思想运用于 p g a m e c 算法，提出i p g a m e c 算法。实验结果显示优化解集合的 引入能有效避免最优解的遗失，从而进一步提高单体型的重建率。 针对基于连锁不平衡的多种群标签s n p s 选择问题，给出其形式 化描述，并通过对集合覆盖问题在多项式时间内的归约证明其是n - p 难的。进一步，本文提出一种求解该问题的贪婪算法m p t a g g i n g ， 该算法在每次迭代过程中选择1 个或2 个标签s n p s 。实验结果表明 m p - t a g g i n g 算法能有效求解该问题，并能够找到较以往算法更少的 标签s n p s 。 针对多元聚合酶链反应引物集设计问题，提出一种多约束最小 引物集选择问题的数学模型。针对该模型，本文提出贪婪算法m g ， 并基于n 1 g 算法设计一种新颖的重组算子，从而给出求解该模型的单 亲遗传算法m g p g a 。实验结果表明m g p g a 算法在满足多约束条 件下能获得较以往求解算法更小的引物集，为m p p c r 引物设计提供 了一种有效的解决方法。 本文对遗传多态性检测中三类典型的组合优化问题进行研究， 并提出了有效的求解算法。这些研究工作能有效地提高遗传多态性 检测的工作效率，并降低其成本。 关键词遗传多态性，组合优化，单体型，标签单核苷酸多态性，引 物集 a bs t r a c t t h ed e t e c t i o no fg e n e t i cd i v e r s i t i e si sak e ys t e pf o ri n v e s t i g a t i n g g e n e t i cd i v e r s i t i e s i nr e c e n ty e a r s ，t h em e t h o d sa s s i s t e db yc o m p u t a t i o n f o rd e t e c t i n gg e n e t i cd i v e r s i t i e sh a v eb e e na p p l i e de x t e n s i v e l y t h e r e h a v eo c c u r r e das e r i e so fc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m si nt h e r e s e a r c hf i e l d ，w h i c hf o c u so ni m p r o v i n gd e t e c t i o n e f f i c i e n c y a n d d e c r e a s i n g d e t e c t i o nc o s t i nt h i sd i s s e r t a t i o n ，t h r e eo ft h e s e c o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sa r es t u d i e d ，w h i c ha r ei n d i v i d u a l h a p l o t y p i n gp r o b l e m ，l i n k a g ed i s e q u i l i b r i u m ( l d ) t a gs n p ss e l e c t i o n p r o b l e m i n m u l t i p l ep o p u l a t i o n s a n dm u l t i p l e x p o l y m e r a s e c h a i n r e a c t i o np r i m e rs e ts e l e c t i o np r o b l e m b a s e do nt h ew e i g h t e dm i n i m u ml e t t e rf l i p sm o d e lo ft h ei n d i v i d u a l h a p l o t y p i n gp r o b l e m ，ah e u r i s t i ca l g o r i t h mh a wi sp r o p o s e d t h e a l g o r i t h mc o m p u t e sag l o b a la g r e e a b l es e tf o re a c hs n pf r a g m e n t ，a n d c h o o s e st w og l o b a la g r e e a b l es e t si n c l u d i n gt h em o s tf r a g m e n t s ( t h e i n t e r s e c t i o no ft h et w os e t si sn u l l ) t oc o n s t r u c ta p a i ro fi n i t i a lh a p l o t y p e s ， a n dt h ef i n a lp a i ro f h a p l o t y p e sa r eb u i l tg r a d u a l l yb ye x t e n d i n gt h ei n i t i a l o n e sw i t ht h er e s tf r a g m e n t s e x t e n s i v ee x p e r i m e n t a lr e s u l t si n d i c a t et h a t h a wa l g o r i t h mc a ns o l v et h em o d e le f f i c i e n t l y , a n dg e t s h i g h e r r e c o n s t r u c t i o nr a t et h a np r e v i o u s l yp r e s e n t e da l g o r i t h m b a s e do nt h em i n i m u mf r a g m e n tr e m o v a lm o d e lo ft h ei n d i v i d u a l h a p l o t y p i n gp r o b l e m ，ap a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mp s o - m f r i sp r e s e n t e d i nt h i sa l g o r i t h m ，p a r t i c l e sa r ed e n o t e db yb i n a r yc o d e s ，a n d t h ec o m p u t a t i o no p e r a t i o n sb e t w e e np a r t i c l ep o s i t i o na n dv e l o c i t ya r e r e d e f i n e d b e c a u s eak i n do fs h o r t p a r t i c l e c o d ei s d e s i g n e df o r p s o - m f ra l g o r i t h mb y t a k i n ga d v a n t a g e o ft h el o wh e t e r o z y g o u s f r e q u e n c i e so fs i n g l en u c l e o t i d ep o l y m o r p h i s m s ( s n p s ) ，p s o - m f r a l g o r i t h mc a ng e n e r a t eas m a l ls o l u t i o ns p a c e ，w h i c hm a k e si tg e tag o o d s o l u t i o na n db ef a s t e x p e r i m e n t sr e s u l t ss h o wt h a tp s o m f ra l g o r i t h m i se f f e c t i v ef o r s o l v i n gt h em o d e l i t c a no b t a i n r e l a t i v e l yh i g h r e c o n s t r u c t i o nr a t ei nas h o r tt i m e ，a n d g e th i g h e rr e c o n s t r u c t i o nr a t et h a n f a s th a r ea l g o r i t h m b a s e do nt h em i n i m u me r r o rc o r r e c t i o nm o d e lo ft h ei n d i v i d u a l h a p l o t y p i n gp r o b l e m ，at h o r o u g ha n a l y s i si sg i v e no nt h er e a s o n sf o rh o w t h er e a lb e s tr e s u l tc a nb el o s td u r i n gah a p l o t y p i n gp r o c e s s w ep r o p o s ea n e wi d e at or e d u c et h ep r o b a b i l i t yo f l o s i n gt h eb e s tr e s u l tb yg e n e r a t i n g as m a l ls e to fo p t i m a lr e s u l t s ，i n s t e a do fas i n g l e o p t i m a lr e s u l t a p a r t h e n o g e n e t i ca l g o r i t h mp g a m e ci sp r e s e n t e dt os o l v et h em o d e l i n t h i sa l g o r i t h m ，ak i n do fs h o r tp a r t i c l ec o d ei s a d o p t e d ，a n dan o v e l r e c o m b i n a t i o n o p e r a t o r i s d e s i g n e d ，w h i c hm a k e sf u l lu s eo ft h e i n f o r m a t i o ni n f r a g m e n t st oa d ju s tt h ec h r o m o s o m e ss t e pb ys t e p e x p e r i m e n t a lr e s u l t si n d i c a t et h a tp g a - m e ca l g o r i t h mc a ns o l v et h e m o d e le f f e c t i v e l y , a n dg e th i g h e rr e c o n s t r u c t i o nr a t e h a p l o t y p e sw i t h s h o r t e rr u n n i n gt i m et h a np r e v i o u sw o r k i na d d i t i o n ，a n i m p r o v e d a l g o r i t h mi p g a - m e ci sp r o p o s e db ya p p l y i n gt h ei d e ao fg e n e r a t i n ga s m a l ls e to f o p t i m a lr e s u l t st oa l g o r i t h mp g a m e c e x p e r i m e n t a lr e s u l t s s h o wt h a tt h ei d e ao f g e n e r a t i n ga s m a l lo p t i m a lr e s u l ts e tm a y e f f e c t i v e l y a v o i dl o s i n gt h er e a lb e s tr e s u l ta n di m p r o v et h er e c o n s t r u c t i o nr a t e f u r t h e r i nt h i sd i s s e r t a t i o n ，am a t h e m a t i c a lm o d e lo ft h em i n i m u ml dt a g s n p ss e l e c t i o np r o b l e mi nm u l t i p l ep o p u l a t i o n s ( m t s m p ) i sf o r m u l a t e d ， a n dw h i c hi sp r o v e dt ob en p h a r db yr e d u c i n gf r o ms e tc o v e rp r o b l e m i n p o l y n o m i a lt i m e ag r e e d ya l g o r i t h mm p t a g g i n gi sp r o p o s e df o r s o l v i n gt h i sp r o b l e m t h ea l g o r i t h ms e l e c t se i t h e rt w ot a gs n p so ro n e s n pa te a c hi t e r a t i o n e x p e r i m e n t a lr e s u l t si n d i c a t et h a t m p t a g g i n g a l g o r i t h mh a sv e r yh i g he f f i c i e n c yf o rs o l v i n gt h i sp r o b l e m ，i tc a nf i n d f e w e rt a gs n p st h a np r e v i o u sa l g o r i t h m t h ep r o b l e mo fd e s i g n i n gm u l t i p l e xp o l y m e r a s ec h a i n r e a c t i o n p r i m e rs e ti ss t u d i e di nt h i sd i s s e r t a t i o n am a t h e m a t i c a lm o d e li s p r e s e n t e df o rt h em i n i m u mp r i m e rs e ts e l e c t i o np r o b l e mw i t hm u l t i p l e i v c o n s t r a i n t s ag r e e d ya l g o r i t h mm gi sp r o p o s e df o rs o l v i n gt h i sm o d e l i na d d i t i o n b yi n t r o d u c i n gan o v e lr e c o m b i n a t i o no p e r a t o rb a s e do nm g a l g o r i t h m ，ap a i r t h e n o g e n e t i ca l g o r i t h mm g p g ai sd e v e l o p e dt os o l v e t h em o d e l e x p e r i m e n t a lr e s u l t ss h o wt h a tm g - p g aa l g o r i t h mc a nn o t o n l yf i n das m a l l e rp r i m e rs e tt h a np r e v i o u sw o r k ，b u ta l s os a t i s f y m u l t i p l eb i o l o g i c a l c o n s t r a i n t s t h ep r e s e n t e dm o d e la n da l g o r i t h m p r o v i d eap r a c t i c a ls o l u t i o nf o rm p p c rp r i m e r s e td e s i g n i nt h i sp a p e r ，s e v e r a le f f e c t i v ea l g o r i t h m sa lep r e s e n t e df o rs o l v i n g t h r e et y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m sf o rd e t e c t i n gg e n e t i c d i v e r s i t i e s t h e s ep r e s e n t e d a l g o r i t h m sw i l lb eh e l p f u lt oi m p r o v e d e t e c t i o ne f f i c i e n c ya n dd e c r e a s ed e t e c t i o nc o s t k e yw o r d sg e n e t i cd i v e r s i t y , c o m b i n a t o r i a lo p t i m i z a t i o n ，h a p l o t y p e ， t a gs i n g l en u c l e o t i d ep o l y m o r p h i s m s ( t a gs n p s ) ，p r i m e rs e t v 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：墨遗亟日期：二竺l 年上月上日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论 文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论文； 学校可根据国家或湖南省有关部门规定送交学位论文。 作者虢进轧翩警名：五粤嗍堕年生月l 日 博士学位论文第一章绪论 1 1 研究背景 第一章绪论 在人类这个大家庭里，为什么会有不同肤色的人种? 为什么在人之间进行 器官移植时仍然有排异反应? 为什么男性和女性的生理和心理以及行为有很多 很多差异? 为什么欧洲人容易患结肠息肉囊肿，但不易患乙型肝炎，而中国人 不容易患结肠息肉囊肿，但容易患乙型肝炎? 为什么我国的汉族人容易患钩端 螺旋体病，但是黎族人则不得钩端螺旋体病【i l ? 答案只有一个，人类是一个具有 多样性的群体。从遗传上说，这是因为人类基因组具有高度变异的特性，不同 个体( 除了同卵双胞胎外) 的基因组不完全相同，即基因具有“多样性”，也称 为遗传多样性。 1 9 9 1 年，卡沃里斯福札( c a v a l l i s f o r z a ) 等一些人类遗传学家和分子生物学 家开始建议尽快地对全球或地理区域人类基因组的多样性进行研究，并建立了 人类基因组多样性计划( h u m a ng e n o m ed i v e r s i t yp r o j e c t ，h g d p ) 1 2 ，3 】，基因组多 样性的研究对阐明不同人群和个体在疾病的易感性和抵抗性方面的差异有着重 要意义。例如h o r i k a w a 等根据单核苷酸多态性( s i n g l en u c l e o t i d e p o l y m o r p h i s m s ，s n p s ) 进行关联分析，在墨西哥裔美国人中把2 型糖尿病基因定 位在2 号染色体长臂，并发现c a p n l 0 基因的3 个s n p s $ 1 2 型糖尿病相关1 4 j 。基因 的多样性取决于基因的多态性( 也称为遗传多态性) ，基因多态性是整个生物医 学研究的组成部分，它对复杂疾病的发生发展过程的基因定位、疾病发生的分 子遗传机理、环境因子易感基因的检出、药物设计和用药均起着举足轻重的作 用。 遗传多态性检测是进行遗传多态性研究的关键环节，高效经济的检测方法 将对研究工作起到重要的推动作用。由于利用计算手段辅助多态性检测可以有 效克服人类基因组数据的海量性及生物检测手段存在的低效、高成本等因素， 近些年利用计算手段辅助多态性检测问题得到了充分认可和广泛应用，同时也 产生了一系列以提高检测效率和降低检测成本为目的的组合优化问题。 博士学位论文第一章绪论 1 2 遗传和变异的相关知识 俗语说：“种瓜得瓜，种豆得豆；一母生九子，九子各异 。这形象地描述 了古人对遗传和变异的认识，世界上没有两个绝对相同的个体，包括孪生同胞 在内，这充分说明了遗传的稳定性是相对的，而变异是绝对的。生物的遗传与 变异是同一事物的两个方面，遗传可以发生变异，发生的变异可以遗传。 1 2 1 遗传的物质基础及遗传法则 当达尔文提出进化论时，尚不知道生物界里有一条遗传定律的存在。后来 遗传学之父，奥地利人孟德尔( m e n d e lgj ) 在18 6 5 年发表专著植物杂交实 验，提出从他8 年植物杂交实验结果中发现的遗传定律，原来生物每一个性状 都是通过遗传因子来传递的，遗传因子是一些独立的遗传单位。1 9 0 9 年，丹麦 人约翰森( j o h a n n s e nwl ) 将孟德尔提出的“遗传因子 改称为后来广为流传 的“基因”( g e n e ) 。1 9 1 0 年摩尔根( m o r g a nth ) 等创立了连锁定律，1 9 4 4 年 艾弗里( a v e r yot ) 确定遗传物质为脱氧核糖核酸( d e o x y r i b o n u c l e i ca c i d ， d n a ) ，1 9 5 3 年沃森( w a t s o njd ) 和克里克( c r i c kfhc ) 建立了d n a 分子的 双螺旋结构模型。至此人们普遍认为生命个体的遗传信息包含在细胞中全部 d n a 所构成的基因组中，生命的表型和其他性状是由基因组决定的。下面简要 介绍遗传的物质基础及遗传法则。 ( 1 ) 染色体 对于人类等真核生物，生命体的基本单位细胞( c e l l ) 中有细胞核 ( n u c l e u s ) ，在细胞核中有染色体( c h r o m o s o m e ) 。1 9 1 0 年摩尔根等创立连锁定 律的同时也证实了遗传信息( 基因) 在染色体上以线状排列。 染色体的化学成分主要是d n a 和蛋白质，在细胞发生有丝分裂时期容易 被碱性染料着色，因此而得名。染色体是遗传物质的主要载体，细胞中大部分 的d n a 在染色体上，染色体中d n a 含量稳定，是主要的遗传物质。 在无性繁殖物种中，生物体内所有细胞的染色体数目都一样。而在有性繁 殖物种中，生物体的体细胞染色体成对分布，称为二倍体。人类体细胞中含有 2 2 对常染色体，l 对性染色体。男性的性染色体对由x 和y 染色体构成( 如图 1 1 ) ，女性的性染色体由2 条x 染色体构成。在这2 3 对同源染色体的每一对中， 博士学位论文第一章绪论 一条来自于母亲，另一条来自于父亲。 在每一条染色单体中，一个d n a 分子像细长的丝带缠绕在组蛋白田i s t o n e ) 分子表面形成所谓的绳珠结构，然后在此基础上进一步形成了染色体的空间三 维结构，如图1 2 所示。 醇董蓦9 哆醇婶羞善 竹吁蟹吁- l 姊 i 。 固1 1 人类男胜体细胞染色体【5 】 廖莲 卜多 二! 困】2 染色体组成h ( 2 ) d n a 分子与基因 构成d n a 分子的基本单位是脱氧核苷酸( d e o l c y r i b o n u c l e o t i d e ) ，脱氧核苷 酸由磷酸( p h o s p h a t e ) 、脱氧核糖( d e o x y d b o s e ) 和碱基( b a s e ) 构成，其中碱 博士学位论文第章绪论 基有四种：腺嘌呤( a d e n i n e ，缩写为a ) 、鸟嘌呤( g u a n i n e ，缩写为g ) 、胞嘧 啶( c y t o s i n e ，缩写为c ) 和胸腺嘧啶( t h y m i n e ，缩写为1 ) ，由此脱氧核苷酸 可分为四种，分别用a 、0 、c 、t 表示。 图1 - 3d n a 赋螺旋结构m ( b ) ；= 嚣：嚣 二； 囤i - 4 碱基互补配对l ”：( a ) d n a 分子化学结构；c o ) d n a 分子碱基对序列 脱氧核苷酸之间通过3 。、5 - 磷酸二酯键相连形成脱氧核苷酸链，两条脱氧 核苷酸链平行但反向盘旋成规则的d n a 分子双螺旋结构，两条链之间通过互 补碱基配对连接在一起，其中a 与t 以2 个氢键相配对，c 与g 之间以3 玲氢 键配对这称为沃森一克里克( w a t s o n - c r i c k ) 碱基互补配对。d n a 的双螺旋结 构如图l 一3 所示，碱基互补配对如图1 _ 4 所示，其中图l _ 4 ( a ) 表示d n a 分子 的化学结构，图l _ 4 ( ”图表示对应于该分子的碱基对序列。在d n a 分子的化 博士学位论文第一章绪论 学结构图中，p 表示磷酸，d 表示脱氧核糖，a 、g 、c 和t 分别表示四种碱基， 一个d n a 单链开始于3 端( 脱氧核糖端) ，终止于5 端( 磷酸端) 。 d n a 分子的一级结构指d n a 分子中核苷酸的排列顺序，即核苷酸序列或 碱基序列，d n a 分子的多样性是由碱基排列顺序的多样性决定的。 现代遗传学认为，基因是指位于染色体的特定位置、编码特异的蛋白质或 r n a 的段核酸序列( 通常是d n a 序列) ，是遗传物质的结构和功能单位。对 于真核生物而言基因位于染色体上，并在染色体上呈线性排列。基因不仅可 以通过复制把遗传信息传递给下一代，还可以使遗传信息得到表达，也就是使 遗传信息以一定的方式反映到蛋白质的分子结构上，从而使后代表现出与亲代 相似的性状。基因组( g e n o m e ) 代表了一个生物细胞内的全部基因和染色体组 成。 r 3 1 分子生物学的中心法则 鬻潞蒸 to q m p ”硼贾“ 图1 5 分子生物学的中一。法则l ” 1 9 5 8 年，克单克提出了两个学| 兑，奠定了分子生物学的理论基础，第个 学说是“序列假i 兑”它认为一段核酸的特殊性完全由它的碱挂序列所决定，碱 孚一 博十学位论文 第一章绪论 基序列编码一个特定蛋白质的氨基酸序列，蛋白质的氨基酸序列决定了蛋白质 的三维结构。第二个学说是“中心法则，遗传信息只能从核酸传递给核酸，或 核酸传递给蛋白质，而不能从蛋白质传递给蛋白质，或从蛋白质传回核酸。后 来，沃森把“中心法则”更明确地表示为，遗传信息只能从d n a 传到r n a ， 再由r n a 传到蛋白质。分子生物学的中心法则( c e n t r a ld o g m ao fm o l e c u l a r b i o l o g y ) 如图1 5 所示，从“中心法则 可以看出，遗传信息的一般流动方向 是：遗传信息可以通过d n a 的自我复制( r e p l i c a t i o n ) 从d n a 流向d n a ，也 可以通过转录过程( t a n s c r i p t i o n ) 从d n a 流向r n a ，进而通过翻译过程 ( t r a n s l a t i o n ) 从r n a 流向蛋白质，最后通过具有空间结构的蛋白质完成细胞的 各项生命活动。 1 2 2 可遗传的变异 人类不同个体有不同的外貌和体格，对疾病有不同的抵抗能力，从遗传的 观点上说，这是因为不同个体的基因组并不完全相同。人类基因组包含2 3 对染 色体上的d n a 序列，总长度达到3 0 亿个碱基。不同个体的d n a 序列极为相 似，若将两个不同个体的同源染色体进行比较，在他们的d n a 序列上可以连 续数百个碱基都是相同的。最近的研究表明，在两个不同个体的同源染色体的 d n a 序列中，9 9 5 的碱基是相同的【1 0 1 ，其他0 5 不同的部分可能是短的d n a 片段的插入( i n s e r t i o n ) 、删除( d e l e t i o n ) 和单个碱基的差异，其中主要是缘于 单个碱基的差异。在同一物种中，如果这些遗传物质上的变化在群体中的发生 频率低于1 ，则称为变异( m u t a t i o n ) ；如果不小于l ，则称为多态性 ( p o l y m o r p h i s m ) ，多态性是一种可遗传的变异。下面简要介绍可遗传变异的有关 概念。 ( 1 ) 单核苷酸多态性( s i n g l en u c l e o t i d ep o l y m o r p h i s m ，s n p ) 单核苷酸多态性是最常见的一种遗传多态性，它是染色体基因组在单个核 苷酸碱基尺度上的变化( 这种变化在群体中的频率最少不小于1 ) 而引起的 d n a 序列多态性【l l j 4 1 。一个s n p 位点指的是在一个物种的基因组d n a 序列中 不同个体可能出现不同碱基的位置。在图1 - 6 中，第3 0 个碱基处是一个s n p 位点。虽然脱氧核苷酸碱基有四种，但s n p 通常只是二等位基因( b i a l l e l i c ) 的 变异，即只含两种等位基因型( 碱基对) 。 6 博士学位论文第一章绪论 人类个体中9 0 以上的多态现象都是单核苷酸多态性。s n p s 广泛分布于人 类基因组，平均每1 0 0 - - 3 0 0 个碱基中就有一个s n p t l 5 ，16 1 ，在整个人类基因组的 3 0 亿个碱基中，大约有一千万个常见的s n p s 17 1 ，所以s n p s 作为分子标记广泛 地应用于致病基因定位等后基因组研究之中。 g t c a t a g c a t t a t t a t t a t t a t t w j ( g ，c ) ， 吃( g ) = i ，若w i ( g ，c ) w o ( g ，c ) ，c = i ，2 ，棚( 2 4 ) i 一，否则 与办( 回对应的权重向量为觋( g ) = 砌i ( g ) ，w h 2 ( 6 3 ，w h 珂( 6 3 ，其中， 哦( g ) = 搿，：g w o ( g w 。( 蚴 搿，机( g 岬，c ) 一1 ，2 ，刀( 2 5 ) 0 ， 否则 这里n o ( g ，c ) 和w o ( g ，c ) 分别表示集合 g 【l ，c 】，g 2 ，c 】，g k ，c 】) 中 0 的个数及对应的权重和；同理h i ( g ，c ) 和w i ( g ，c ) 分别表示集合 g 1 ，叫， g 2 ，c 】，g k ，c 】) 中l 的个数及对应的权重和。权重和的计算方法如公 2 8 博士学位论文 第二章个体单体型检测问题的w m l f 模型和算法 式( 2 - 6 ) 和( 2 7 ) 所示。 w o ( g ，c ) = w g j ，c 】，j = l 2 ，k ( 2 6 ) g 【c l = o m ( g ，c ) = w g j ，c 】，j = l 2 ，k ( 2 - 7 ) g l c j = l 对于s n p 矩阵m 的一个行划分仁( g l ，a 2 ) ，h ( g 1 ) 和h ( g 2 ) 分别表示由 g l 和g 2 中的片段构建的单体型，带权的字符修改函数蹦尸) 的计算方法如公 式( 2 - 8 ) 所示。 ( p ) = d 2 ( h ( g t ) ，m i ，一】) ，f = 1 ，2 ，m ( 2 8 ) i = 1 彳i i ，j e g ， 若存在某个划分尸+ 满足f 舯) 吲尸) ，根据w m l f 模型的优化目标，表明划分 p 优于划分p 。 2 3h a w 算法 本章提出一种求解w m l f 模型的启发式算法h a w ，算法输入为一个所以 的s n p 矩阵从一个m n 的权重矩阵和参数f ，输出为一对长度为刀的单体 型h = ( h l ，h 2 ) 。 h a w 算法首先对矩阵m 和进行预处理，将矩阵m 中的行m g ，- 1 ( 卢l ， 2 ，聊) 按照l ( m i ，_ 】) 从小到大排序，同时将矩阵形中的行也做相应调 整以保持与m 的对应关系，删除矩阵m 和中的冗余信息以得到m x 的新 矩阵m 和矽。然后按照排序后的顺序为每条s n p 片段计算其局部兼容集o k i 、 冲突集n o k 和全局兼容集o k 2 。接着，算法假设若某个0 1 ( 2 集中包含的片段 数越多，根据该集合中片段重建的单体型则越长。基于这一启发式策略，算法 选中包含片段数最多且交集为空的两个o k 2 集以生成一对初始单体型，再通过 不断对其进行扩充，以得到对应于新矩阵m 的结果单体型h = ( 办( g 1 ) ， ( g 2 ) ) ， g l 和g 2 为矩阵m 的两个互不相交的片段子集。最后，对h 进行扩展，得到对 应于矩阵m 的结果单体型厅= ( l ，h 2 ) 。下面分别介绍算法设计中的关键步骤。 博士学位论文第二章个体单体型检测问题的w m l f 模型和算法 ( 1 ) 预处理 求解问题前，首先为矩阵帅的行m f ，_ 】( 卢l ，2 ，m ) 计算三( m f ，- 】) 和尺( m f ，1 ) 值，并将矩阵m 中的行按照三( m f ，_ 】) 值从小到大排序，令r l ，r 2 ， 为排序后的行，即满足f 可当且仅当( 哟三( 功( f ，产1 ，2 ，脚) 。同时，将 矩阵肿的行也做相应的调整以保持与蝴对应关系。 由于纯合位点对于单体型重建工作没有任何作用，为提高算法的运行效率， 可以将这些位点暂时删除，使其不参与运算。因为测序错误不可避免，所以当 大部分片段在某个位点上的值都相等时，则认为该位点为纯合位点。删除肿满 足条t 牛- f x m , c ) fg 等于o 或1 ，c = l ，以) 的列，这里f 设置为0 2 1 7 9 1 。若 被删除的列中大部分非空元素值为0 ，则称其为0 列，否则称为1 列。将所有满 足上述条件的列删除之后，某些行将变成空行( 元素值全为u ) ，它们对于重建 没有也任何作用，因此也将其删除。将肿被删除的元素所对应的权重元素从矩 阵中删除。得到的新矩阵记为m 。钿和。钿，m 中的行记为r l ，r 2 ，小。 下文为方便描述，仍用。开和w i 。刀表示新的s n p 矩阵和权重矩阵。 ( 2 ) 计算集合o k i 、i 纠卿o k 2 给定s n p 矩阵m 中的行乃( 卢l ，2 ，肌) ，局部兼容集o k l ( r f ) 定义为 那些行序小于厂f ，与n 至少有一个共同覆盖的s n p 位点，且与，j 兼容的行所构 成的集合，如公式( 2 9 ) 所示。冲突集n o k ( r f ) 定义为那些行序小于n ，与n 至少有一个共同覆盖的s n p 位点，且与n 冲突的行所构成的集合，如公式( 2 1 0 ) 所示。全局兼容集o k 2 ( r ，) 定义为那些行序小于等于n ，且与，f 兼容的行所构 成的集合，如公式( 2 1 1 ) 所示。按照行序n ( 卢l ，2 ，朋) 为矩阵m 中的 每一行计算集合o k i ( ) 、n o k ( ) 和o k 2 ( ) 。 o k l ( r i ) = 洲j l ( r 3 ，说，功2 0 ) n o k ( r i ) 2 ，= ，l j o ) o k 2 ( r , ) = r j u o k l ( r j ) u o k i ( j ) 一n o k ( r , ) ，j o k l ( r , ) ( 2 - 9 ) ( 2 1 0 ) ( 2 1 1 ) ( 3 ) 产生初始单体型 在第( 2 ) 步得到的所有o k 2 ( ) 集之中，选择包含片段数目最多且交集为 空的两个o k 2 ( ) 集，并将其作为g l 和g 2 ，其对应的权重矩阵为w g l 和w g 2 。 根据公式( 2 - 4 ) 和( 2 5 ) ，由g l 和g 2 中的片段构建出两条初始单体型h ( g 1 ) 和 3 0 博士学位论文第二章个体单体型检测问题的w m l f 模型和算法 办( g 2 ) ，相应地，其权重向量为w h ( g t ) 和w h ( c 2 ) 。 ( 4 ) 剩余片段分组 对矩阵m 中的行r i ( i = l ，2 ，m ) 进行分组，若萑g ug ：，则根据n 与单体型h ( g 1 ) 和h ( g 2 ) 的相似程度，判断将其放入片段集合g l 或g 2 中，即 如果d l ( r ，h ( g 1 ) ) d l 以，办( g 2 ) ) ，则将n 放入g l 中，否则将其放入g 2 中。 因此，厅( g ，) 和w h ( g t ) ( 1 = 1 ，2 ) 的构建是在剩余片段的分组过程中逐步完成的。 ( 5 ) 扩展结果 在预处理阶段，单体型中的某些s n p 位点被删掉了，因此最后需将这些已 被删掉的s n p 位点重新加回。对于单体型h ( g 1 ) 和办( g 2 ) ，如果某个已被删除 的s n p 位点为0 - p 0 ( 1 列) ，则将0 ( l ) 插回单体型h ( g t ) 和厅( g 2 ) 的相应位 置，以此得到扩展后的单体型h l 和垃。下面给出算法h a w 的详细步骤。 h a w 算法： i n p u t ： 一个m x n 的s n p 矩阵m 一个肌刀的权重矩阵形，参数， o u t p u t ：一对长度为玎的单体型 = ( l ，】f 1 2 ) s t e p1 f o rf = 1 。md o s t e p1 1 计算l ( m i ，_ 】) 和r ( m i ，_ 】) ； s t e p2 按照( m f ，- 】) 从小到大，对矩阵m 中的行排序，相应地调整矩 阵肜中的行以保持与m 的对应关系； s t e p3 删除矩阵m 中的冗余列和冗余行，得到新矩阵。刀和w i 圳 s t e p4 f o rf = 1 肌d