（计算机软件与理论专业论文）单体分型和单体型频率估计：复杂性及算法.pdf

摘要 计算机和网络技术的飞速发展，为分子生物学研究提供了新的强大手段。单体型信 息因其在医学特别是遗传疾病研究方面具有重要意义，引起生物与医学工作者的极大关 注。但绝大多数所研究的生物个体，包括人类自身，都是双倍体结构：目前由于时问和 经济成本上的约束、在实验室里只能得到双倍体结构的复合基因型序列。因此，当需要 知道物种或者组织的单体型序列信息时，我们必须借助于计算手段，将每一条基因型序 列分解为两务单体型序列，这就是单体分型问题。本文研充了不同数据集及不同模型上 单体分型问题的计算复杂性，设计和实现了一系列高效的单体分型和单体型频率估计算 法。其主要内容和贡献包括： ( i ) 群体数据集单体分型 群体数据集不包含任何幂系信息，是最常见的一种基因型数据集。关于群体数据 集单体分型问题，目前常见的计算手段有c l a r k 算法，p p i l 算法雎及e m 和g s 等概率 统计算法。本文对一种新近提出的基于最大节约原则的单体分型( h m p ) 模型进行了研 究，证明其是n p h a r d 的和a p x h a r d 的( 即，除非n p = p ，否则存在一个常数p 0 ， 该j o q 题没有比1 + p 好的多项式时间逼近算法) 。因此，我们为其设计了一个多项式时间 的贪d 算法以及一个将贪n 策略和分支限界策略集合在统一框架下的复台算法。实验结 果表明：贪一。算法在保持了较准确分型结果的基础上运行速度相当快；而复合算法虽 是完全算法，但其运行效率和实例规模比原有的分技限界算法都得到了极大提高。 群体数据集中特定基因型序列分型( s g h ) 判定问题与上述c l a r k 算法相关，它可泓 帮助我们更好理解单体分型问题。拳文证明了s g h 问题为n p 。c o m p l e t e 的。 ( 2 )家系数据集单体分型 由于冢系信息的对单体构型的限制，基于家系数据集进行的单体分型和单体型频率 估计的结果会更加可靠。目前对其研咒集中于寻找使得幂手中发生最少重组事件的单体 构型。本文提出了一个e 一最少重组单体分型( k - m r i q ) 模型，它在现有的最少重组单体 分型【m r f i ) 模型中引八额外限制，使得重组事件在家系中更加合理地平衡分布。同时 设计了k - m r h 模型的一个综合了寻根策略的优化动冬规划算法，尽管该模型也是 n p h a r d 的、但我们的限制条件使其解空间大大缩小，从而大大提高了算法的搜索效率 这在模拟和实际数据的实验中郝得到了验证。 尘里坠兰垫查奎兰篁圭兰堡兰圣 垫量 零重组单体分型( z r h ) 问题是m r h 问题一个特例，其目标是为给疋家系求解不 包含任何重组事件的单体构型，它在单体分型以及单体型频率估计方面具有重要意义。 本文给出了z r h 问题的一个最优的线性时问算法：h c l 连锁分析单体分型算法。 ( 3 )家系数据集单体型频率估计 单体型频率估计和单体分型问题密切相关，本丈提出了一个两段式的家系数据集单 体型频率估计方法：i ) 、单体分型阶段：用h c i 连锁分析单体分型算法找出所有零重 组单体构型：i i ) 频率估计阶段：发展了原有针对群体数据集的e m 算法以在前一阶段 得到的单体构型上进行频率估计，并且使用分割一合并技术，将原指数日 问的e m 算法 改造为近似线性时间算法。 以前的直接估计法不考虑家系信息，必须对所有可能的单体型序列进行估计。而我 们的两段式方法多了一个分型阶段，该阶段排除了大量不合理和不重要的单体构型。因 此，整个频率估计日十问大为减少，结果也更加可靠：这些都从实验中得到了验证。 按照研究内容分类，本文的创新之处在于： 1 群体数据集单体分型证明了h m p 模型为n p h a r d 和a p x h a r d 的；s g l 4 问题 为n p c o m p l e t e 的，并为h m p 模型成功设计了一个贪d 算法和一个复合完全算法，它 们能够解决较大规模的问题实例。 2 、家系数据集单体分型在m r l t 模型基础上，提出了一个更加合理的k - m r h 模 型：并为其设计了一个优化动态规划算法，该算法能够解决犬部分实际的k - m r h 问题； 给出了m r h 问题的特例z r h 问题一个最优的缉睦时问算法。 3 、家系数据集单体型频率估计首次明确指出零重组单体构型可以作为家系数 据集单体型频率估计的基础：并由此为后者设计了一个两段式方法，比起以前的直接估 计法，该方法所需时问大为减少，结果也更加可靠。 关键词：计算生物学、单核苷酸多态性( s n p ) ，基因型、单体型、单体型分析单体 分型、单体构型，最大节约原则、家系、三元家庭重组最少重组、一最少 重组、零重组、组合优化、算法、可计算性、复杂度、n p h a r d 、a p x h a r d 、 分枝限界、贪, 1 2 法、动态规划、h c l 一连锁、e m 算法、分割一合并 a b s t r a c t t h er a p i dd e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g yh a se q u i p p e dm o l e c u l a r b i o l o g i s tw i t hn o v e lp o w e r f u lm e t h o d s h a p l o t y p ea n a l y s i sh a sa r r a c t e dg r e a ta t t e n t i o no f b i o l o g ya n dm e d i c a lr e s e a r c h e r sf o ri t ss i g n i f i c a n c ei nl a t r o l o g y e s p e c i a l l yi ns t u d i e s o n g e n e t i cd i s e a s e sh o w e v e r , m o s to r g a n i s m s ，i n c l u d i n gh u m a nb e i n g s ，a r ed i p l o i ds i n c ei ti s b o t ht i m e c o n s u m i n ga n de x p e n s i v et oo b t a i nh a p l o t y p e s ，g e n o t y p e s ，i n s t e a d ，a r eg e n e r a t e di n l a b o r a t o r i e s w h e nh a p l o t y p ei n f o r m a t i o ni sd e m a n d e d ，w em u s tr e s o r tt oc o m p u t a t i o n a l m e t h o d st os p l i le a c hg e n o t y p et oap a i ro fh a p l o t y p e s i ti sc a l l e dh a p l o t y p i n g w ed i s c u s st h e c o m p u t a t i o n a lc o m p l e x i t i e sf o rt h eh a p l o t y p i n gp r o b l e mo nd i f f e r e n td a t as e t sa n do f d i f f e r e n t m o d e l s w ea l s op r e s e n tas e r i e so fe m c i e n th a p l o t y p i n ga l g o r i t h m sa n dh a p l o t y p ef r e q u e n c y e s t i m a t i o nm e t h o d s t h em a i nc o n t r i b u u t l o n si n c l i t d e ： ( 1 ) p o p u l a t i o nd a t ah a p l o t y p i n g b e a r i n gn op e d i g r e ei n f o r m a t i o n ，p o p u l a t i o ng e n o t y p ed a mi st h em o s tf r e q u e n tk i n do f d a t as e tc l a r ka l g o r i t h m ，p p ha l g o r i t h m a n de ma l g o r i t h m g sa l g o r i t h mw e r eb r o u g h t f o r w a r df o rh a p l o t y p i n go np o p u l a t i o ng e n o t y p ed a t a an e w l yp r o p o s e dm o d e l ，c a l l e dh m p , t h a tb a s e so nt h em a x i m u mp a r s i m o n yr u l ei ss t u d i e di nt h i sp a p e r h m pm o d e l i sv e r ys i m p l e y e tp e r f o r m sp r e t t yw e l li np r a c t i c eh o w e v e r , w ep r o v ei tt ob en p - h a r da n da p x - h a r d f w h i c hm e a n st h a tu n l e s sp2n rh m pc a n n o tb ea p p r o x i m a t e di n p o l y n o m i a lt i m ew i t h i n r a t i oi + pf o rs o m ec o n s t a n t9 1a sw e l l t b i s p a p e rp r e s e n t s ap o l y n o m i a lt i m eg r e e d y a l g o r i t h m a n da c o m p o u n da l g o r i t h mt h a tc o m b i n e st h eg r e e d yp o l i c y w i t ht h e b r a n c h a n d b o u n ds t r a t e g yi nau n i f o r a lt r a m e w o r k t h ee x p e r i m e n t a lr e s u l ts h o w st h a tt h e g r e e d ya l g o r i t h mr n n sm u c hf a s t ，y e to u t p u t sp r e t t yw e l lr e s u l t sa l t h o u g hi ti sa l s oc o m p l e t e ， t h ec o m p o u n d e da l g o r i t h mi sm u c hm o r ee f f i c i e n tt h a nt h eb r a n c h - a n d b o u n da l g o r i t h ma n d c a nb ea p p l i e dt oi n s t a n c e so fm u c hl a r g e rs c a l e s r e l e v a n tt ot h ec l a r ka l g o r i t h m s i n g l eg e n o t y p eh a p l o t y p i n gp r o b l e m ( s g h ) c a l lh e l p t ob e t t e ru n d e r s t a n dt h eh a p l o t y p i n gp t o b l c mw cs h o wt h a ti ti sn p c o m p l e t e ( 2 ) p e d i g r e ed a t a h a p l o t y p i n g h a p l o t y p i n go np e d i g r e eg e n o t y p ed a t a i sb e l i e v e dt ob er n o r ec r e d i b l eb e c a u s et h e p e d i g r e ec o n s l r a i n tf o r c e sg e n o t y p e st o s e t t l eo ns o m eh a p l o t y p ec o n f i g u r a t i o n s c u r r e n t r e s e a r c hh l t e r e s t sf o c u so ns e e k i n gh a p l o t y p ec o n f i g u r a t i o n so fm i n i m u mr e c o m b i n a n t h e r e w ep i e s e n tan l o r ei e a l i s t i ck - m i n i m u mr e c o m b i n a n th a p t o t y p i n g ( k - m r h ) m o d e lt h a t i n t r o d u c e sa na d d l t i o n a lc o n s tr a i n tt ob a l a n c et h ed i s t r i b u t i o no tr c c o m b i n a n t si nt h ew h o l e p e d i g r e ea no p t i m i z e dd y n a m i cp r o g r a m m i n gt h a tc o m b i n e sar o o ts e l e c t i o np o l i c yi sg i v e n a i t h o u g hk - m r i 1i sa l s on i h a r d ，t i l ec o n s t r a i n th a sg r e a t l yr e d u c e dt h es o l u t i o ns p a c ea n d 竺里型茎堡尘奎茎堡圭耋堡篁耋至圣塑茎 t h u sg r e a t l ye n h a n c e dt h es e ar c h i n ge f f i c i e n c yo ft h ed y n a m i cp r o g r a m m i n ga l g o r i t h m ，w h i c h h a sb e e nd e m o n s t r a t e di ne x p e r i m e n t so ns i m u l a t e da n dr e a ld a t as e t s b e i n gas p e c i a lc a s eo ft h em r hp r o b l e m ，t h ez e r or e c o m b i n a n th a p l o t y p i n g ( z r h ) p r o b l e ma i m sa ts e e k i n gh a p l o t y p ec o n f i g u r a t i o nw i t h o u tr e c o m b i n a n t sf o rg i v e np e d i g r e e i t h a sg r e a ts i g n i f i c a n c ei nb o t hh a p l o t y p i n ga n dh a p l o t y p ef r e q u e n c ye s t i m a t i o n i nt h i sp a p e r ， w ep r e s e n ta no p t i m a ll i n e a rt i m ea l g o r i t h m ：t h eh c l a n a l y s i sh a p l o t y p i n ga l g o r i t h m ( 3 ) p e d i g r e ed a t ah a p l o t y p ef r e q u e n c ye s t i m a t i o n h a p l o t y p ef r e q u e n c ye s t i m a t i o ni sc l o s e l y r e l a t e dt ot h eh a p l o t y p i n gp r o b l e m w e p r o p o s e a t w o s t a g e dh a p l o t y p ef r e q u e n c ye s t i m a t i o nm e t h o di n t h i sd i s s e r t a t i o n ：i ) ， h a p l o t y p i n gs t a g e ：e n u m e r a t ea l l z e r or e c o m b i n a n th a p l o t y p ec o n f i g u r a t i o n s u s i n gt h e h c l a n a l y s i sh a p l o t y p i n ga l g o r i t h m ；i i ) ，f r e q u e n c ye s t i m a t i o ns t a g e ：g e n e r a t et h ee m a l g o r i t h mo fp o p u l a t i o nd a t as ot h a ti tw o r k sf o rp e d i g r e eh a p l o t y p ec o n f i g u r a t i o n s ( o b t a i n e d f r o mt h eh a p i o t y p i n gs t a g e ) w ea l s oe m p l o yt h ep a r t i t i o n l i g a t i o nt e c h n i q u et or e c o n s t r u c t t h ee x p o n e n t i a lt i m ea l g o r i t h mt oan e a rl i n e a rt i m eo n e ， d i r e c te s t i m a t i o nm e t h o d so v e r l o o kp e d i g r e ei n f o r m a t i o na n dh a v et ot a k ei n t oa c c o u n t a l lp o s s i b l eh a p l o t y p e s ，w h i l eo u rt w o s t a g e dm e t h o dh a sa ne x t r ah a p l o t y p i n gs t a g e ，w h i c h r u l e so u tag r e a tn u m b e ro fi r r a t i o n a lo ru n i m p o r t a n th a p l o t y p ec o n f i g u r a t i o n sc o n s e q u e n t l y , o u rm e t h o dt a k e sm u c hl e s st i m ea n do b t a i n sm o r ec r e d i b l ee s t i m a t e s ，w h i c hh a sb e e n d e m o n s t r a t e db ye x p e r i m e n t a lr e s u l t s c l a s s i f i e db yt h er e s e a r c hc o n t e n t ，t h ei n n o v a t i o n so ft h i sd i s s e r l a t i o na r e ： 1 ，p o p u i ，a t i o nd a t ah a p i o t y p i n gw eh a v ep r o v e dt h a th m pt ob en p h a r da n d a p x h a r d ；s g ht ob en p c o m p l e t ew ea l s od e s i g nag r e e d ya l g o r i t h ma n dac o m p o u n d c o m p l e t ea l g o r i t h mt h a tc a nb ea p p l i e dt or e l a t i v e l yl a r g es c a l eh m pi n s t a n c e s 2 ，p e d i g r e ed a t af l a p o t y p i n gw ep r o p o s eam o r er e a l i s t i cm o d e l ，k - m r h ，b a s e d o nm r ha n dd e s i g na no p t i m i z e dd y n a m i cp r o g r a m m i n ga l g o r i t h mf o ri t ，w h i c hc a ns o l v e m o s tp r a c t i c a lk - m r hi n s t a n c e sw ea l s op r e s e n ta no p t i m a ll i n e a rt i m ea l g o r i t h mf b rz r t t ，a s p e c i a le a s eo fm r h 3 ，p e d i g r e ed a t ai i a p l o t y i ee r e q u e n c 、, 。e s i i m a t i o n w ef i i s t p o i n t o u tt h a t h a p l o t y p ef r e q u e n c i e si np e d i g r e e sc a nb ee s t i m a t e db a s e do nh a p l o t y p ec o n f i g u r a t i o no fn o n r e c o m b i n a n t a n da c c o r d i n gt ot i f f s ，w ep r e s e n tat w o s t a g e dm e t h o d w h i c ht a k e sm u c hl e s s t i m ea n do b t a i n sm o r ec r e d i b l ee s t i m a t e sc o m p a r e dw i t ht i l ef o r m e rd ir e c te s t i m a t em e t h o d k e y w o r d s ：c o m p u t a t i o n a lb i o l o g ) , ；s i n g l e n u c l e o t i d e p o l y m o r p h i s m ( s ：v 叫g e n o t y p e , h a p l o r y p e h a p l o o , p ea n a l y s i s h a p l o ( y p i n g , h a p l o o , p ec o l 矿i g z t r a t i o n m a x i m u m p o r s i m o n 3 p e d i g r e e ，i o r e c o m b i n a t i o n m i n i m u mr e c o m b i n a n t k - m i n i m u m r e c o m b i n a n t ， z e r o r e c o m b i n a n t , c o m b i n a l o l i o l o p t i m i z a t i o n a l 9 0 7 + i t h m c o m p u t a b i l i t 3 ；c o m p e x i 0 4 n p h a r d a p x - h a r d , b r a n c h a n d - b o u n d , g r e e d y , d y n a m i cp r 0 9 7a m m i u gh c l l i n k a g e e ma f g o ，i t h m ，p a r t i t i o n l i g a t i o n 绪论 本章概要 本章给出整个沧文的主要研究内容。在此之前，我们先简要介绍 计算生物学的概念及研究领域。接下来，我们给出单体分型和单体型频率估计 的研究意义以及前人在这方面已经取得的工作成果。我们还提供了一个简单的 资源列袁，通过该列表可以熟悉和跟进包括单体型分析在内的多个计算生物学 研究课题的进展。本章最后给出全文的章节安排。 1 1 计算生物学 这篇论文的题目“单体分型和单体型频率估计：复杂性及算法”充分说明其内容 既和理论计算机科学又和生物学相关。计算生物学就是这样的一门新兴交叉学科，它 一般使用数学或者计算机手段来觯决生物和医学研究中出现的问题。本文研究内容是 属于单体型分析范畴的单体分型和频率估计问题，其研究动机毫无疑问来自生物和医 学，但是在解决问题的过程中，我们使用的是典型的理沦计算机科学方法：讨沦问题 的计算复杂性、设计完全或者逼近算法并给出算法的复杂性分析以及具体计算平台上 的实验结果。 计算生物学( c o m p u t a t i o n a lb i o l o g y ) ，在越来越多人那里，被当作生物信息学 ( b i o i n f o r m a t i c s ) 的同义词处理：但有一些人则坚持认为计算生物学和生物信息学应 当有不同的含义因为生物信启、学主要关注生物学中所得信息的采集，存贮，分析处理 以及如何提供服务，而计算生物学则侧霉于使j = ；| 汁算手段解决生物学问题；甚至，还 有一些人认为，计算生物学和生物信息学应该是包含与被包含的关系。第 类人可以 细分成两种：其一认为生物信息学的内涵较广，它不光包括传统计算生物学的领域， 也包括新兴的主要是生物数据库和网上数据服务等问题：另外一些人则执完全相反的 意见，他们认为汁算生物学包含普通生物信息学所不包含的大分子体系模拟等研究课 颥。 中国科学技术大学博一| = 学位论文 计算生物学 在这里，我们并不打算给出自己的看法。然而按照传统习惯，本文使用“计算生 物学”这一提法，因为文中涉及到计算机科学范畴的内容主要是典型的计算复杂性和 算法设计，这些与信息处理和服务无关。 生物学是一个古老的学科，而计算机科学则只有几十年的历史。但计算机的飞速 发展和生物数据的海量计算要求以及其天然的序列表达性，使得计算技术进入生物领 域成为一件非常顺理成章的事情。几十年来，计算生物学蓬勃发展，目前已经巍然成 为吸引了最多研究兴趣和研究经费的交叉领域。数以百计的政府研究机构、大学、医 药公司等都投入大量的人力物力进行计算生物学的研究，这与其已取得的重大成果以 及未来的美好预期两者都密不可分。 计算生物学的研究领域十分广泛，一般来蜕，只要是分子生物学所涉及的计算问 题，都可以列入其中。传统的计算生物学研究课题主要包括：序列比对和同源序列检 索、进化树构建、基因发现、基因表达数据分析、模体发现、蛋白质结构和功能预测、 r n a 结构预测、蛋白质设计、蛋白质相互作用等。随着研究的进一步深入以及各个大 型亡| 划比如人类基因组计划、h a p m a p 计划等的完成或者进行，一些新的研究课题吸 引了越来越多研究者的目光，其中包括：基因本体沦和基因组语义学、生物过程路线 图及作用网络、单体型分析、生物文献挖掘、细胞和组织建模等。由此可以看出，计 算机的触角已经深入分子生物学研究的方方面面之中。 1 2 本文工作背景 国际人类基因组单体型图计划( h a p m a pp r o j e c t ) 1 1 是一个由日本、英国、加拿 大、中国、尼日利和美国的科学家们合作进行的国际合作计划。该讲划旨在构建一 个高分辨率的人类d n a 序列多态位点的图谱，以帮助研究人员确定对人类健康和疾病 以及对药物和环境的反础有影响的相关基因的关键信息。 与单体型幽计划相关的单体型分析( h a p l o r y p ea n a l y s i s ) 主要包括单体分型5 2 3 0 3 6 , ”，4 3 2 、单体型频率估圳3 5 t2 0 , 2 7 , 1 “、单体型分块m “3 ”4 6 , 4 5 , 74 ”、标签s n p 位点选择 8 ”4 。“皿 “7 ，”1 等问题。本文主要研究了在群体数据集和家系数据集上的单体分型和 单体型频率估计问题。 单体型的信息可以用来定位与遗传疾病相关的基因m ，”- 2 7 ”1 。但是，常见的生物 个体r 包括人类自身，都具有双倍体结构。f ：i j 于时矧和成本上的约束，我们常常无法 分离出单独的单体型序列进行研究。因此，当研究需要知道物种或者自【织的单体型序 列信息刚，我们需要借助十计算单体分型手段，：i 每缚一条复台基吲型序列分倒为两条 篼一章绪论中国科学技术大学博士学位论文 单体型序列。 针对不同的数据集和模型，目前已有大量的文献讨论单体分型问题。早在】9 9 0 年， a c l a r k 【6 1 就首先研究了群体数据集上的单体分型问题并给出了一个很简单的随机算 法。这之后，在a c m 主办的计算生物学年会( a n n u a lc o n f e r e n c eo f tc o m p u t a t i o n a l b i o l o g y ，r e c o m b ) 等会议以及a m e r i c a nj o u r n a lo f h u m a ng e n e t i c s ，b i o i n f o r m a t i c s 等 杂志上就经常有关于单体分型的报告和文章出现，使得单体分型一直到现在都是计算 生物学研究中的热点问题。 按照给定基因型数据集的不同，单体分型问题可以分为：群体数据集上的单体分 型问题、家系数据集上的单体分型问题以及片断数据集上的单体分型问题。在片断数 据集单体分型问题中，需要进行单体分型的基因型数据是一些互相重叠但不完全相同 的d n a 序列片段【”。在本文中我们讨沦了除片断数据单体分型以外的两种单体分型 问题以及与这两类单体分型问题密切相关的单体型频率估计问题，在下面我们简要 给出这几个问题的研究现状。 1 2 1 群体数据集单体分型 如果给定的基剧型数据集不带有任何家族血缘信息，我们在做单体分型时就可以 认为这些基因型序列相互独立。群体数据单体分型是研究的较早的一类单体分型问题， 这包括刚刚提到的a c l a r k 的研究工作。针对群体数据集上的单体分型问题，目前主 要有两类算法：组合优化算法和概率统训算法。 概率统讨单体分型算法主要包括le x c o m e r 】，m h a w l e y 1 9 1 ，m s t e p h e n s 3 8 i ， 以及zq i n 和tn i u 队3 4 , 2 8 培人的工作。le x c o f f i e r 和mh a w l e y 等首先使用期望最 大化( e m ) 算法来进行群体数据单体分型和单体型频率估计。ms t e p h e n s 提出了一种 基于吉布斯采样( g s ) 的算法。zq i n 等介绍r 使用分割一合并( p l ) 技术的p l e m 算法来改善原来e m 算法的时问复杂度。 概率统计单体分型阎然有其优点，比如分型模型有理沦可以依循，算法设训有框 架可以遵行，并且其结果通常都有一定的置信指标可以参考。然而概率统计方法也 有其兀法避免的固有缺陷比如必须引入假设来使得样本数据满足某个统计模型，算 法运行日_ j 问一般较长等等。特别是，概率统计方法是一种探索学习性的方法，它通常 具有很大的后验概率。例如当给定的样本数据数量不够大时，概率统计方法的结果可 靠望报低。 组合优化方法是另一种解决问题的通用方法，一般来说，比之概率统计方法，它 具确模型简单，算发运行比较快等优点。从组合优化角度来考察单体分型问题首先要 竺垦垒兰垫查奎兰型：! 兰竺篁兰 ! ；! 兰兰三堑塑坌 建立一个组合优化模型。例如d g u s f i e l d 就为a c l a r k 的算法设定了个优化目标( 在 本文中我们称之为晟多分型目口m 1 i i 模型【l ”) 并进行了深入研究。除了m h 模型，d g u s f i e l d 等还提出了个基于遗传和变异的完美进化树单体分型( p p h ) 模型，并围绕 该模型及其变种提出了系列算法【4 ，1 0 , 15 , ”。 在本文中，我们深入研究了一个新近提出的基于最大节约原则的单体分型( h m p ) 模型。我们设训并实现了h m p 模型的一个多项式时问贪心算法以及一个把贪心策略和 分支限界策略集合在统一框架下的复合算法。 1 2 2 家系数据集单体分型 相反，如果给定的基因型数据集带有家族血缘信息，我们就可以利用这些限制信 息，更加_ j 靠地进行单体分型。同样，针对家系数据集上的单体分型问题，电有组合 优化算法和概率统计算法两类算法。 事实上，目前家系数据集单体分型问题的概率统计算法都和前一小节中介绍的群 体数据集单体分型算法样，即忽略家系数据集的家系信息，当成群体数据集作为概 率统计算法的输入。 从组合优化角度来考察家系数据集上的单体分型问题主要基于一个假设：在满足 原来家系和基因型序列的所有单体构型中，如果重组次数越少就越接近真实情况。d q i a n 和lb e c k m a n n ”1 首先形式化了这种单体分型问题，并称之为屉少重组单体分型 ( m r i q ) 问题。 jl i 、tj i a n g 以及k d o i ( 92 3 2 5 h e 目q 了不管是对于简单家系还是般家系，m r h 问题都是n p h a r d 的。在求解方法方面，d q i a n 和l jb e c k m a n n l 3 3 给出了一个启发式 算法来求解m r h 问题。jl i 和tj i a n g 给出了m r h 问题的另一个启发式算法阻2 5 ( 称 为b l o c ke x t e n s i o n ，b e 算法) 以及一个线性规划完全算法1 2 6 2 “。特别地，列于简单家 系，kd o i 、jl i 和丁j i a n g 给出了两个动态规划算法【9 1 。 m r h 问题有一个重要特例：零重组单体分型( z r h ) 问题，即寻找给定家系及基 因型序列不包龠重组的单体构型。em w i j s m a n l 4 2 首先研究了z r h 问题，他提出了一 个包含2 0 条规则的算法； j r 0 c o n n e l l ”1 描述了一个基f 莲冈型消除的指数删间算 法：j l i 和1 ij i a n g 2 3 , 2 5 1 给出了立方州问复杂度的线性规划算法。最近，k z 1 1 a n g 等 4 7 给出了一个包含多条规则的启发式算法。 针对m r h 模型f l , g s 安a ，本义提出了一种更加合理的、考虑蕈组事件在整卜家系中 的平衡分佰的k - 最小晕组( k - m r h ) 模型。我们给出了k - m r h 模型的个带有寻根策 略的优化动态规划算法，以及z r h 问题的一个最优的线性刚问算法。 兰三耋童丝 ! 里塑兰鍪奎奎兰竺圭兰丝篁兰 1 2 3 单体型频率估计 单体型频率估计是一个和单体分型问题密切相关的单体型分析问题陋”1 “。一 方面，有了单体分型的结果可以较容易的进行单体型频率估计；另一方面，单体型频 率的信息也可以用来帮助进行单体分型。另外，样本群体内的单体型频率信息也可以 直接给疾病相关单体型研究提供启示。 目前已有的单体型频率估计问题主要是针对群体数据集。l e x c o f f i e r ”和 mh a w l e v l 1 9 1 等首次给出了阁e m 算法估计单体型频率0 的方法。首先从一个初始频率 参数集。o = f 乱，甜 出发，接下来通过一系列循环步骤通过不断修正参数估 计。在循环过程中首先在当前的参数集0 扩f ，用h a r d y 。w e i n b e r g 方程计算单体构型 的概率以及基因型样本的概率p r ( d o ，旧( 期望步，e x p e c t a t i o ns t e p ) 。接下来，用刚刚 得到的p r ( d i ，肘) 反过来估计瓤的参数集0 泔1 ( 撮大化步，m a x i m i z a t i o ns t e p ) 。这样 循环下去，一直到o 收敛( 0 一0 小于某一个指定阈值) 为止。m + s t e p h e n s 等” 提出的g s 算法也可以用来进行群体数据单体型频率估汁。g s 算法也是从一个初始单 体型序列集合风和初始频率参数集o o 开始，通过循环来改进对h 和0 的估计。g s 算法步中每一次对h 和0 的估计形成一个m a r k o v 链，所以这是一种m a r k o v c h a i n m o n t ec a r l o ( m c m c ) 方法。 群体数据单体型频率 f & 5 , - i 的e m 算法和g s 算法的缺点都在于效率。前面已经指出， e m 算法是指数时间复杂度的，为了克服e m 算法的这个缺陷，zq i n 和i sl i u 1 提 出了一种一使用类似于分治法( d i v i d e a n d c o n q u e r ) 的分刮一连接技术，使用了该技术的 p l e m 算法降低了原来e m 算法的时间复杂度。同样，g s 算法受运行时问的约束更 加大，其原因在于m a r k o v 链收敛的速度很慢。 在本文中，我们的研究集中在使用e m 算法进行家系数据集上的单体型频率估计。 我们指出，和单体分型问题一样，家系信息同样町以帮助降低单体型频率估“的时间 复杂度并提高估计结果的可靠性。 1 3 文献资源 计算生物学的研究离不丌与国际固内同行的交流以及丰富的文献资源。为了便于 调研、学习莉i 研究，我们列出一些在引算生物学领域特别是单体型分析方面有影响 的网络站点、杂志和期刊资源供参考。 中国科学拄术大学博士学位论文 13 文献资源 1 3 1 机构、组织和个人 美国健康署( n i h ) 国立生物信息技术中心( n a t i o n a lc e n t e rf o rb i o t e c h n o l o g y i n f o r m a t i o n ，n c b i ) ：h t t p ：w w w n e b i n l m n i h g o v 欧洲分子生物实验室( e u r o p e a nm o l e c u l a rb i o l o g yl a b o r a t o r y , e m b l ) ： h t l p ：w w we m b l h e i d e l b e r g d e 国际计算生物学会( i n t e r n a t i o n a ls o c i e t yf o rc o m p u t a t i o n a lb i o l o g y , i s c b ) ： h t t p ：f w w w i s c bo r g 基因组研究所( t h ei n s t i t u t ef o rg e n o m i cr e s e a r c h ，t 1 g r ) ：h t t p ：w w wt i g r o r g 橡树岭国家实验室计算生物学研究所( c o m p u t a t i o n a lb i o l o g yi n s t i t u t eo f o a kr i d g e n a t i o n a ll a b ) ：h t t p ：c o m p b i o o r n l g o v h a p m a p 计划m t p ：w w w h a p m a po r g s n p 合作组织h t t p ：s n p e s h l o r g b i o s c i 新闻组h t t p ：h w w w b i on e t u n i v e r