（计算机应用技术专业论文）单体型组装加权最小字符翻转问题参数化算法研究.pdf

摘要 单体型检测在遗传病基因的定位、药理反应的研究、个体识别等 方面有极其广阔的应用前景。但是在当前的实验技术下直接测定个体 的单体型所需的时间和金钱上的花费过于昂贵，因此利用计算机技 术来确定个体的单体型有极其重要的现实意义。单体型检测可分为两 大类：单体型组装问题和单体型推断问题。本文主要对单体型组装问 题相关模型和算法进行研究。 由于单体型组装问题计算模型绝大部分是n p h a r d ，当片断数和 s n p 位点数较大时，基本上没有可行的精确算法，而诸如启发式算法、 遗传算法等近似算法的近似程度很难保证，往往不能获得最优解。因 而尽可能提高精确算法的时间和空间效率具有极其重要的现实意义。 本文着重探索了如何利用小参数技术显著降低相关计算模型的 时间和空间复杂度，并针对单体型组装加权最小字符翻转( w m l f ) i h - 题提出了一个时间复杂度为o ( n k 2 2 殷切，卿z + 优岛) 的参数化算法，可 以在较短的时间得到w m l f 问题的精确解，具有良好的可扩展性和 较高的实用价值。 参数化算法是精确算法而且具有时空复杂度较低的特性，因此我 们在现有实验条件下可利用参数化算法来比较不同计算模型的单体 型重构精度。基于适用于不同模型的参数化算法，本文对m s r 、m f r 、 m e c 、w m l f 、m e c g i 等单体型组装模型做了详细的分析比较，从 而提出了一系列新的评价指标，然后采用真实和模拟的生物数据对相 关模型进行大量实验，分析影响单体型重构精度的原因，从而为设计 新的计算模型指明了思路。 关键词单核苷酸多态性，单体型，n p 一难问题，参数化算法 a bs t r a c t h a p l o t y p ed e t e c t i o nh a se x p a n s i v ea p p l i c a t i o ni ni n h e r i t e dg e n e s o r i e n t a t i o n ，m e d i c i n er e a c t i o n s r e s e a r c ha n di n d i v i d u a li d e n t i f i c a t i o n t h ec o s to ft i m ea n dm o n e yi st o oe x p e n s i v et od e t e c tt h ei n d i v i d u a l h a p l o t y p eu n d e rt h ec u r r e n te x p e r i m e n tt e c h n i q u e ，s ot h eu s eo fc o m p u t e r t oc o n f i r mt h ei n d i v i d u a lh a p l o t y p eh a sg r e a ts i g n i f i c a n c e h a p l o t y e d e t e c t i o nc a nb ec l a s s i f i e di n t ot w oc l a s s e s ：h a p l o t y ea s s e m b l yp r o b l e m a n dh a p l o t y p ei n f e r e n c ep r o b l e m t h i sp a p e rm a i n l yd o e sr e s e a r c ho n m o d e l sa n d a l g o r i t h m so fh a p l o t y p ea s s e m b l yp r o b l e m b e c a u s em o s to ft h em o d e l sa r en p h a r d ，i ft h en u m b e ro ff r a g m e n t s a n dt h es n p si sb i g g i s h ，t h e r ei sf e wf e a s i b l ea c c u r a t ea l g o r i t h m s b u tt h e a p p r o x i m a t i o no fa p p r o x i m a t ea l g o r i t h m s i s u n c e r t a i n ，s u c ha s t h e h e u r i s t i ca l g o r i t h m s ，a n dt h e s ea l g o r i t h m sc a n tg e tt h eo p t i m a lr e s u l ti n m o s tc a s e s s oi th a sg r e a ts i g n i f i c a n c et oi m p r o v et h et i m ea n ds p a c e s e f f i c i e n c yo fa c c u r a t ea l g o r i t h m s t h i sp a p e re m p h a s i z e so nh o wt om a k eu s eo ft h ep a r a m e t e r t e c h n i q u et or e d u c et h et i m ea n ds p a c e sc o m p l e x i t yo fc o m p u t a t i o n m o d e l s i tf o r w a r d sap a r a m e t e r i z ea l g o r i t h mf o rt h eh a p l o t y p ea s s e i n b l y p r o b l e mw e i g h t e dm i n i m u ml e t t e rf i i p s ( w m l f ) w h i c hh a st h et i m e c o m p l e x i t yo ( n k 2 2 殷+ m l o g m + m k i ) t h i sa l g o r i t h mc a ng e tt l l ea c c u r a t e r e s u l tq u i c k l y , a n di ti ss c a l a b l ea n da p p l i c a b l ei np r a c t i c e b e c a u s et h ep a r a m e t e r i z e da l g o r i t h mi sa na c c u r a t ea l g o r i t h ma n di t h a st h ep r o p e r t yo fl o wt i m ea n ds p a c e sc o m p l e x i t y , w ec a nm a k eu s eo f p a r a m e t e r i z e da l g o r i t h mt oc o m p a r et h eh a p l o t y p er e c o n s t r u c t i o nr a t ef o r d i f f e r e n tm o d e l s 。t h i sp a p e rd o e ss p e c i f i ca n a l y s i so nm s r ，m f r 、m e c ， w m l fa n dm e c g i ，a n df o r w a r d ss o m en e wj u d g es t a n d a r d a f t e rt h a t w ed oal o to fe x p e r i m e n t s o u ra n a l y s i sa n dr e s u l t sd e m o n s t r a t en e w p r o s p e c t so nd e s i g n i n gn e wc o m p u t a t i o nm o d e l s 。1一 k e yw o r d s s i n g l e n u c l e o t i d ep o l y m o r p h i s m s ，h a p l o t y p e ，n p h a r d p r o b l e m ，p a r a m e t e r i z e da l g o r i t h m i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：上毕 日期：盟年卫月卫日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 日期：2 盆年望月纽日 硕士学位论文 第一章绪论 第一章绪论 随着电子信息、空间科技、物理化学等各种科学技术的发展，人类对于世界 的认识和了解在迅速扩展。生命科学的发展，特别是通过人类基因组测序计划， 人类将自身基因组信息这部“天书”中的“字母”翻译成了可以理解的文字，第一次 较为全面的认识了关于自身的生长、发育、健康、进化等方面的基因组信息，终 于打开了生命的奥秘之门。尽管如此，我们对生命的奥秘还缺乏了解，对生命信 息的组织、传递和表达还知之甚少，对不断产生的生物数据的了解和利用远远不 够。这些生物分子数据具有丰富的内涵，其背后隐藏着人类目前尚不知道的生物 学知识。充分利用这些数据，通过数据分析、处理，揭示这些数据的内涵，从而 得到对人类有用的信息，是生物学家、数学家和计算机科学家所面临的一个严峻 的挑战。 生物信息学就是为迎接这种挑战而发展起来的一门新型学科【l 】，一般意义 上，生物信息学是研究生物信息的采集、处理、存储、传播、分析和解释等各方 面的一门学科，它通过综合利用生物学、计算机科学和信息技术而揭示大量而复 杂的生物数据所赋予的生物学奥秘。具体而言，生物信息学作为一门新的学科领 域，它是把基因组d n a 序列信息作为源头，在获得蛋白质编码区的信息后进行 蛋白质空间结果模拟和预测，然后依据特定蛋白质的功能进行必要的药物设计。 基因组信息学、蛋白质空间结构模拟以及药物设计构成了生物信息学的3 个重要 组成部分。在生物学、医学的研究和应用中，利用生物分子数据及其分析结果， 可以大大提高研究和开发的科学性及效率，如根据基因功能分析结果来检测与疾 病相关的基因，根据蛋白质分析结果进行新的药物设计等。一般提到的“生物信 息学”就是指这个狭义的概念，更准确的说，应该是分子生物信息学( m o l e c u l a r b i o i n f o r m a t i c ) 。 目前，分子生物信息学是国内外科学家的一个研究热点。本文主要关注生物 信息学中单体型组装计算问题的研究，即给定一组来自某对同源染色体的由 d n a 测序方法得到的d n a 片段数据，根据片段上的s n p 值组装出两条单体型。 本文将对单体型组装计算问题的典型计算模型进行比较研究，并针对其中的 w m l f 模型进行了相应的算法研究与实验分析。 1 1 课题研究背景 为了破译人类的遗传信息，1 9 9 0 年1 0 月人类基因组计划启动，2 0 0 3 年4 月 硕士学位论文第一章绪论 人类基因组图谱基本完成，至此人类基因组共性的一面被揭示出来，但人类个体 多态性的一面没有得以体现。不同的人具有不同的外貌、体格，对疾病有不同抵 抗能力，对药物有不同的敏感性，从遗传上说，这是因为不同个体( 除了同卵双 胞胎外) 的基因组不完全相同。两个人之间的d n a 差异约占基因组的0 1 ，不 同个体或种群之间d n a 序列的差异称为多态性。d n a 序列的差异决定着一些外 部特征如绿眼睛和褐眼睛，直发与弯发等。 单核苷酸多态性s n p ( s i n g l e n u c l e o t i d ep o l y m o r p h i s m s ) 是由染色体上单个碱 基的变化引起的一种d n a 序列差异。s n p 是人类基因组d n a 序列变异的主要 形式，决定了人类疾病( 尤其是多基因疾病) 易感性和药物反应性差异的核心信 息。平均每1 0 0 0 个碱基序列中就可能有一个单核苷酸多态性发生，在整个人类 基因组中大约有3 4 0 万个单核苷酸多态性存在【2 】。s n p s 是一个物种中不同个体 表型的主要遗传来源，而单体型是一条染色体上的一段相关的s n p s 的有序组合。 单体型检测为基因的精确定位，常见疾病致病基因定位、药理反应差别等研究， 最终将为复杂性疾病的诊断、个性化治疗乃至疾病的预警预防提供分子遗传的数 据基础，亦可用于人类各群体的遗传关系分析 3 , 4 1 。s t e p h e n s 等采用个体单体型 问题变异的方法研究人类31 3 个基因中的3 8 9 9 个s n p s ，然后进行连锁不平衡分 析，其结果支持了人类群体在近代扩张的说法f 5 l 。h o r i k a w a 等根据s n p s 进行关联 分析在墨西哥裔美国人中把2 型糖尿病基因定位在2 号染色体长臂，并发现 c a p n l 0 基因的3 个s n p s 和2 型糖尿病相关1 6 1 。 为了确定对人类健康和疾病以及对药物和环境的反应有影响的相关基因的 关键信息，构建人类d n a 序列中多态位点的常见模式，即单体型i 羽( h a p m a p ) ， 2 0 0 2 年l o 月国际人类基因组单体型图计划启动【7 , s l ，2 0 0 5 年1 0 月公布了第一阶 段人类基因组单体型图1 9 1 。人类基因组计划( h u m a ng e n o m ep r o j e c t , h g p ) 解读了 分布于2 2 条常染色体与两条性染色体上的3 0 亿对碱基，涵盖了人类的所有生存 信息。全人类只有一个共同的基因组，但每个个体中所含有的某些基因会出现细 微差别，这些差别中包含了人类各种生物学现象的奥秘。随人类基因组研究的纵 深发展，对人类基因组多态性及变异的研究十分必要。单核苷酸多态性是d n a 多态性的一种，指d n a 序列中单碱基的差异，由于其数目多、分布广泛且相对 稳定，成为继第一代限制性片段长度多态性标记、第二代微卫星标记后的第三代 基因遗传标记，是随着h g p 的实施而发展起来的新一代遗传标记，被认为是人 们疾病易感性和药物反应的决定性因素。这些成果为单体型的各项应用提供的广 阔的l 景。因此，s n p s 已成为当前人类基因组研究的重要领域( 1 0 l l j 。 但是由于技术条件的限制和认识上的差距，迄今为止，疾病的遗传研究大多 从单个基因入手，但是少数基因的多态性不能真实全面地反映出疾病发生的原 2 硕士学位论文第一章绪论 因，我们应该从整个基因组及其整体的功能状态来考虑。由于分布在人类基因组 中的s n p s 数以百万计l l 引，仅利用实验手段检测种群样本中每一个s n p 与疾病 之间的关联是不实际的。这些应用要从实验室走进实际应用，需要廉价而快捷的 单体型检测技术。不幸的是在当前的实验技术下直接测定个体的单体型所需的时 间和金钱上的花费过分昂贵，因此利用计算机技术来确定个体的单体型有极其 重要的现实意义。 我们把获取染色体上所有的s n p s 这样一个问题称为单体型检测问题。由于单 体型在生物遗传、医疗等方面的广泛应用以及测定单体型的复杂性，目前，国外 发达国家有很多学者如a c l a r k t l 3 】，d g u s f i e l d 体1 6 1 ，gl a n c i a 1 7 , i s ，vb a f r m 1 9 j ，j l i ，t j i a n g 2 m 捌和l s w a n g ，y x u 2 3 1 等，国内中科院数学与系统科学研究院的 章祥荪教授领导的生物信息学研究中心等对单体型检测中的计算问题进行了大 量研究 2 4 - 2 6 ，提出了单体型检测的各种模型和算法，这些模型总的说来主要分为 单体型组装和单体型推断两大类 2 4 , 2 7 。接下来我们首先对单体型推断问题的各个 计算模型做简单介绍，然后重点对单体型组装问题计算模型进行详细的描述和分 析。 1 1 1 单体型推断问题 利用现有的测序技术可以较容易得到个体的基因型，单体型推断问题就是如 何从群体的基因型来推断出个体的单体型。 目前关于单体型推断的主要计算模型有如下几种： l 基于节俭原则的模型 这类模型基于人群中的单体型种类是尽可能少的这种假设。c l a r k 0 3 】最先提出 了基于节俭原则的几条基本推断规则c l a r k 规则，这些规则对大部分数据简 单有效，但是有些情况下需要随机判断从而使最终的结果很有可能不是最节俭 的。 后来g u s f i e l d 1 4 ，”】基于c l a r k 规则提出t m r 模型( m a x i m u mr e s o l u t i o n ) ，他用图 论的方法证明了该问题是n p h a r d ，并把该问题转化为一个线性规划问题来求解。 b o n i z z o n i 等【2 7 1 提出了一个类似f 约s g r 模垂f l _ ( s i n g l eg e n o t y p er e s o l u t i o n ) ，l i n 等1 2 8 1 把该问题归约为3 s a t 问题，从而证明其为n p c o m p l e t e 。到目前为止尚无人提出 有效的算法来求解这个问题。 2 0 0 3 年g u s f i e l d 进一步提出了h i p p 模型( h a p l o t y p ei n f e r e n c e 咖p u r e p a r s i m o n y ) 1 2 9 j ，l a n c i a 等证明其为a p x - h a r d f l 3 1 。近来陆续有学者提出分支限界算 法【2 3 1 、整数规划算法1 3 叫及一些启发式算法【3 1 ，3 2 1 。 3 硕士学位论文 第一章绪论 2 基于进化史的模型 g u s f i e l d ，b a f n a , e s k i n 等1 6 3 3 3 4 】提出了基于进化史对单体型进行推断的模型 p p h ( p e r f e c t p h y l o g e n yh a p l o t y p i n g ) ，并提出了多项式时间的算法，但是在有数据 丢失或碱基识别出错的情况下，该问题被证明是n p c o m p l e t e l 3 5 1 。 3 基于家族的模型 这类计算模型是利用一个家族的基因组数据来推断个体的单体型。“和 d o i 2 0 - 2 2 提出t m r h c 模型( m i n i m u mr e c o m b i n a t i o nh a p l o t y p ec o n f i g u r a t i o n ) ，并 证明其是n p h a r d 。 4 基于统计的模型 。 单体型推断的统计模型以h w e ( h a r d y - w e i n b e re q u i l i b r i u m ) 假设为前提，主 要采用e m 方法( 却p 砒l 砌刀m a x i m i z a t i o n ) 3 7 】，基= = b a y e s i a n 估计和g i b b s 取样的 统计方法【3 8 1 和基于m a r k o v 链模型的方法【3 9 1 。基于e m 方法 ( e x p e c t a t i o n m a x i m i z a t i o n ) ，基于b a y e s i a n 估计和g i b b s 取样的统计方法必须假设 单体型片断在遗传中保持不变，需要对整条单体型估计频率，且无法对长的单体 型进行分析，因而有很大的局限性，而基于m a r k o v 链模型的算法时间复杂度高， 而且这些算法都是启发式算法，容易收敛到局部最优，不能获得最优解。 1 1 2 单体型组装问题 l 单体型组装问题相关概念和计算模型介绍 对于人类等二倍体生物，染色体是成对存在。一条染色体某一区域在s n p 位 点上的碱基序列叫做单体型( h a p l o t y p e ) 。而一对染色体某一区域在s n p 位点上的 混合的碱基序列叫做基因型( g e n o t y p e ) 。对于任何一个二倍体生物，都有一对单 体型。 图1 1单体型及基因型( c h r o m 表示染色体，h a p 表示单体型，g e n o 表示基因型) 单体型组装问题就是给定一组来自某对同源染色体的由d n a 测序方法得到 的d n a 片段数据，根据片段上的s n p 值组装出两条单体型【1 7 1 。一对同源染色 体在对应的s n p 位点上的值可以相同也可以不同，因此s n p 值可以用两个字符 o 和l 来表示，而不必用真正的碱基a 、c 、g 和t 以减少计算复杂度。这样d n a 4 硕士学位论文 第一章绪论 片断的数据集可以表示为在 0 ，l ， 上的一个m 疗的矩阵，叫做s n p 矩阵m 1 7 1 ， 其中矩阵m 的m 行表示m 个片断，刀列表示按在染色体上的次序从左到右的疗 个s n p 位点，m ，的值表示第i 个片断在第_ ，个s n p 位点上的取值，其值可以是 0 、l 或- ，其中- 表示片断在该位点的取值为空( 其值未能确定) ，或者说该片断在 这个s n p 位点上有一个洞( h o l e ) 。 s n p 矩阵 一 图i - 2d n a 序列片断及其对应的s n p 矩阵 对于s n p 矩阵m 的两行，如果它们在列i 上的值不相等，且都不为，则这两 行在列j 上冲突；如果这两行在所有的列上均不冲突，则这两行互相兼容。 如果m 的所有行可以分成2 个不相交的子集，且每个子集中的所有行都相互 兼容，则称m 可行。 理想的无任何测序误差过程得出的片段数据所对应的s n p 矩阵显然是可行 的，因为来自同一染色体的片段显然是相互兼容的。可是由于当前技术的局限性， d n a 测序存在错误和直接测序片断长度较短以及测试样本的污染等问题，从而 很难确定哪些d n a 片断来自哪条染色体。 l a n c i a 等对这个问题进行了研究，首先提出了下面2 个计算模型1 1 7 1 ： 最少片段删除( m i n i m u mf r a g m e n tr e m o v a l ，m f r ) ：去掉最少的片段( r p s n p 矩阵的行) 使得由该s n p 矩阵可以组装出两个单体型，即使得该s n p 矩阵可行。 最少s n p 删除( m i n i m u m5 1 7 v ：pr e m o v a l ，m s r ) ：去掉最少的s n p 位点( 即s n p 矩阵的y u ) 使得s n p 矩阵可行。 5 硕士学位论文第一章绪论 为了避免丢失片断或者位点信息，l i p p e r t 等进一步提出了第3 个计算模型【4 0 】： 最少错误修正( m i n i m u me r r o rc o r r e c t i o n ，m e c ) 或叫做m l f ( m i n i m u m l e t t e rf l i p s ) ：该模型要求修改最少的s n p 矩阵元素，使得s n p 矩阵可行。 在m e c 模型的基础上，结合基因型的信息，文献【4 l 】进一步提出以下模型： m e c g i ( m i n i m u me r r o rc o r r e c t i o n g e n o t y p ei n f o m a t i o n ) ：该模型要求修改最 少的s n p 矩阵元素，使得s n p 矩阵可行且与基因型兼容。 基因型用字符集 o ，1 ，2 上的字符序列来表示，对基因型g = 像，9 2 , ，圳，以及 两单体型h t = ( h t l ，j i l ，2 ，h i d ，h 2 = ( h 2 1 ， 易， 一，如果g i ：2 ，则令而口= 蛔= 舒；如果 纩2 ，求解办，h 2 j i j 与m e c 模型相同。 类似的，为了利用位点的可信度权值信息，g r e e n b e r g 等提出了带权的m l f 模型【4 2 】： 最少权值和翻转( w e i g h t e dm i n i m u m l e t t e rf l i p s ，w m l f ) ：给定片断数据以及 位点的可信度权值，翻转某些位点的取值( 0 翻转到1 或从1 翻转到0 ) 使得s n p 矩阵 可行，同时使得翻转的位点所关联的权值总和最小。 通过上面的介绍，我们已初步了解了这些模型。下面我们将详细介绍这些模 型所基于的理论基础，从而得出这些模型相对应的图的问题及相应的计算复杂 度，详细内容如下所示。 2 单体型组装计算模型的来源 在前一节里，我们知道如果s n p 矩阵m 的行可以分为两个不相交的子集，则 m 可行。在通常情况下，这种矩阵可行性问题可以规范化成o r ( o p e r a t i o nr e s e a r c h ) 这种自然模型：二分图问题。给定s n p 矩阵m 以及冲突图g 似目，肘的行集 肌， m 玎) 对应图g 的顶点集职v ，) ，行m i 与m 拧冲突意味着顶点1 ，与之间存在边 相连。一个6 6 大小的s n p 矩阵及其所对应的冲突图如图1 3 所示。 一个重要的发现是：矩阵m 是可行的当且仅当图g 是一个二分图。接下来的 i 扫s k i e n a l 4 3 1 给出的关于二分图的结论是几乎所有现阶段已建立的组装模型的理 论基础： 定理1 i t 叫一个图是二分图当且仅当图中所有的环的长度为偶数，或者说图 中不存在奇数长度的环。 根据定理1 1 ，自然的，为了使冲突图向二分图转化，我们需要去掉所有奇数 长度的环，也就是说，适当的去掉奇数长度环上的某些边或者顶点，使其为偶数 长度。遵循这个基本思想，现有的各种模型主要是通过切边或者移除顶点的策略 推导出来的。接下来我们将揭示如何从冲突图来推导出这些模型。 ( 1 ) 基于错误片断移除的模型 在奇环上删除一个项点等价于删除一条s n p 片断。l a n c i a 等【1 7 】根据这个思想 6 硕士学位论文第一章绪论 推导出了m f r 以及l h r 模型。 图1 - 3s n p 矩阵及对应的冲突图 ( 2 ) 基于冲突片断修复的模型 删除奇环上的一条边等价于消除两条片断上的所有冲突的s n p 位点。通过以 下两种方式可以消除两条片断上的所有冲突的s n p 位点：一种是删除这些导致引 起片断冲突的位点，另一种则是纠正这些位点的取值使之不再冲突。由删除位点 的方式可得到相应的优化模型m s r ，根据纠正位点的方式则可推导出m e c 与 w m l f 模型。 3 单体型组装计算模型计算复杂度分析 利用计算机解决实际问题时，需要研究的关键问题之一就是：所要求解的问 题是易解的还是难解的。若知道了给定问题的计算时间下界，我们就可以正确的 评价解决该问题的各种算法的效率，进而确定对已有算法还有多少改进的余地。 问题的计算复杂度可以利用求解此问题所需要计算量的多少进行衡量。一般 目前将可以在多项式时间内可以求解的问题看作时易解的问题；将在指数时间内 求解的问题看作是难解的问题。对于实际遇到的许多问题，人们至今无法准确了 解其内在的复杂性，因此只能利用分类的方法将计算复杂性大致相同的问题归类 进行研究，而对于能够进行较彻底分析的问题则尽可能准确地确定其计算复杂 性，从而获得对它的深刻的理解。 对于问题的计算复杂性分析一般需要利用某种计算机模型，包括定义该计算 模型中所用到的基本运算，其目的是为了使问题的计算复杂性分析有一个共同的 客观尺度。为了研究问题的计算机复杂度，将他们大致分为以下几类。 p 类问题：确定型图灵机在多项式表达的时间内解决的问题的集合。脱离图 灵机的概念，就在普通的计算机上看，p 类问题是指能够在多项式时间求解的判 定问题( 判定问题指只需要回答是和不是的问题) 。 n p 类问题t 非确定型图灵机上在多项式时间内找出的问题的集合。脱离图 灵机的概念，就在普通的计算机上看，n p 问题则是指那些其肯定能够在给定正 确信息下在多项式时间内验证的判定问题。 7 硕士学位论文 第一章绪论 n p 完全问题：如果判定问题z r n p ，并且对所有其他判定问题矿n p ，都 有矿多项式变换到硝记为矿力，则称判定问题t 是n p 完全的。n p 完全问题是 n p 问题中最难的问题。在n p 完全类中，如果有一个问题有多项式时间算法， 那么n p 类中所有问题也有多项式时间算法。 n p 一难问题：对于一个搜索问题矿若存在求解它的假想子问题s ，通过调用s 可以设计出解答搜索问题i t 的算法么。而且若s 是多项式时间算法，则么也是多 项式时间算法。这样问题石可多项式时间归约到问题矿，简称多项式图灵归约。 对于搜索问题石，如果存在某个n p 完全问题可以多项式时间归约到它，那么称 该搜索问题7 t 是n p 难。 在p c n p 的假设下，如果一个问题是n p 难意味其不存在多项式时间算法的， 一旦确定某个问题l 是n p 一难的，则表明它至少与n p 完全问题的难解程度一样， 但不一定恰好和n p 完全问题一样难解。 n p 完全理论的发展是理论计算机科学中的最伟大成就之一。n p 一完全理论 为难解的计算问题的研究提供了坚实可信的基础。然而，由于这些难解的计算问 题在实际应用中的重要性，人们提出了很多方法来解决这些难解的计算问题，比 如：多项式时间近似算法、随机算法和启发式算法。但是没有一个方法能满足所 有工业和应用上的需求，多项式时间近似算法只能提供近似解，而我们在某些应 用中需要的却是精确解。随机算法的成功通常非常依赖于问题实例的概率分布， 启发式算法不能保证有正式的执行效率。 l a n c i a 等【i7 j 证明了在d n a 片断数据有空隙的情况下，m f r 是n p - h a r d ；如果 一片断空隙数超过一个的话，m s r 是n p h a r d 。在d n a 片断数据无空隙的情况下， m f r 、m s r 和l h r 是多项式时间可解的。文献【1 9 】还证明了m f r 和m s r 都是 a p x h a r d 。c i l i b r a s i 等1 4 4 证明了即使在没有空隙的条件下，m l f 以及w m l f 问题 也是n p h a r d ，同时在有一个空隙的条件下该问题是a p x h a r d ，这意味着针对这 两个问题也没有好的近似算法。 在通常情况下利用计算机来解决这些问题所需的内存和c p u 资源十分巨大， 当片断数和s n p 位点数较大时，没有可行的精确算法，而诸如启发式算法、遗传 算法、动态聚类算法等近似算法的近似程度很难保证，往往不能获得最优解，因 而尽可能提高精确算法的时间和空间效率具有极其重要的现实意义。 1 1 3 单体型组装与推断两类问题比较 根据前面的介绍，单体型推断问题指根据属于一个群体的多个个体的基因型 来确定每个个体的单体型。这种方式的优点在于基因型容易获取，技术容易实现； 缺点在于推断出来的单体型不精确。而单体型组装问题则是根据个体联配的 8 硕士学位论文 第一章绪论 d n a 片段数据，组装出该个体的一对单体型。透过组装方式得到的单体型优点 在于精确，缺点在于技术实现困难( 比如要区分组装出的单体型来自哪条同源染 色体，片断长度短，存在d n a 测序错误，测试样本的污染) ，实验费用昂贵，组 装速度较慢( 对应的组合优化问题绝大多数是n p h a r d ) 。具体采用哪种方式应视给 定的生物数据特点和实验条件而定。 1 2 课题研究内容 本课题主要探索如何利用小参数技术显著降低单体型组装计算模型的时间 和空间复杂度，提出相应的参数化算法使这些n p 难问题在当前的计算资源下高 效可行；进而利用高效的算法，采用真实和模拟的生物数据对相关模型进行大量 实验，对不同的计算模型的精确度进行比较，分析影响模型精确度的原因，提出 新的计算模型来提高精度，从而为单体型的测定提供更实用的算法支持，更进一 步激发生物信息学中单体型检测领域的计算模型和算法研究。 通过对单体型组装现有的典型计算模型及其算法的研究发现国际上对此模 型和算法的研究大多只是着重于问题的形式化和计算模型的复杂度证明，然后在 抽象的计算模型上进行算法研究，很少考虑真实生物数据的特征，本课题深入研 究实际生物数据的特征，对w m l f 模型进行参数化，利用小参数技术及其它计 算技术显著降低求解这些模型的时空复杂度，提出了一个时间复杂度为 o ( n k 2 2 鸵+ m l o g m + m k l ) 的参数化算法。对于实际的生物实验数据，即使m 和刀都 相当大，本算法也可以在较短的时间得到w m l f 问题的精确解，从而填补了 w m l f 模型至今尚无实用精确算法这一空白，具有良好的可扩展性和较高的实 用价值。 参数化算法为比较不同计算模型的计算精度提供了一个高效精确的算法平 台。基于适用于不同模型的参数化算法，本课题对m s r 、m f r 、m e c 、w m i ，f 、 m e c g i 等单体型组装模型进行了大量的对比实验，采用真实和模拟的生物数据 对这些模型的单体型重构的精确度进行比较，分析影响模型精确度的原因，提出 了一系列新的评价指标，得出了各种模型的优缺点和设计计算模型的一般思路， 从而为设计新的计算模型提供了借鉴。 1 3 论文组织 论文全文共分五章： 第一章，绪论。这一章首先介绍了课题研究背景，介绍了生物信息学中单核 苷酸多态性( s n p s ) 与单体型组装问题的相关知识，同时阐述了课题的研究内容 9 硕士学位论文 第一章绪论 和研究意义。 第二章，单体型组装问题相关计算模型的比较研究。这一章介绍了单体型组 装问题相关的计算模型，首先从理论上分析了m s r 、m f r 、m e c 、w m l f 、m e c g i 等单体型组装模型的特点以及各自的优缺点，然后通过详细的实验研究得出了不 同模型的单体型重构精度，最后为设计具有更高重构精度的计算模型指明了思路 和方向。 第三章，单体型组装问题相关算法研究。针对算法所采用的关键技术对单体 型组装问题的相关算法分启发式算法以及精确算法两块进行描述。针对精确算法 中的参数化算法做了详细的介绍，同时介绍了参数理论的提出背景，相关概念及 其应用，并分析了其应用范围以及与单体型组装问题的结合可能。然后介绍了当 前针对单体型组装问题的参数化算法研究，最后对各种算法进行了比较，比较结 果表明了参数化算法的优越性。 第四章，单体型组装加权最小字符翻转问题( w m l f ) 的参数算法研究。这 一章首先介绍了w m l f 问题的研究现状，然后重点介绍了w m l f 模型的参数化 过程，在此基础上提出了pw m l f 算法。最后对pw m l f 算法与z h a o i 6 5 】提出 的动态聚类算法做了详细的实验比较与理论分析，实验结果表明，与hw m l f 相比，我们的算法有效的提高了单体型重构精度。 第五章，结束语。这一章总结了课题研究内容，分析论文的主要创新点，并 对将来进一步的研究工作提出了建议与展望。 l o 硕士学位论文第二章单体型组装问题计算模型的比较研究 第二章单体型组装问题计算模型的比较研究 上一章我们已经介绍了单体型组装计算模型的概念以及来源，通过对单体型 组装现有的典型计算模型的研究发现国际上对这些模型的研究大多只是着重于 问题的形式化和复杂度证明，然后在抽象的计算模型上进行算法研究，还没有 人对各计算模型进行横向的比较研究。为了揭示不同计算模型在不同实验环境 下的优劣和适应性，本章对单体型组装现有的5 种主要计算模型m f r 、m s r 、 m e c 、m e c g i 、w m l f 进行了大量的对比实验，对这些模型的单体型重构的 精确度进行比较，分析影响模型精确度的原因，从而揭示出各模型的内在特性， 为进一步改进单体型组装模型提供了依据。 2 1 单体型组装模型评价指标 单体型组装过程中，片断的处理分为以下3 个步骤：最初为片断生成器根据 初始单体型所生成的初始片断，然后引入了测序误差，最后是经过算法处理后所 保留的片断信息，记为尼。为了方便后面的描述，我们把由初始片断的数据集所 对应的s n p 矩阵记为m ，由尼的数据集所对应的s n p 矩阵记为p ，根据p 的片断信 息组装得到的单体型称为重构单体型。， 令一，少，一) ，记d ( 游协燃_ 删肆y ，g 、x ，- - j m l , i o m e f x ：州- ， e ( ) 【y 产1 芷：t 赫i 辩。以上定义将出现在后面对实验指标的定义中。 本文通过以下指标对上述模型进行实验比较和分析： l 不同错误率下m s r 模型的位点删除率、m f r 模型的片断删除率及m e c 、 m e c g i 、w m l f 模型的位点修正率 各模型在进行单体型重构时对片断或位点的处理具有其自身的特点。m s r 模型在处理过程中删除了片断所包含的某些位点信息，因此针对m s r 模型提出 了位点删除率的概念，即删除的单体型位点数与单体型长度的比值。m f r 模型 则删除了整个片断信息，因此针对m f r 模型提出了片断删除率的概念，即删除 的片断数占所有片断总数的比值比较而言m e c 、m e c g i 、w m l f 模型不删 除任何信息，而通过修改位点信息对片断进行处理，所以针对这三个模型提出了 位点修正率的概念，即翻转的s n p 位点数目( 矩阵p 与矩阵m 中对应位点处取 值不同的位点数目) 占矩阵m 中0 ，l 位点总数的百分比。 2 片断错误率 片断错误率【醯】是s n p 矩阵尸中的错误信息占尸中所有0 、l 信息的比率，其 硕士学位论文第二章单体型组装问题计算模型的比较研究 可表示为：e i jd ( p i ，几m i ，_ ，】) ，驴g ( p i ，巾。 3 信息丢失率 信息丢失率表明了矩阵m 与矩阵p 之间的差异率，其可表示为 e je ( p i ，】，m i ，皿，y jg ( m i ，】) 。 根据片断错误率和信息丢失率，我们可以从分析片断数据的角度来分析各模 型的特点及其对单体型重构率的影响。 4 单体型重构率 文献 4 1 】给出了其具体定义：对任意两条片断m i2 ( m i l ，m i 2 ，m 汤) 以及 m k2 ( m k l ，i n k 2 ，m 砌) ，定义h d ( m b m g ) 为片断m f 和片断m 七相冲突的s n p 位点数 目，即h d ( m i ，m k ) = 歹：1 d ( m i j ，m k j ) 。令初始单体型j l = 仍j ，h 9 ，重构单体型 h = ( 乜h 2 ) ，令r q = h d ( h 6h j 上f - j ，2 , j = j ，2 ，则单体型重构率可表示为 r r ( h ，厅) = 1 一( m i n 1 i l + 7 乏，i 2 + 乞l ，2 n ) 。 由于没有考虑到重构单体型中存在的空隙，文献 4 1 】提出的单体型重构率仅 局限于重构单体型中不存在空隙的情况。为了更精确的揭示模型特性，必须考虑 重构单体型中存在的空隙。这是因为首先在某些情况下，片断中存在空隙；其次 在某些模型进行单体型重构时，会丢失大量的信息，比如m f r 模型会删除片断 信息，m s r 模型会删除位点信息。这样导致重构出来的单体型中某些s n p 位点 的信息为，即丢失了位点信息。为此我们提出单体型空隙率来衡量重构单体型 中空隙所占的比例，其定义为重构单体型中空隙的个数与单体型长度的比值。显 然，文献【4 l 】定义的单体型重构率与单体型空隙率的差值才是各模型真实的单体 型重构率。因此在文献【4 l 】的基础上，本文扩展了对单体型重构率的定义：单体 型重构率= 文献【4 1 】定义的单体型重构率一单体型空隙率。 单体型重构率表明了重构单体型与初始单体型的近似度，是衡量各模型优劣 的标准。 2 2 实验分析 2 2 1 实验环境 由于原始的d n a 测序片段数据很难得到，大量文献利用计算机模拟真实生 物数据的特征生成测试数据集进行个体单体型各种算法的实验测试【6 引。本文采 用与上述文献相同的方法和参数来生成测试数据。模拟数据生成的方法如下：首 先随机生成指定长度的单体型，根据指定的两个单体型的差异率来随机生成另一 个单体型。然后根据指定的测序误差、片段的覆盖率、片段的最小长度和最大长 度来随机生成片段数据集。实验室的d n a 测序误差为3 5 1 6 8 1 ，片段的覆盖率 硕士学位论文第二章单体型组装问题计算模型的比较研究 为1 0 左右【5 7 1 。为了使模拟生成的片段数据能很好的反映真实情况，根据文献【6 9 】 的测试方法，首先采用著名的s h o t g u n 测序模拟片断生成器c e l s i m 生成一系列的 片断数据，生成参数设置为两个单体型的差异率为2 0 ，测序误差为