（计算机软件与理论专业论文）生物序列分析算法的研究及其应用.pdf

摘要 摘要 随着人类基因组计划的完成，人们获得了大量的生物学数据。在对这些生物 数据进行处理和分析的过程中，涌现出了大量的数学问题。这些数学问题亟需通 过有效的计算手段进行解决。 d n a 和蛋白质研究是分子生物学中两项核心的研究课题，我们针对d n a 和 蛋白质序列分析中出现的一些数学问题进行研究。单体型是一些特定的d n a 位 点组成的序列。单体型分析可以帮助我们了解基因与疾病之间的关联，这在遗传 疾病的研究方面具有重要意义。模体是一些保守的d n a 片段，模体发现对基因 转录及其调控的研究很有帮助。蛋白质的空间结构决定了它的功能，基于蛋白质 序列，我们可以对蛋白质的结构进行预测，从而为病毒检测以及生物制药等研究 提供帮助。本文围绕单体分型、模体发现和蛋白质结构预测等问题展开研究，主 要的研究内容包括： ( 1 )提出一种群体数据集上的单体分型算法 由于成本的限制，单体型难以 通过实验手段大量获得。但是单体型可以利用基因型数据通过计算手段进行求 解，其中分块- 合并策略被广泛地应用于多个算法中，用以提高算法的效率。在 传统的分块一合并策略中，分块是均匀的，但很多研究表明单体型具有特有的块 结构，分块并不均匀。基于此我们统计不同位点间的关联强度，并使用动态规划 算法设计了更合理的分块策略，利用贪心算法对相邻分块进行合并，我们将新的 分块合并策略其应用于e m 单体分型算法中。 ( 2 )提出一种家系数据集上的单体分型算法近来，通过一些新的生物实验 手段，可以获得一种新类型的数据异或基因型。基于异或基因型的单体分型 成为一项新的研究课题。研究者们对群体数据集上基于异或基因型的单体分型算 法做了很多研究，但基于家系数据的研究还很少。基于完美进化树模型，我们将 家系上的异或基因型分型问题转化为图论中的图实现问题进行求解，家系结构为 问题求解提供了更多的约束，使得问题有更大的概率获得唯一解。 ( 3 )提出一种序列模体发现算法模体在转录因子绑定及蛋白质间相互作用 中起着重要作用，对它的发现会有助于我们了解基因的功能。植入( f jd ) 模体 发现是其中一类经典的问题，但不幸的是，这一问题是n p 难解的。研究者们提 出了很多算法。由于问题的n p 难解性，精确算法难以在有效时间内对其进行求 解。结合哈希表和剪枝策略，我们提出一种更有效的序列模体发现精确算法。 ( 4 )提出一种蛋白质二级结构预测算法蛋白质结构的确定对我们了解蛋白 质的功能至关重要。以往的蛋白质结构预测算法大多是基于序列以及数据库比较 摘要 的。我们结合化学位移信息和蛋白质序列来对蛋白质的二级结构进行预测。通过 n m r 实验，我们可以获得蛋白质中每个氨基酸对应原子的化学位移信息。利用 这些化学位移信息，我们提出一种新的蛋白质二级结构预测算法。算法首先使用 k n n 方法对蛋白质二级结构进行初步预测，之后在利用b c j r 算法对预测结果 进行平滑。 按照研究内容分类，本文的贡献和创新之处在于： ( 1 )群体数据集单体分型根据单体型固有的块结构，提出了一种更合理的 单体型分块合并算法，并将其应用于群体数据集单体分型中，提高了分型的准 确性。 ( 2 )家系数据集单体分型基于一种新型的异或基因型数据，结合家系信息， 提出一个多项式时间的算法对单体型进行求解。和群体数据集相比，家系数据集 有更大概率获得唯一解。 ( 3 )序列模体发现提出了一种新的序列模体发现算法，设计了一个完美哈 希函数，对解空间进行哈希，并在计算的过程中对不可能的解进行剪枝，和已有 的算法相比，该算法取得了更高的效率。 ( 4 )蛋白质二级结构预测基于化学位移数据和蛋白质序列，利用k n n 方 法对蛋白质二级结构进行预测，并使用b c j r 算法对结果进行平滑，和已有的算 法相比，该算法取得了较高的预测准确性。 关键词：生物信息学、单核苷多态性( s n p ) 、单体分型、模体发现、蛋白质二 级结构预测 a b s t r a c t a b s t r a c t w i t ht h ec o m p l e t i o no ft h eh u m a ng e n o m ep r o j e c t ，w eg e tal a r g em o u n to f b i o l o g i c a ld a t a m a n ym a t h e m a t i c a lp r o b l e m sa r i s ef r o mt h ea n a l y s i sa n dp r o c e s s i n g o ft h e s eb i o l o g i c a ld a t a e f f i c i e n ta l g o r i t h m sa r er e q u i r e dt ob ed e s i g n e dt os o l v et h e s e p r o b l e m s d n aa n dp r o t e i ns t u d i e sa r et w ob a s i cs u b j e c t si nt h es t u d yo fm o l e c u l a rb i o l g y w e s t u d ys o m ep r o b l e m si nt h ea n a l y s i so fd n a a n d p r o t e i ns e q u e n c e h a p l o t y p ei st h e s e q u e n c eo fs o m es p e c i a ld n as i t e s h a p l o t y p ec a n b eu s e dt ol o c a t et h ep r o b a b l e g e n o m ea s s o c i a t ew i t hc o m m o nd i s e a s e s h a p l o t y p ea n a l y s i sp l a y sa ni m p o r t a n tr o l e i nt h ed i s e a s ea s s o c i a t i o ns t u d y m o t i fi sac e r t a i nk i n do ff r a g m e n to fd n a m o t i f f i n d i n gi sc r i t i c a lt ot h es t u d yo ft h eg e n et r a n s c r i p t i o na n dr e g u l a t i o no ft h eg e n e e x p r e s s i o n t h ef u n c t i o no fap r o t e i ni sd e t e r m i n e db yi t s s t r u c t u r e t h ep r o t e i n s t r u c t u r ec a nb ep r e d i c t e dt h r o u g hi t ss e q u e n c e ，w h i c hc a nb ef u r t h e ru s e dt ot h ev i r u s d e t e c t i o na n dd r u gd e s i g n w es t u d ys o m ep r o b l e m sa b o u tt h eh a p l o t y p e ，m o t i fa n d p r o t e i ns t r u c t u r e a n dd e s i g ns o m ea l g o r i t h m sf o rt h e m t h em a i nc o n t r i b u t i o n s i n c l u d e ： ( 1 ) p r o p o s i n gah a p l o t y p i n ga l g o r i t h mi np o p u l a t i o nd a t aa c q u i r i n gh a p l o t y p e d a t af r o mb i o l o g i c a le x p e r i m e n t si su s u a l l yv e r yt i m ec o n s u m i n ga n de x p e n s i v e a l t e r n a t i v e l y t h e h a p l o t y p e s c a r lb ei n f e r r e df r o mg e n o t y p e d a t a u s m g c o m p u t a t i o n a lm e t h o d s ，w h i c h i sc a l l e dh a p l o t y p i n g m a n yh a p l o t y p i n g a l g o r i t h m sh a v eb e e np r e s e n t e d b l o c kp a r t i t i o n - l i g a t i o n s t r a t e g y i s w i d e l y a d o p t e di nt h e s ea l g o r i t h m st oi m p r o v e t h ee f f i c i e n c y i nt h et r a d i t i o n a lh a p l o t y p e b l o c kp a r t i t i o n 1 i g a t i o ns t r a t e g y ，t h eb l o c kp a r t i t i o ni su n i f o r m h o w e v e r ，m a n y s t u d i e ss h o wt h a tt h eh a p l o t y p eh a sc e r t a i nb l o c ks t r u c t u r e w ee s t i m a t et h e l i n k a g ed i s e q u i l i b r i u ma m o n g d i f f e r e n ts n p s b ye m p l o y i n gd y n a m i c p r o g r a m m i n ga n dg r e e d ya l g o r i t h m ，w ep r o p o s e am o r er e a s o n a b l eh a p l o t y p e b l o c kp a r t i t i o n 1 i g a t i o ns t r a t e g yt oi m p r o v et h ea c c u r a c yo fh a p l o t y p i n g ( 2 ) p r o p o s i n gah a p l o t y p i n ga l g o r i t h m i np e d i g r e ed a t ar e c e n t l ys o m en e w b i o l o g i c a lt e c h n i q u e s a r ed e v e l o p e dt og e n e r a t ean e wt y p eo fb i o l o g i c a ld a t a c a l l e dx o r g e n o t y p e c o m p a r e dw i t ht h et r a d i t i o n a lg e n o t y p ed a t a ，x o r - g e n o t y p ei s 1 e s si n f i o n n a t i v eb u tm o r ee c o n o m i c s o m es t u d i e sh a v eb e e np e r f o r m e d o nt h e h a p l o t y p i n gi np o p u l a t i o nb a s e do nt h ex o r - g e n o t y p ed a t a h o w e v e r t h er e l a t e d a b s t r a c t s t u d yi np e d i g r e ei sr a r ea c c o r d i n gt oo u rk n o w l e d g e w et r a n s f o r mt h i sp r o b l e m t oat r a d i t i o n a lp r o b l e mi ng r a p ht h e o r yc a l l e dg r a p hr e a l i z a t i o n c o m p a r e dw i t h p o p u l a t i o nd a t a ，p e d i g r e es t r u c t u r ep r o v i d e sm o r ec o n s t r a i n t s ，w h i c hl e a d st o a h i g hp r o b a b i l i t yt og a i nau n i q u es o l u t i o n ( 3 ) p r o p o s i n gas e q u e n c em o t i ff i n d i n ga l g o r i t h mm o t i fp l a y sa ni m p o r t a n tr o l e i nt h et r a n s c r i p t i o nf a c t o rb i n d i n ga n dp r o t e i n p r o t e i ni n t e r a c t i o n m o t i ff i n d i n g w i l lb ev e r yh e l p f u lt oo u ru n d e r s t a n d i n go ft h eg e n o m ef u n c t i o n p l a n t e d ( ，力 m o t i ff i n d i n gp r o b l e mi sat r a d i t i o n a lm a t h e m a t i c a lp r o b l e m u n f o r t u n a t e l yi th a s b e e np r o v e dt ob en ph a r d m a n ya l g o r i t h m sh a v eb e e np r o p o s e d b e c a u s eo fi t s n p h a r d n e s s ，t h er u n n i n gt i m eo fe x a c ta l g o r i t h m sa r eu s u a l l yv e r yl o n g w e p r o p o s e dam o r ee f f i c i e n c ye x a c ta l g o r i t h mb ye m p l o y i n gh a s ht a b l ea n dp r u n i n g s t r a t e g y ( 4 ) p r o p o s i n gas e c o n d a r ys t r u c t u r ep r e d i c t i o na l g o r i t h mt h ed e t e r m i n a t i o no f p r o t e i ns t r u c t u r e i sc r i t i c a lt oo u ru n d e r s t a n d i n go ft h ep r o t e i nf u n c t i o n t h e t r a d i t i o n a lp r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o nm e t h o d sa r eu s u a l l yb a s e do n h o m o l o g ys e q u e n c ec o m p a r i s o n t h r o u g ht h en m re x p e r i m e n t s ，w ec a ng a i nt h e c h e m i c a ls h i o ；n f o r m a t i o no ft h ea t o m si ne a c ha m i n oa c i do fap r o t e i n u s i n gt h e c h e m i c a ls h i f ti n f o r m a t i o n ，w ep r o p o s e dan e wp r o t e i ns e c o n d a r ys t r u c t u r e p r e d i c t i o na l g o r i t h m a tf i r s t t h i sa l g o r i t h mu s ek n nm e t h o dt o p r e d i c tt h e s e c o n d a r ys t r u c t u r e t h e nt h eb c j ra l g o r i t h m i s e m p l o y e dt o s m o o t ht h e p r e d i c t i o nr e s u l t 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 st h e s i sa r e ： ( 1 ) h a p l o t y p i n gi np o p u l a t i o na c c o r d i n gt ot h eh a p l o t y p eb l o c ks t r u c t u r ei nt h e h u m a ng e n o m e ，w ep r o p o s eam o r er e a s o n a b l eh a p l o t y p eb l o c kp a r t i t i o n - l i g a t i o n a l g o r i t h m t h i sa l g o r i t h mc a nb eu s e di nt h eh a p l o t y p i n gp r o b l e mi np o p u l a t i o nt o i m p r o v et h ea c c u r a c yo ft h eh a p l o t y p i n gr e s u l t ( 2 ) h a p i o t y p i n gi np e d i g r e ew ep r o p o s ea na l g o r i t h mw i t hp o l y n o m i a lt i m e c o m p l e x i t y t os o l v et h e h a p l o t y p i n gp r o b l e m i n p e d i g r e e b a s e do nt h e x o r - g e n o t y p ed a t a c o m p a r e dw i t ht h ex o rh a p l o t y p i n gi np o p u l a t i o n ，t h ep e d i g r e e s t r u c t u r ep r o v i d e sm o r ec o n s t r a i n st ot h i sp r o b l e m ，w h i c hi n c r e a s e st h ec h a n c et o g a i nau n i q u es o l u t i o n ( 3 ) s e q u e n c em o t i ff i n d i n gw ep r e s e n tan e ws e q u e n c em o t i ff i n d i n ga l g o r i t h m a p e r f e c th a s hf u n c t i o ni sd e s i g n e dt om a pt h es o l u t i o ns p a c e p r u n i n gs t r a t e g yi s a l s oe m p l o y e di no u ra l g o r i t h mt or e d u c et h ea v e r a g et i m ec o m p l e x i t y c o m p a r e d - i v a b s t r a c t w i t ht h ee x i s t e da l g o r i t h m s ，o u ra l g o r i t h mi sm u c hm o r ee f f i c i e n t ( 4 ) p r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o nu s i n gt h ec h e m i c a ls h i f ti n f o r m a t i o n a n dp r o t e i ns e q u e n c e ，w ee m p l o yk n nm e t h o dt op r e d i c tt h ep r o t e i ns e c o n d a r y s t r u c t u r e b c j ra l g o r i t h mi su s e dt os m o o t ht h ep r e d i c t i o nr e s u l tt of u r t h e r i m p r o v et h ea c c u r a c y c o m p a r e dw i t ho t h e ra l g o r i t h m s ，o u ra l g o r i t h mg a i n sb e t t e r r e s u l t k e y w o r d s ：b i o i n f o r m a t i c s ，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 ) ，h a p l o t y p i n g ，m o t i f f i n d i n g ，p r o t e i ns e c o n d a r ys t r u c t u r ep r e d i c t i o n v 一 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得 的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表 或撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文 中作了明确的说明。 作者签名： 签字日期：翌丝垦兰 中国科学技术大学学位论文授权使用说明 作为申请学位的条件之一，学术论文著作权拥有者授权中国科学技术大 学拥有学位论文的部分使用权。即：学校有权按有关规定向国家有关部门或机 构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位 论文。本人提交的电子文档的内容和纸制论文的内容相+ 。致。 保密的学位论文在解密后也遵守此规定。 留么开口保密( 年) 作者签名：建幽 签字日期： 2 d 肜j 广 导师签名：1 巫 签字日期：塑19q 9 第1 章结论 第1 章绪论 本章概要 近些年来，生物科学与计算科学飞速发展，一门新的变叉学科一 生物信息学也随之兴起。在本章中，我们首先对生物信息学的概念及研究内容作 简单的介绍；之后介绍本文所研究的几项研究课题，分别是群体数据集单体分型、 家系教据集单体分型、生物序列模休发现和蛋白质二级结构预测问题；最后给出 全文的章节安排。 1 生物信息学 1 9 9 0 年人类基因组计划j 下式启动，包括我国在内的美国、英国、法国、1 3 本等多个国家参与了这项计划，我国在其中负责大约1 的基因组测序工作。人 类基因组计划不仅帮助我们进一步了解人类基因的奥秘，同时也掀起了全世界生 命科学研究的热潮，这一计划和曼哈顿原子弹计划与阿波罗登月计划并称为2 0 世纪三大科学计划。 g r o a t l l 9 8 2 h o f g e 8 n l b a n k 4 n 2 随着人类基因组计划的完成人们得到了大量的基因序列数据。而同时由于 生物基因测序技术的不断成熟生物序列数据更是在最近的十几年里有了爆炸性 的增长。图1 1 列出了g c i l b 趴k 数据库近3 0 年里的数据增长曲线瑚，时至今日， ” n 0 ic口ieil，f0 第1 章绪论 g e n b a n k 数掘库已经收录了超过1 亿条d n a 序列的1 0 0 0 多亿对碱基对的信息。 海量的信息为我们解密基因密码提供了可能，但同时也对数据的分析处理造成了 极大的困难。 海量的数据当然无法通过人工手段有效地处理和分析，一门横跨生物科学与 计算机科学的交叉学科生物信息学( b i o i n f o r m a t i c s ) 就由此诞生了。尽管 生物学是一门非常古老的学科，计算机科学却仅有几十年的历史，而由它们所衍 生出来的生物信息学的历史就更为短暂。如果从s m i t h 和w a t e r f l l a n 在1 9 8 1 年发 表的关于序列比对的标志性论文算起【3 】，对生物信息学的研究也不过是最近三十 年的事情。尽管如此，作为一门新兴学科，生物信息学的发展却非常迅速。大量 的科研院校、研究所、医药公司都投入到生物信息学的研究中来。通过对生物信 息学的深入研究，人们加深了对各种生命现象的认识。而生物信息学的蓬勃发展 也对生物学、医学等学科产生了深远的影响。 生物信息学所涵盖的内容非常广泛，海量的生物数据处理对计算科学中的数 据库、模式识别、数据挖掘、分类聚类等算法提出了更高的要求，不仅如此，生 物学中的很多问题也可以被抽象成为数学模型，亟需通过高效的算法来进行求 解。具体说来，生物信息学的研究课题包括序列比对、进化树构建、基因发现、 基因表达数据分析、基因组序列嗣转排序、模体发现、蛋白质结构预测、蛋白质 功能预测、蛋白质功能位点鉴定、r n a 结构预测、蛋白质相互作用等【lj 。而随 着生物科学研究的不断深入，一些新的课题如单体型分析、蛋白质鉴定、生物过 程路线图及作用网络等也不断涌现出来。 1 2 本文的研究内容 在这里我们对本文的研究内容、当前的研究现状做一个简单的介绍，详细的 背景知识会在论文的第二章进行补充说明。 我们知道，基因是人类遗传的物质基础，而d n a 则是基因的载体，很多遗 传性疾病例如糖尿病、白血病甚至癌症等都和d n a 有着密不可分的关烈4 1 。通 过对d n a 序列的分析，我们可以了解不同基因的功能，比较疾病基因与f 常基 因之间的异同，从而寻找治疗这些疾病的方法。蛋白质则是人类生命的物质基础， 它不仅是构成细胞和生物体的重要物质，同时也在很多生命活动中扮演着重要的 角色。针对d n a 和蛋白质研究中出现的一些数学问题，我们设计了相应的算法 进行求解，主要的工作包括以下几个方面：群体数据集单体分型、家系数据集单 体分型、生物序列模体发现以及蛋白质二缴结构预测。 1 2 1 群体数据集单体分型 第1 章绪论 单体型( h a p l o t y p e ) 是d n a 序列的片段，它可以帮助我们定位和遗传疾病 相关的基因。但是常见生物的染色体都是双倍体结构，例如人类就有2 3 对染色 体。由于生物实验手段的限制，通常我们只能获得一对染色体中两条单体型的混 合序列，这种混合序列同时也被称作是基因型( g e n o t y p e ) 。要将基因型序列通 过实验手段分离丌来，需要耗费大量的时间以及昂贵的成本。出于对时间以及成 本的考虑，为了大规模地获得单体型数据，一个自然的想法就是通过计算的手段 将两条单体型序列分解开来，这就是单体分型问题。 为了定位与疾病相关的基因，生物学家们通常需要收集一些正常个体和疾病 个体的基因型数据，并对两者进行比较和分析。这些个体往往是相互独立的，互 相之间并不存在血缘关系。对于这些群体基因型数据集上的单体分型问题，研究 者们做了大量的工作，目前的研究主要集中于两类算法：组合优化算法和频率估 计算法。 基于生物学的一些发现，研究者们可以抽象出一些数学模型或者约束，组合 优化算法大多基于这些数学模型以及约束。在1 9 9 0 年，c l a r k 首先提出了关于单 体分型的一个简单规则【5 】，之后基于c l a r k 规则g u s f i e l d 等人又提出了最大求解 问题以及最大简约模型【6 】，尽管这些问题最终大都被证明为n p 难解的，研究者 们仍然提出了很多实用的近似算法以及分支限界算法 7 q 2 】。除此之外，基于一些 生物实验发现，g u s f i e l d 又提出了完美进化树模型【l 引，完美进化树为单体分型问 题加入了额外的约束，使得单体分型问题可以在一些情况下在多项式时间内进行 求解。 组合优化算法通常可以为每个个体给出一个精确的单体型构造解，但正如前 面所说，基于c l a r k 规则的单体分型问题大多是n p 难解的，而完美进化树模型 所加入的约束又太强，某些时候并不符合真实情况。一些研究者试图通过概率统 计的方法来估计单体型出现的频率，并根据所估计的频率为每个个体寻找最可能 的单体型构造解。对此研究者们做了大量的研究，主要的单体型频率估计算法包 括期望最大化算法( e x p e c t a t i o nm a x i m i z a t i o n e m ) 1 4 - t 5 、贝叶斯统计算法 ( b a y e s i a n ) 1 6 1 以及马尔可夫蒙特卡洛算法( m a r k o vc h a i n m o n t ec a r l o ) u r l 等。 和组合优化算法相比，频率估计算法不但可以统计出不同单体型的频率分 布，还可以提供每个单体型构造解的概率作为置信度参考。但是频率估计算法通 常需要较大的数据样本，并且需要较长的时间来对单体型概率进行统计。利用分 治的思想，q i n 等人提出了分块合并算法来降低频率估计算法的时间复杂度1 1 川。 q i n 等人的分块合并算法对单体型的分块是均匀的，但是一些研究表明，人 类的单体型并不是均匀的，而是具有特定的块结构【1 弘剐。基于这个发现，在本文 第1 章绪论 中我们研究了单体型的块结构，提出了基于基凶型的单体型分块算法，并据此提 出了更优的分块一合并算法来提高单体型频率估计的准确度。 1 2 2 家系数据集单体分型 除了群体基因型数据，我们知道，很多疾病例如糖尿病、哮喘等都带有明显 的遗传特征，对于一个家族基因的系统分析更能够帮助我们了解这些疾病的病 因。这时我们就需要在家系数据集上进行单体分型。 和群体数据集相比，家系数据集会提供给我们更多的信息。孟德尔遗传定律 告诉我们，我们的每一对染色体中都有一条染色体来自于父亲，而另外一条来自 于母亲。利用孟德尔遗传定律，家系信息能够有效地帮助我们进行单体分型。和 群体数据集一样，对家系数据集上单体分型问题的研究同样分为组合优化算法和 频率估计算法两类。 在基因遗传的过程中，单体型可能会发生重组，但是发生重组的位点是不确 定的。重组给家系数据集上的单体分型问题带来了很多困难，好在重组发生的概 率并不大，所以大多数组合优化算法都基于这样一个假设：重组次数越少的单体 型构造就越接近真实情况，这就是最少重组单体分型问题( m i n i m u m r e c o m b i n a t i o nh a p l o t y p el n f e r c n c e m r h i ) 。 “和j i a n g 首先证明了带环家系的m r h i 问题是n p 难解的1 2 0 j ，之后d o i 等 人又证明了无环家系的m r h i 问题同样是n p 难解的1 2 ，并同时给出了两个指数 时间的动态规划算法，分别适用于家系较小及单体型长度较短的情况。q i a n 和 b e c k m a n n 给出了一个多项式时间的近似算法【2 2 1 ，l i 和j i a n g 同样也提出了一个 基于块扩展的启发式算法 2 3 】。 一些研究表明人类的单体型具有块状结构，块内通常不会发生重组i l 引，基 于这个发现，m r h i 问题在单体型块内就退化为零重组单体分型问题( z e r o r e c o m b i n a t i o nh a p l o t y p ei n f e r e n c e z r h i ) 。和m r h i 不同，z r h i 是在多项式 时间内可解的。w i j s m a n 首先研究了z r h i 问题【2 4 1 ，并提出了一个基于2 0 条规 则的算法，之后l i 和j i a n g 给出了立方时间复杂度的线性规划算法f 2 引，2 0 0 5 年 c h a n 等人又提出了z r h i 问题的线性时间算法【2 6 1 。 类似地，基于群体数据的单体型频率估计算法也可以扩展到家系中来，z h a n g 等人对基于家系的单体型频率估计算法做了相应的研究【2 7 1 。 在单体分型算法不断发展的同时，获取基因型的生物实验手段也在不断进 步，最近一种新的实验手段d h p l c 被生物学家提出【2 8 】。和传统提取基因型的生 物实验手段相比，d h p l c 更加廉价，但是d h p l c 只能区分出杂合位点与纯合 位点，却不能区分两种不同的纯合位点，由d h p l c 实验获得的基因型数据也被 第1 章绪论 称作是异或基因型( x o rg e n o t ) r p e ) 。如何针对这种不同类型的基因型数据进行单 体分型，就成为生物信息学研究中的一项新课题。研究者们对此作了很多工作， 但是目前对异或基因型的研究主要集中在群体数据上【2 9 引】，而针对家系数据的工 作却很少。结合完美进化树模型，我们提出了基于家系异或基因型数据的单体分 型算法，并在模拟家系数据集与群体数据集上做了实验结果比较。 1 2 3 生物序列模体发现 生物序列模体发现同样是d n a 序列分析中一项重要的研究课题【3 2 】。在d n a 转录的过程中，有一类特殊的蛋白质，被称作是转录因子( t r a n s c r i p t i o nf a c t o r ) ， 它们会结合在识别的d n a 序列上，从而对基因表达进行调节。在d n a 序列上 与转录因子结合的位点被称作是转录因子绑定位点( t r a n s c r i p t i o nf a c t o rb i n d i n g s i t e ) ，通常这些绑定位点是一些非常相似但又不完全相同的短串，我们将其称之 为模体( m o t i f ) 。 生物序列模体发现问题就是从很多d n a 序列中寻找出这样的短串，这有些 类似于计算机科学中的模糊字符串匹配问题。但与之不同的是，我们只有文本串， 却并不知道模式串是什么。我们只知道很多文本串中都包含了类似的模式串，目 标是将这些模式串找出来。研究者们对此做了大量的工作，现有的模体发现算法 主要分为组合优化算法和频率估计算法两类。 对模体发现的组合优化算法大多基于( td ) 模型，但不幸的是，基于( 厶d ) 模型的模体发现问题是n p 难解的，尽管如此，研究者们仍然做了大量的工作。 p e v z n e r 和s z e 首先将这一问题转化为图论中的最大团问题【3 3 】，并给出了一个指 数时间的精确算法w i n n o w e r ，之后m i t r a 3 4 】，p m s l 3 5 】，r i s o t t o 3 6 j ， s p e l l e r 3 7 1 ，v o t i n g 3 8 1 矛dp m s p r u n e 3 9 1 等精确算法也先后被提出来，这些算法的 时间复杂度大多是关于，和d 的指数函数，但是通过剪枝及分支限界策略，它们 可以有效应用于规模较小的实例中。除了精确算法，研究者们还提出了一些随机 算法如p a t t e r nb r a n c h i n g 4 0 】和r a n d o mp r o j e c t i o n 4 i 】等，这些随机算法通过多次迭 代，可以在一定概率上获得问题的解。 e m 算法【4 2 1 和吉布斯采样1 4 3 】等频率估计算法也被应用于模体发现问题中。频 率估计算法通常需要很长的运行时间，但和组合优化算法不同，频率估计算法并 不会给出一个精确的模体，而是给出模体中每个位置上各种核苷出现的频率。 针对模体发现的( td ) 模型，我们提出了c v o t i n g 算法，通过剪枝及构建哈 希表，c v o t i n g 算法可以对问题进行精确求解，尽管算法的时间复杂度仍然是指 数的，但和现有的大多数精确算法相比，c v o t i n g 算法仍然具有最快的运行速度。 第l 章绪论 1 2 4 蛋白质二级结构预测 不仅d n a 序列中存在模体，在蛋白质中同样也存在着模体。蛋白质模体通 常具有非常相似的空间结构，并在蛋白质一蛋白质问相互作用的过程中扮演着重 要的角色。对蛋白质空间结构的确定将有助于我们了解蛋白质的功能，同时也对 病毒诊断和药物设计等工作具有重要的指导意义。 蛋白质的空间结构可以通过x 射线晶体衍射( x r a yd i f f r a c t i o n ) 或者核磁 共振( n u c l e a rm a g n e t i cr e s o n a n c e n m r ) 等生物实验获得，但是这些生物实 验通常非常昂贵且耗时漫长。蛋白质的空间结构与它的氨基酸序列之间存在着密 切的关联，如何通过蛋白质的氨基酸序列准确地预测蛋白质的空间结构就成为生 物信息学中一项重要的课题。 蛋白质的空间结构通常也称为蛋白质三级结构，但是到目前为止，对蛋白质 三级结构进行预测仍然非常困难。由于蛋白质的分子结构特性，蛋白质的空l 日j 结 构具有明显的规律性。从空间结构特点进行区分，蛋白质的结构大体上可以分为 口螺旋( 口h e l i x ) 、折叠( s t r a n d ) 和无规则卷曲( c o i l ) 三种，这也就是 所谓的蛋白质二级结构。蛋白质二级结构预测问题就是通过氨基酸序列对蛋白质 中每个残基所处的二级结构进行预测。蛋白质二级结构预测不仅可以帮助我们了 解蛋白质的大概结构特点，同时也可以为进一步的三级结构预测提供依据。 研究者们已经提出了大量的蛋白质二级结构预测算法，包括c h o u f a s m a n 算法晔l 、g o r 算法【4 5 】、人工神经网络算法【4 6 】等等，这些算法大多基于蛋白质的 序列信息，对二级结构的预测结果并不理想。通过n m r 实验，我们可以获得与 蛋白质结构相关的大量信息，通过这些信息，生物学家可以根据经验确定蛋白质 的三维空间结构，但这一过程通常非常耗时。如果可以通过计算的方法对n m r 实验所得的实验数据进行分析，并进而确定蛋白质的三级结构，势必会大大提升 蛋白质三级结构测定的效率。利用n m r 实验中获得的这些与结构相关的信息， 我们可以进行较为准确的蛋白质二级结构预测，从而为进一步的蛋白质三级结构 预测打下基础。 通过n m r 实验，我们可以获得蛋白质的每个残基中相应原子的化学位移信 息，这些化学位移信息和蛋白质的空间结构密切相关。结合这些化学位移信息， 研究者们也提出了一些算法来进行蛋白质二级结构预测。但是由于以往的数据较 少，预测的准确率和可靠性都有所欠缺。我们收集了更大规模的化学位移数据， 并在其基础上提出了新的算法，和已有的算法相比，新算法的准确率和可靠性都 有所提升。 第1 章绪论 1 3 论文组织 本文首先介绍研究课题所需的背景知识，然后按照研究内容的先后顺序以及 各个课题之间的关联进行撰写和编排。全文共分七章，各章节的内容安排如下。 第一章：绪论 本章首先对生物信息学这一新兴交叉学科的历史和现状 做简单的介绍，然后大致介绍了群体数据集单体分型、家系数据集单体分型、生 物序列模体发现及蛋白质二级结构预测问题的意义和研究现状，并给出了我们的 研究侧重点。最后给出本文的章节安排。 第二章：分子生物学背景为了方便后面的讨论，本章将重点介绍单体 分型、生物序列模体发现及蛋白质二级结构预测方面的分子生物学背景知识。我 们会描述染色体、d n a 、s n p 、单体型、基因型、模体、蛋白质、化学位移、蛋 白质二级结构这些生物概念，并给出进行单体分型、模体发现及蛋白质二级结构 预测研究的动机及意义。 第三章：群体数据集单体分型本章首先给出群体数据集单体分型问题 的数学定义，然后分别介绍针对这一问题的组合优化算法及频率估计算法。对组 合优化算法，我们将主要介绍最大简约模型和完美进化树模型；对频率估计算法， 我们将着重介绍e m 算法及p l e m 算法。之后我们将提出一个新的基于基因型 的分块算法，并将其应用于p l e m 算法中，从而提高算法的准确性，详细的算 法步骤及实验结果也将在本章中给出。 第四章