（应用数学专业论文）生物信息学中序列比较的一些问题及其算法.pdf

摘要 摘要 大规模的基因序列同基因，蛋白质表达项目产生了爆炸性增长的生物信息数据，这 些不断增长的数据导致了生物信息学的诞生。生物信息学是一门快速兴起、发展的学 科，它综合运用数据库技术、信息技术和数学与统计学方法来管理和分析生物数据。 众所周知，二十一世纪是“生命科学”与“信息科学”的世纪，而生物信息学则是生 命科学与自然科学的核心。 序列比较是生物信息学研究中一类重要的、基础的问题，通过序列比较可以挖掘 序列相似性、物种同源性等等重要的生物信息。生物信息学中的序列比较问题实质上 体现为字符串比较的问题，已经证明了许多该类问题都是组合优化n p 难问题，同时由 于生物信息学中的问题规模一般较大，因而要是能够找到快速、有效的算法解决序列 比较的问题，将有力的推动生物信息学的发展，同时给其他组合优化n p 难问题提供解 决思路。 本文主要的工作是： 1 介绍了生物信息学数据库、序列联配问题及其经典算法，然后通过分析给出了 序列联配问题的上界。 2 介绍了演化计算的过程，着重介绍了遗传算法及其过程，同时说明了遗传算法 在解决组合优化中的n p 难问题的特点。 3 针对生物信息学中一类特殊的序列比较问题c l o s e s ts l r i n g 问题。给出了该 问题的组合优化模型并设计了一种快速的近似算法- ic r a 算法。通过分析算法的 时问复杂度，说明了该算法是c l o s e s ts t r i n g 问题的一个快速的解决方法。通过与遗传 算法的对比实践，得到l c r a 算法是针对该问题快速有效算法的结论。 4 针对c l o s e s ts t r i n g 问题提出了一种全新的演化算法一概率矩阵演化算法，它 基于一个被选择概率矩阵，通过随机选择、评价、概率矩阵修正和概率矩阵变异修正 四个过程使被选择概率矩阵进化来搜索问题的解。通过算法的分析与对比实践，说明 了概率矩阵演化算法是针对该类问题的十分有效的演化算法。 5 对于c l o s e s ts t r i n g 问题的般化问题- s u bc l o s e s ts t r i n g 问题给出了该问题 的组合优化模型并设计了一种针对该问题的、特殊的遗传算法，算法的实践证明该遗 传算法设计对该问题而言是有效的。 关键词生物信息学；序列比较i 演化计算；c l o s e s ts t r i n gp r o b l e m ：l c r a 算法；遗 传算法；概率矩阵演化算法：s u b c l o s e s t s t r i n gp r o b l e m 华南理工大学硕士学位论文 a b s t r a c t t h ee x p l o s i v ei n c r e a s ei n b i o l o g i c a l i n f o r m a t i o np r o d u c e db yl a r g e - s c a l e g e n o m e s e q u e n c i n g a n d g e n e p r o t e i ne x p r e s s i o np r o j e c t s h a s g i wb i r t h t ob i o i n f o r m a t i c s b i o i n f o r m a t i c s ，ar a p i d l ye v o l v i n gd i s c i p l i n e ，i st h ea p p l i c a t i o no fc o m p u t a t i o n a lt e c h n i q u e s a n dm a t h e m a t i c sm e t h o d st ot h e n m u a g e r n c n ta n da n a l y s i so fb i o l o g i c a ld a t a a sk n o w , t w e n t y - f i r s tc e n t u r y i sa c e n t m 3 , o f l i f e s c i e n c ea n di n f o r m a t i o ns c i e n c e a n d b i o i n f o r m a t i c si st h ec o r eo ft h el i f cs c i e n c ea n dn a t u r a ls c i e n c e s e q u e n c ec o n a p ：a r i s o ni sa ni m p o r t a n ta n d b a s a lr e s e a r c hf i e mo fb i o i n f o r m a t i c s t h r o u t h s e q u e n c ec o m p a r i s o n ，w ec a l ld i s c o v e rt h ei m p o r t a n ti n f o r m a t i o no fb i o l o g y sc o m p a r a b i l i t y a n dh o m o g e n e i t y i nf a c t , t h i sk i n do f p r o b l e m sw h i c h a r en p - h a r d p r o b l e m o fc o m b i n a t o r i a l o p t i m i z a t i o nc o m ed o w nt o t h e d i s p o s a lo fs t r i n g s b e c a u s eo ft h el a r g es c a l eo ft h e s e p r o b l e m s i nb i o i n f o r m a t i c s ，i fw ec a l lf i n ds o m ef a s ta n de f f e c t i v ea l g o r i t h m s ，w ec a n p r o m o t e t h ed e v e l o p m e n to fb i o i n f o r m a t i c st oal a r g es c a l ea n dp r o v i d et h o u g h tp l a t f o r mt oo t h e r c o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e m m y w o r ki sa sf o l l o w s ： 1 t h i sa r t i c l ei n t r o d u c e st h ed a t a b a s ef o rb i o i n f o r m a t i c s ，s e q u e n c ea l i g n m e n tp r o b l e m s a n di t sc l a s s i c a la l g o r i t h r a s t h e nt h r o u g ha n a l y s i s ，w eg i v et h eu p p e rb o u n do fs e q u e n c e a l i g n m e n t 2 w ep r e s e n tt h ep r o c e s so fe v o h t i o n a lc o m p u t i n g ，e s p e c i a l l yg e n e t i ca l g o r i t h ma n d i t s p r o c e s s t h e nw ee x p l a i ns o m ec h a r a c t e r so fg e n e t i ca l g o d t h r ai ns o l v i n gc o m b i n a t o r i a l o p t i m i z a t i o np r o b l e m s 3 a st ot h ee s p e c i a ls e q u e n c ec o m p a r i s o np r o b l e m , c l o s e s ts t r i n gp r o b l e m ，w eg i v ea c o m b i n a t o r i a l o p t i m i z a t i o nm o d e la n dd e s i g n ar a p i da l g o r i t h mc a l l e dl c r aa l g o r i t h m t h r o u g ha n a l y z i n g t h et i m ec o m p l e x i t ya n d c o m p a r i n g t ot 1 1 cg e n e t i ca l g o r i t h m , w ec a l lc o m e t oac o n c l u s i o nt h a tl c r aa l g o r i t h mi saf a s ta n de f f e c t i v ea l g o f i t h r af o rc l o s e s ts t r i n g p r o b l e m 4 a st 0c l o s e s ts t r i n gp r o b l e m , w ed e s i g na n o t h e rn e w e v o l u t i o n a r ya l g o r i t h m , w h i c h i s b a s e do ne v o l u t i o n a r yo fam a t r i xo fs e l e c t e dp r o b a b i l i t i e s i ts e a r c h e st h es o l u t i o nt h r o u g h t h ee v o l u t i o n a r yo ft h em a t r i xw h i c hi sb a s e do nt h ep r o c e s s e so fs t o c h a s t i cs e l e c t e & e v a l u t i o n ，m a t r i xm o d i f i c a t i o n 。m a t r i xm u t a t i o nm o d i f i c a t i o n t h r o u g he x p e r i l u e n t s ，w ec a n s e ei ti sav e r ye f f e c t i v ea l g o r i t h mf o rt h ec l o s e s ts t r i n gp r o b l e m 5 w e p r e s e n t t h es u bc l o s e s ts t r i n gp r o b l e ma ne s p e c i a lg e n e t i ca l g o r i t t l m , w h i c hi s t h eg e n e r a l i z e dv e r s i o no fc l o s e s ts t r i n gp r o b l e m f o rt h i sp r o b l e m - t h r o u g he x p e r i m e n t s ，w e 一一 c a ns e ei ti sav e r ye f f e c t i v ea l g o r i t h m k e y w o r d sb i o i n f o r m a t i c s ；s e q u e n c ea l i g n m e n t ；e v o l u t i o n a r yc o m p t u t i n g ；c l o s e s ts t r i n g p r o b l e m ；l c r a ；g e n e t i ca l g o r i t h m ；e v o l u t i o n a r yo fm a t r i xo fs e l e c t e dp r o b a b i l i t i e s ；s u b c l o s e s ts t r i n gp r o b l e m 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名：钰印矗、 日期：矿；年莎月盯日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于， 不保密瓯 ( 请在以上相应方框内打“4 ”) 作者签名：话矿 别磁轹赤| 3 日期：，? 年二月日 日期：够年彭月膨珀 第一章绪论 i 1 课题背景 第一章绪论 伴随着科学技术的发展，人类已经可以窥探生命的秘密，甚至包括人类自身的一 些奥秘。自从人类基因组工程启动以来，每天都有大量的数据产生并存入数据库。这 些数据堆积如山，浩如烟海。这些海量的生物信息数据是用特殊的“遗传语言” d n a 的四个碱基字符( a 、t 、g 和c j 和蛋自质的2 0 个氨基酸字符( a 、r 、n 、d 、c ， q 、e 、g 、h 、i 、l 、k 、m 、f 、p 、s 、t 、w 、y 和、r ) 写成。如何存储、利用这 些数据，如何从这些数据中发掘出有用的信息等等之类的需要推动了生物信息学的产 生与发展。生物信息学是- - f 1 年青的学科，学科虽然年青，但它充满了挑战、机遇并 引人入胜吐 1 1 1 生物信息与生物信息学 1 1 1 1 生物信息的海量堆积与迅速增长 近2 0 年来，分子生物学发展的一个显著特点是生物信息的剧烈膨胀，迅速形成了 海量的生物信息库。这里所指的生物信息包括多种数据类型，如分子序列( 核酸和蛋白 质) 、蛋白质二级结构和三维结构数据、蛋白质疏水性数据等等。由实验获得的大量核 酸序列和三维结构数据被存在数据库中，这些数据库就是所谓的初级数据库( p r i m a r y d a t a b a s e s ) ：那些由原始数据分析而来的诸如二级结构、疏水位点和功能区( d o m a i n ) 数 据仞，则组成了所谓的二级数据库( s e c o n d a r yd a t a b a s e s ) 。那些由核酸数据库序列翻译而 来的蛋白质序列数据组成的蛋白质数据库，也应被视为二级数据库。生物信息的增长 是惊人的。近年来，核酸库的数据每1 0 个月左右就要翻一翻，2 0 0 0 年底，数据库数据 则达到了创记录的1 0 0 亿个记录，大量生物( 甚至包括我们人类自身) 的整个基因组序列 被测定完成或正在进行中，遍布世界各地研究实验室的高通量大型测序仪在日夜不停 地运转，每天都有成千上万的数据被源源不断地输入相应的生物信息库中。同时，由 这些原始数据分析加工而来的蛋白质结构等数据信息也被世界各地的分子生物学、生 物信息学等学科领域专家输入二级数据库中【” 3 】。 1 1 1 2 人类基因组工程 目前，生物信息学最活跃的前沿是“基因组信息学”，它正在成为基因发现和获 取、基因组密码破译并推动试验科学的强有力工具。人类基因组计划是美国科学家在 1 9 8 5 年率先提出的【1 】，旨在阐明人类基因组3 0 亿个碱基对的序列，发现所有人类所有 的基因并弄清它们在染色体上的位置，破译人类全部遗传信息，使人类第一次在分子 华南理工大学硕士学位论文 的水平上全面的认识自我。人类基因组计划1 9 9 0 年正式启动。这一价值3 0 亿美元的 工程目标是：为3 0 亿个碱基对构成的人类基因组精确的测序，从而弄清每一种基因制 造的蛋白质及其作用。人类基因组工程与曼哈顿原子弹计划同阿波罗登月计划被称为 2 0 世纪人类的三大科学工程。近些年人类基因组计划内涵和外延在不断扩展，最近， 又提出了“环境基因组学”与癌肿瘤基因组解剖计划。 对于如此大规模的、海量的生物数据，如何从中提取有用的信息，如何利用这些 信息为人类社会服务就推动了一门新的学科生物信息学的诞生1 3 1 。 1 。1 1 3 生物信息学的概念 生物信息学便是在生物信息的急剧膨胀的压力下诞生了。一般意义上，生物信息 掣1 】是研究生物信息的采集、处理、存储、传播、分析和解释等各方面的- - ( 1 学科，它 通过综合利用生物学、计算机科学和信息技术而揭示大量而复杂的生物数据所赋有的 生物学奥秘。具体而言，生物信息学作为一门新的学科领域，它是把基因组d n a 序列 信息分析作为源头，在获得蛋白质编码区的信息后进行蛋白质空间结构模拟和预测， 然后依据特定蛋白质的功能进行必要的药物设计。基因组信息学、蛋白质空间结构模 拟以及药物设计构成了生物信息学的3 个重要组成部分。从生物信息学研究的具体内 容上看，生物信息学应包括这3 个主要部分：( 1 ) 新算法和统计学方法研究：( 2 ) 各类数 据的分析和解释：( 3 ) 研制有效利用和管理数据新工具。 生物信息学最初更多地是关注数据库，那些数据库存储着来自基因组测序计划完 成的序列数据。目前生物信息学已今非昔比，它所关注的是各类数据，包括生物大分 子的三维结构、代谢途径和基因表达等等。生物信息学最使人们感兴趣的是它利用计 算方法分析生物数据，如根据核酸序列预测蛋白质序列、结构、功能的算法等。虽然 这些预测还不是非常精准，但是当可靠的实验数据还无法得到的情况下，这些预测可 以作为一盏路灯，指示你应如何开展实验。 1 1 1 4 生物信息学发展简史 1 9 6 2 p a u l i n g 提出分子进化理论 1 9 6 7 d a y h o f f 构建蛋白质序列替换矩阵 1 9 7 0n e e d l e m a n - w u n s c h 算法被提出 1 9 7 7s t a d e n 利用计算机软件分析d n a 序列 1 9 8 1s m i t h w a t e r m a n 算法出现 1 9 8 1 序列模序( m o t i 0 的概念被提t 丑( d o o l i t t l e ) 1 9 8 2 g e n b a n k 数据库( r e l e a s e 3 ) 公开。三大核酸数据库( g e n b a n k 、e m b l 和 d d b j ) 开始国际合作 1 9 8 2 凡噬菌体基因组被测序 1 9 8 3 w i l b u r 和l i p m a n 提出序列数据库的搜索算法( w f l b e r - l i p m a n 算法) 第一章绪论 1 9 8 5 快速序列相似性搜索程度f a s t p f a s t n 发布 1 9 8 8 美国家生物技术信息中心o e b i ) 创立 1 9 8 8 欧洲分子生物学网络e m b n e t 仓立 1 9 9 0 快速序列相似性搜索程序b l a s t 发布 1 9 9 1 表达序列标签( e s t ) 概念被提出，从此开仓e s t 测序 1 9 9 3 英国s a n g e r 中心迁址英国h i n x t o n 1 9 9 4 欧洲生物信息学研究所在英国h i n x t o n 成立 1 9 9 5第一个细菌基因组测序完成 1 9 9 6 酶母基因组测序完成 1 9 9 7 p s i - b l a s t ( b l a s t 系列程序之一) 发布 1 9 9 8 p h i l g r e e n 等人研制的自动测序组装系统p h r e d - p h r a p - c o n s e d 系统正式发 布 1 9 9 8多细胞线虫基因组测序完成 1 9 9 9 果蝇基因组测序完成 2 0 0 0 人类基因组测序基本完成 2 0 0 1 人类基因组初步分析结果公布 2 0 0 2 人类基因组图谱基本完成 上面列出了生物信息学最近几十年的主要事件n j 脚。这些事件大多是在“生物信息 学”( b i o i n f o r m a t i c s ) - - 词出现前便发生了。纵观生物信息学的发展历史，可将它分为3 个主要阶段：( 1 ) 萌芽期( 6 0 - 7 0 年代) ：以d a y h o f f 的替换矩阵和n e e u e m a n - w t m s c h 算法 为代表，它们实际组成了生物信息学的一个最基本的内容和思路：序列比较。它们的 出现，代表了生物信息学的诞生( 虽然“生物信息学”一词很晚才出现) ，以后的发展基 本是在这两项内容上不断改善：( 2 ) 形成期( 8 0 年代) ：以分子数据库和b l a s t 等相似性 搜索程序为代表。1 9 8 2 年三大分子数据库的国际合作使数据共享成为可能，同时为了 有效管理与日俱增的数据，以b l a s t 、f a s t a 等为代表工具软件和相应的新算法大量 被提出和研制，极大地改善了人类管理和利用分子数据的能力。在这阶段，生物信 息学作为一个新兴学科已经形成，并确立了自身学科的特征和地位；( 3 ) 高速发展期( 9 0 年代至今) ：以基因组测序与分析为代表。基因组计划，特别是人类基因组计划的实 施，分子数据以亿计：基因组水平上的分析使生物信息学的优势得以充分表现，基因 组信息学成为生物信息学中发展最快的学科前沿。p h r e d - p h r a p c o n s e d 系统软件包自 1 9 9 3 年出现，1 9 9 5 年己广泛应用于鸟枪法测序中序列的碱基识别、拼装和编辑等，是 目前人类基因组等测序计划的主要应用软件，与b l a s t 一起在人类基因组计划的研究 历史中占有一席之地f 见s c i e n c e2 0 0 1 年2 月1 6 日人类基因组专刊“ah i s t o r yo fh u m a n g e n o m ep r o j e c t ”一文) 。在此阶段，生物信息学已成为举世瞻目、竞相发展的热点学 科。g e n b a n k 等数据库中数据的增长在近十年来呈直线上升趋势( 如下图1 1 ) i 钔，这条 华南理工大学硕士学位论文 曲线很容易就使我们联想到生物信息学的发展历程，可以说，这条曲线便是生物信息 学近十余年发展的写照。生物信息学在近十余年间经历了长足的发展，并迅速成为生 命科学新的生长点。人类基因组计划的实施和生物医药工业的介入是生物信息学迅猛 发展的主要推动力f i 】。 l q 。u e n c e 暑 n l i 曩i n i d i li m q u e m 嘲p r o 协i ns t r u c t u 晰 i l - - s量1 i1 1 1知l l l | 】l i l j l l i工- i ii 薯l i d m t 瞻i n 嘲啤眦尊i l i b l i o g r a p h k ； l i i s1 l i l t 1 墨 1 置1 7 量】u i l j i i i 摹 图i - - i 各类生物信息的同步增长状况。图中依次为核酸序列( g e n b a i l k ) 、蛋白 质序列( p d b ) 、蛋白质序列( s w i s s - - p o r t ) 和文献数量增长幅度( 引i 鲁n c b ， 2 0 0 0 ) 1 1 2 生物信息学的现状与发展 1 1 2 1 生物信息学重要的研究课题 1 大规模基因组测序中的信息分析 2 新基因和新s n p 的发现与鉴定 3 非编码区信息结构分析 4 遗传密码的起源和生物进化 第一章绪论 5 完整基因组的比较研究 6 犬规模基因功能表达谱的分析 7 生物大分子的结构模拟与药物设计 8 生物信息学分析方法韵研究 9 建立国家生物医学数据库与服务系统 i o 应用与发展研究 1 _ 1 2 2 生物信息学可能面临的困难 1 政府投资不足【1 1 虽然国际上生物信息学研究在各发达国家中比较受重视，但仍有不少研究机构抱 怨政府资金投入不够。最近美国许多研究院纷纷申请要求政府加大生物信息学工具与 数据库方面的投入，而且欧洲、日本、澳大利亚在这些领域也存在着资金困扰问题， 欧洲生物信息学研究所( e b i ) 和欧洲基金会生命科学中心去年都遇到了麻烦。目前虽 然危机已经暂时渡过，但未来几年e b i 数据库和其它基础结构仍将受到资金短缺的困 扰，一致有人发出了”免费数据服务还能维持多久”的疑问。 2 来自商业机构的竞争h 1 基因组研究潜在的巨大商业利润使得国际上一批大型制药公司和化学公司向该领 域大规模的进军。世界最大制药集团之一的g i b ag e i g y 和s a n d o z 合资建立的n o v a r t i s 公司投资2 5 亿美元建立基因组研究所；g l a x o - w e l l c o m e 在基因组研究领域投入4 7 0 0 万美元，将研究人员增加一倍；s m i t hk l i n e 公司花1 2 5 亿美元扩展人基因组的顺序， 将生物信息学的研究人员从2 人增加至7 0 人，并将该公司药物开发项目中的2 5 建立 在基因组学之上。这一方面给生物信息学发展注入了生机，另一方面对那些政府支持 的不以赢利为目的的研究机构造成了巨大的压力，学术部门的瓷金投入远远不及工业 部门，其负面冲击力不可忽视。毕竟经济利益的盲目追求会导致基因组研究的片面 性，生物信息学长路漫漫，保护这些学术部门的良好发展非常有必要。 3 专业人才匮乏 1 目前该领域缺乏懂得如何利用计算机技术处理大量生物数据的生物学家，不少生 物学家只是将计算机用来打字或作为图纸的替代品。甚至出现了这样有趣的现象：制 药业、工业、农业、生物技术研究团体经常在学术机构大肆搜查那些“可疑人”，更有 甚者他们彼此问互挖“墙角”。虽然对于人才的渴求与日俱增，但全世界也仅有2 0 多 个专业人才培训中心，而且这些中心本身也处在恶性循环中，那些经培训后的人才往 往由于高薪诱惑而投身应用工业部门，导致培训教育人员越来越少，出现“断层”现 象。 1 1 2 3 生物信息学发展展望 第三次技术革命写到：“一场与工业革命和以计算机为基础的革命有相周影响 兰塑型三奎堂塑主兰苎兰苎 力的变化正在开始。下一个伟大时代将是基因组革命时代，它现在处于初期阶段。”可 见基因组研究乃至整个生物信息学的发展对今后人类社会将产生的深远影响。 信息学的商业价值十分显著。国外很多大学，研究机构，软件公司甚至政府机构 纷纷成立各种生物信息机构，建立自立的生物信息集成系统，研制这方面的软件，重 金招聘人才，期望从中获取更多的生物信息和数据加以研究和利用，缩短药物开发周 期，抢注基因专利，获取更大利润。我国如不加大资金投入力度，将来可能会花更多 的钱去购买别人的软件，使用专利基因或购买新的药物。所幸，我国也开始重视这一 学科：南、北方人类基因组中心的相继建成，北大生物城的破土动工等，标志着我国 对生物信息学的重视。我们有理由相信，我国的生物信息学在2 l 世纪将会有巨大的飞 跃。 作为计算机科学和数学应用于分子生物学而形成的交叉学科，生物信息学己经成 为基因组研究中强有力的必不可少的研究手段。在我国，生物信息学随着人类基因组 研究的展开才刚刚起步，但已显露出蓬勃发展的势头。许多科研单位已经开始或准备 开始从事这方面的研究工作。北京大学研究建立起一个e m b l 的镜像数据库，并提供 数据检索服务。在复旦大学遗传学研究所，为克隆新基因而建立的一整套生物信息系 统也己初具规模。中科院上海生化所、生物物理等在结构生物学和基因预测研究方面 也有相当的基础，中科院计算所作为我国计算机科学的顶尖机构，利用自身优势，也 开始在生物信息方面投入大量的人力物力，从事相关的研究。 生物信息学作为基因组研究的有力武器，被广泛地用来加快新基因的寻找过程， 以达到将“有用”新基因抢先注册专利的目的。在这场世界范围内的竞争中，中国科 学家以及科研资金投向的决策部门如何结合我国科研水平的现状、优势领域等客观情 况将有限的投资投入以求获得最大可能的科学研究以及商业回报，是一个无法回避的 新课题( 2 】。 1 2 生物序列比较 伴随着生物信息学的发展，越来越多的d n a 与蛋白质序列被产生，生物信息学的 一个重要研究内容就是对这些序列进行分析以提取有用的信息乃至发现隐藏的一些重 要信息。这其中一个重要的问题就是生物信息序列的比较，从比较中发现同源性等等 有用的信息。 d n a 序列可以认为是由a 、c 、t 、g4 个字符组成的字符串，这些字符串决定了 该个体或者物种的种种特性。利用比较分析，可以发现物种的同源性等信息1 4 】。 蛋白质序列由2 0 个氨基酸字符( a 、r 、n 、d 、c 、q 、e 、g 、h 、i 、l 、k 、m 、 f 、p 、s 、t 、w 、y 和v ) 写成，通过比较分析这些序列，可以发现疾病、可以挖 掘类似性等等信息。 最常见的比较是蛋白质序列或者核酸序列问的两两对比，通过比较两个序列间的 第一章绪论 相似区域与保守性位点，寻找二者可能的分子进化关系。进一步的对比是将多个蛋白 质或者核酸同时进行比较，寻找这些有进化关系的序列之间共同的保守区域、位点 等，从而探索导致它们共同功能的序列模式。此外，还可以把蛋白质序列与核酸序列 相比来探索核酸序列可能的表达框架：把蛋白质序列与具有三维结构信息的蛋白质对 比，从而获得蛋白质折叠类型的信息。 1 2 1 两序列比较 序列对比的理论基础f 2 是进化学说，如果两个序列之间具有足够的相似性，就推测 二者可能有共同的进化祖先，经过序列残基的替换、残基与序列片断的缺失以及序列 重组等等遗传变异过程进化而来。序列相似与序列同源是不同的概念，序列之间的相 似程度是可以量化的参数，而序列是否同源需要进化事实的验证。在残基一残基的对 比中，可以明显看到序列中某些氨基酸残基比其他位置的残基更为保守，这些信息揭 示了这些位点上的残基对蛋白质的结构与功能是至关重要的。但是并不是所有的残基 都一定是结构功能重要的，可能它们是由于历史的原因被保留下来，而不是进化压力 而保留下来的。因此，如果两个序列有显著的保守性，要确定二者具有共同的进化历 史，进而确定二者有近似的结构和功能还需要更多的试验与信息的支持。通过大量的 试验与序列对比分析，一般认为蛋白质的结构和功能比序列具有更大的保守性，因此 粗略的说，如果序列之间的相似性超过了百分之三十，他们就很可能是同源的。 1 2 2 多序列比较 多序列比较就是把两条以上可能有系统进化关系的序列进行比较的方法。目前序 列比较的研究一直处于不断的前进中，现有的大多数算法都是基于渐进的比对的思 想，在序列对两条序列对比的基础上逐步优化多序列对比的结果删。 华南理工大学硕士学位论文 1 3 本文的研究内容及组织 目前，生物信息学的研究如火如荼，而生物信息中的许多问题都体现为字符串问 题。序列联配是生物信息学中发现序列相似性，进而研究同源性的序列比较方法，实 质上体现为字符串的对齐比较问题。 c l o s e s ts t r i n g 问题是生物信息学中序列处理的类特殊问题，可以看作是一般序 列联配问题的特殊形式。它在生物医药、遗传研究等诸多方面都有应用。s u bc l o s e s t s t r i n g 问题则是c l o s e s ts i r i n g 问题的一般性推广。 本文针对序列联配问题，给出了上界，从而在序列进行联配之前就可确定它最好 的联配结果，进而确定其最好同源显著性，这样对于某些上界太差的序列就不需再进 行联配。 针对c l o s e s ts t r i n g 问题本文给出了组合优化模型并提出了l c r a 算法，证明了相 关的一些性质，通过同具有良好收敛性的遗传算法对比，说明了ic r a 在解决该问题 时，具有快速、稳定的特性，并能够找到次优甚至最优解。同时，本文还提出另外一 种行之有效的算法概率矩阵演化算法来解决该问题，算法的分析和实践证明了算 法对于该类问题是十分有效的。以上的两个算法构成了本文的主要研究内容。 针对s u bc l o s e s ts t r i n g 问题，本文根据该问题良好的遗传性，设计了针对问题的 遗传算法，实践证明，算法能够较好的收敛，能够找到较好的解。 第二章序列联配问题与算法 第二章序列联配问题与算法 2 1 生物信息学数据库 生物信息学涉及的数据库可大致分为二种：初级数据库和二级数据库。初级 数据库贮存原始的生物数据，如d n a 序列，由晶体衍射( c r y s t a l l o g r a p h y ) 获得 的蛋白质结构等。二级数据是在初级数据库的基础上经加工和增加相关信息，使 它们更便于特定专业人员的使用，如真核生物启动子序列库e p d 和蛋白质一般 结构或功能模体( m o t i f ) 数据库p r o s i t e 。一个数据库记录( e n t r y ) 一般由两部分组 成：原始序列数据和描述这些数据生物学信息的注释( a n n o t a t i o n ) 。注释中包含的 信息与相应的序列数据同样重要和有应用价值，这一点值得注意。在基因组规模 上的测序过程便产生了注释问题。对于那些从自动测序仪中出来的序列，我们往 往只知道它们来自何种细胞类型，而其它方面却知之甚少。如果你在确定一段未 知蛋白质序列的功能，发现一个与之匹配的序列，但该序列却没有任何有关功能 的信息时，你的研究工作便很难为继了。不同的数据库的注释质量差异很大，因 为一个数据库往往要在数据的完整性和注释工作量之间寻找一个平衡点。一些数 据库提供的序列数据很广，但这必影响序列的注释；相反，一些数据库数据面较 窄，但它提供了非常全面的注释。数据库记录的注释工作是一个动态过程，新的 发现不断被补充进去。在所有的生物信息数据库中总会有一小部分的记录( 包括 原始序列数据和注释) 是不正确的，这是一个无法避免的事实【”。 2 1 1 基因与基因组数据库 2 1 i 1g e n b a n k g e n b a n k t q 数据库包含了所有已知底核酸序列与蛋白质序列，以及与它们相 关的文献与生物学注释。它由美国国立生物技术信息中心建立，同时也由它维 护。它的数据直接源于测序工作者提交的数据、测序中心提交的大量的e s t 数 据与其他序列数据、以及同其他数据机构交换而来的数据。g e n b a n k 每天都要 与欧洲分子生物学实验室的数据库已经日本的d n a 数据库进行数据交换。目前 为止，g e n b a n k 已经收集了海量的生物信息数据，它的数据可以从n c b i 的f t p 服务器上免费下载。同时n c b i 还提供广泛的数据检索、数据相似检索以及其他 的一些相关服务，当然用户可以从n c b i 的主页上找到这些服务。 g e n b a n k 库中的数据大致来源与5 5 0 0 0 个物种，但是其中5 6 是人类的基 因组序列。每条g e n b a n k 数据记录包含了对序列的简要描述，它的科学命名、 华南理工大学硕士学位论文 物种分类名称、参考文献、序列特征表以及序列本身。序列里还包括生物学特征 的注释：编码区、转录单元重复区位、突变位点和修饰位点等等。所有的这些序 列被分在多个文件里。 2 1 1 2g e n b a n k 数据库中的数据检索 n c b i 的数据库检索系统是e n t r e z 【6 。它是基于w e b 界面的综合生物信息数 据库检索系统。e n 仃e z 的网址是：h t t p ：l w w w n c b i n l m n i h g o v e n t r e z 。利用这个 系统，用户不仅可以方便的检索g e n b a n k 的核酸数据，还可以检索来自 g e n b a n k 和其他一些数据库中蛋白质序列数据、基因组图谱数据，来自分子模 型数据库的蛋白质三维结构数据、种群序列数据集，以及一些相关的文献资料。 e n t r e z 提供使用方便的检索服务，所有操作都可以在浏览器上完成。用户可 以利用e n e z 提供的服务完成复杂的检索与查询。对于检索到的数据，用户可 以选择保存、显示甚至图形显示等各种操作。 2 1 1 3 向g e n b a n k 数据库中提交数据 用户可以将自己得到的序列数据提交到g e n b a n k 数据库。n c b i 的网址是： h t t p ：w w w n c b i n l m n i h g o v 。提交数据可以通过基于w e b 界面的b a n k i t 或者独 立程序s e q u i n 来完成。b a n k l t 的网址是：h t t p ：h w w w n c b i n l m n i h g o v b a n k i t 。 b a n k l t 是一系列表单，包括联系信息、发布要求、引用参考信息、序列来源 信息以及序列本身的信息。用户提交数据以后，会从电子邮件收到自动生成的数 据条目、g e n b a n k 的新序列编号以及完成注释后的完整的数据记录。用户还可 以修改已经发布的序列的信息。b a n k i t 只适合与测序工作者提交少量的序列，也 不适合很长的序列、e s t 序列及g s s 序列的提交。 大量的序列数据提交可通过s e q u i n 程序来完成。它能方便的编辑和处理复 杂的注释，并包含一系列的查询函数来保证序列的质量。它还用来提交系统进 化、种群和突变研究的序列。同时，s e q u i n 还可以用来做序列分析，任何以 f a s t a 或者a s n 1 格式序列作为输入的序列分析程序都可以整合到s e q u i n 下。 s e q u i n 的下载网址是：h t t p ：w w w n c b i n l m n i h g o v s e q u i n 。 2 1 1 4e m b l 核酸序列数据库 e m b l l 剐核酸序列数据库是由欧洲生物信息研究所维护的。由于同其他的一 些数据库的数据交换，它同时也是一个全面的核酸序列数据库。数据库的网址 是：h t t p ：w w w e b i a c u k e m b l 。该数据库由o r a c l e d b m s 维护，查询通过 i n t e r n e t 上的序列提取系统来完成，提交数据则可以通过s e q u i n 程序来完成也可 以通过基于w e b的w e b i n工具，工具的网址是： h t t p ：w w w e b i a c u k e m b f s u b m i s s i o n w e b i n h t m l 第二章序列联配问题与算法 2 。1 1 5g d b 基因组数据库 基因组数据库【6 j ( g d b ) 为人类基因组计划( h g p ) 保存和处理基因组图谱 数据。它的目标是建立关于人类基因组的百科全书，除了构建基因组图谱外，还 开发了描述序列水平的基因组内容的方法，包括序列变异和其他一些对功能和表 形的描述。g d b 以面向对象的模型来保存数据，提供基于w e b 的对象检索服 务，网址是：h _ t t p ：h g d b p k u e d u , c n g d b f 。 2 1 2 蛋白质数据库 2 1 2 。1p i r 和p s d p i r 国际蛋白质序列数据库( p s d ) 是由蛋白质信息资源( p i r ) 、幕尼黑蛋 白质序歹| j 信息中心和日本国际蛋白质序列数据库共同维护的国际上最大的公共蛋 白质序列数据库。这是一个全面的、经过注释的、非冗余的蛋白质序列数据库， 包含超过1 4 2 0 0 0 条蛋白质序列，其中包括来自几十个完整基因组的蛋白质序 列。所有的序列经过整理，超过9 9 的序列已经按蛋白质家族分类，一半以上 按蛋白质超家族分类。p s d 的注释中还包括对许多序列、结构、基因组和文献 数据库的交叉索引。以及数据库内部条目之间的索引，这些内部索引帮助序列帮 助用户在包括复合物、酶一底物相互作用、活化和调控级联和具有共同特征的条 目之间的捡索。 p s d 数据库含有几个辅助数据库，如基于超家族的非冗余库等。p i r 提供三 类搜索服务：基于文本的交互式检索；标准的序列相似性搜索，包括b l a s t 、 f a s t a 等：结台序列相似性、注释信息和蛋白质家族信息的高级搜索，包括按 注释分类的相似性搜索、结构域搜索g e n e f i n d 等。 网址是：h _ t t l x p i r , g e o r g e t o w n , e d u 。 2 1 2 2s w p i s s p r o t s w i s s - - p r o t t 是经过注释的蛋白质序列数据库，由欧洲生物信息学研究 所( e b i ) 维护。数据库由蛋白质序列条目构成，每个条目包含蛋白质序列、引 用文摘信息、注释等，注释中包含蛋白质的功能、转录后的修饰、特殊位点和区 域、二级结构、四级结构、域其他序列的相似性、序列残缺和疾病的关系、序列 变异体和冲突等信息。 s w i s s p r o t 尽量的减少了冗余序列，并与其他3 0 多个数据库建立了建 立交叉引用，其中包