（生物医学工程专业论文）基因芯片探针优化及核酸杂交模拟.pdf

abs tract t h e s i s t i t l e: p r o b e o p t imi z a t i o n o f g e n e c h i p a n d n u c le ic a c i d s i m u l a t i o n gr a du at e s tude nt nam e: f an g hu i s u p e r v i s o r n a me : s u n x i a o ( p r o f e s s o r ) s c h o ol n ame : s o u t h e a s t u n i v e r s i t y g e n e c h i p i s a m i c r o - m u l t i - p a r a m e t e r s b i o s e n s o r . i t c o n s t r u c t s a s e t o f m i c r o - a n a ly s i s c e l l s a n d s y s t e m s w i t h m a n y n u c l e i c a c i d p r o b e s f ix e d o n t h e s u r f a c e o f a t in y m a t r ix . s o t h e b i o l o g y e l e m e n t s s u c h a s n u c l e i c a c i d c a n b e s e l e c t e d a n d e x a m i n e d e x a c t ly a n d q u i c k l y w i t h l a r g e q u a n t it i e s . p r o b e d e s i g n i s t h e l k e y s t e p o f g e n e c h i p f a b r i c a ti o n , a n d i t i s a l s o t h e p r e p a r a t i o n f o r o t h e r s t e p s . p r o b e s d e s i g n e d w i t h t h e t r a d i t i o n a l s a m e - l e n g t h - s h i f t m e t h o d m a y c a u s e t h e m i s m a t c h b e t w e e n s e q u e n c e s e x a m in e d a n d p r o b e s , b e c a u s e t h e p r o b e s me l t i n g t e mp e r a t u r e s a r e n o t c o n s i s t e n t . i n t h i s p a p a , w e u s e t h e p r o b e - a n d - o v e r l a p p 吨 le n g t h c h a n g i n g m e t h o d t o a s s u r e t h e c o n s i s t e n c e o f p r o b e s m e l t in g t e m p er a t u r e s妙 峭u s t in g t h e l e n g t h o f p r o b e s a n d o v er l a p p i n g s e q u e n c e s . i t d e m a n d s p r o b e s w i t h f ix e d l e n g t h d u r i n g c h i p d e s ig n . h o w e v er , t h e p r o b e - a n d - o v er l a p p i n g l e n g t h c h a n g in g m e t h o d p e r f o r m s p o o r i n d e s i g n i n g f i x e d p r o b e s . s o w e b r i n g f o r w a r d a n a l g o r i t h m b a s e d o n d is t a n c e t o d e s i g n f i x e d p r o b e s . 街 d e f in i n g a n a p p r o p r i a t e d i s t a n c e , w e c a n f ind a n d d e l et e p r o b e s w h o s e m e l t i n g t e mp e r a t u r e s a r e n o t c o n s i s t e n t . t h u s w e c a n d e 吨n p r o b e s w i t h c o n s i s t e n t m e l t i n g t e m p er a t u r e s . f u r t h e r m o r e , t h e a ff e c t t o t h e a l g o r it h m s p e r f o r m a n c e b y d e f in i n g d i ff er e n t d i s t a n c e s i s d i s c u s s e d . th e p r o b e -a n d - o v e r la p p in g le n g th c h a n g in g m e th o d a n d th e o p ti m iz a ti o n m e th o d b a se d o n d i s t a n c e c a n d e s i g n a s e t o f p r o b e s w i t h c o n s i s t e n t m e l t i n g t e m p er a t u r e s , b u t o n l y o n e s e t . t a k e i n t o a c c o u n t t h e o p t im i z a t i o n o f s t e n c i l , w e u s e g e n e t ic a lg o r it h m t o d e s i g n s e v e r a l s e t s o # p r o b e s f u r th er m o r e , t h e a ff e c t t o t h e a lg o r i t h m s p er f o r m a n c e b y d e f in i n g d iff er e n t p a r a m e t e r s i s d i s c u s s e d . f o r a c h i p u s e d t o e x a m i n e a s p e c i a l g e n e , w e j u s t n e e d d e s i g n s p e c i a l p r o b e s a c c o r d i n g t o 工 工 工 t h e c h a r a c t e r i s t i c s e q u e n c e s o f t h e g e n e . c h a r a c t e r i s t ic s e q u e n c e i s a u n i q u e s e q u e n c e j u s t a p p e a r i n g i n t h i s g e n e . i n t h i s p a p e r , a ft e r d e s i g n i n g p rob e s w it h c o n s i s te n t me l t i n g t e m p e r a tu r e s , w e u s e d y n a m i c p r o g r a mm i n g a l g o r i t h m t o d o s imi l a r i t y s e a r c h t h r o u g h d a t a b a s e f o r t h o s e s e g m e n t s ma t c h i n g t h e p r o b e s , s o w e c a n p i c k u p t h e s p e c i a l p r o b e s . u s u a l l y w e v a l u e t h e a c t u a l e ff e c t o f a c h i p b y h y b r i d i z a t i o n e x p e r i m e n t s a f t e r d e s i g n . b u t i t c o s t s m u c h . i n t h i s p a p e r , w e t ry c o m p u t e r s im u l a t io n o f n u c l e i c a c i d h y b r i d i z a t i o n u s in g m o l e c u l a r d y n a m ic m e c h a n i c s . a s f o r t w o n u c l e i c a c i d c h a i n s m a t c h i n g e a c h o t h e r , t h e y c a n b e r e n a t u r e d a ft e r d e n a t u r e d . b u t i f t h e r e i s a m i s m a t c h i n t w o c h a i n s , i t s d i ff i c u l t f o r t h e m t o r e p 的 i r e. ke y wo r d s : g e n e c h i p d y n a 面c p r o g r a m mi n g c h a r a c te r i s ti c s e q u e n c e p rob e o p ti mi z a t i o n g e n e t i c a l g o r i t h m mo l e c u l a r d y n a m i c s i m u l a t i o n i v 东 南 大 学 学 位 论 文 独 创 性 声 明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含 其他人已 经发 表或撰写过的 研究 成果， 也不包含为获得东南大学或其它教 育机构 的学位或证书 而使用过的 材料。 与我一同 工作的同 志对本研究所做的任何贡献均 己在论文中作了明确的说明并表示了谢意。 研究生签名: 哗 日 期 渔 率 担 且 - 东 南 大 学 学 位 论 文 使 用 授 权 声 明 东南大学、中国 科学技术 信息 研究所、 国家图书馆有权保留 本人 所送交学 位 论文的复印件和电 子文档， 可以 采用影印、 缩印或其他复制手段保存论文。 本人 电子文档的内 容和纸质论文的内 容相一致。 除 在保密期内的保密论文外， 允许论 文被查阅和借阅， 可以公布 ( 包括刊登) 论文的全部或部分内容。 论文的公布 包 括刊登)授权东南大学研究生院办理。 研 “ 生 签 “ : 49日 期 : ，刁. t. z r 绪论 第一章绪论 1 . 1基因组学 1 9 8 6 年美国 科学家t h o m a s r o d e r i c k 提出了 基因 组学( g e n o m i c s ) ,基因组学是指对 所有基因进行基因组作图 ( - 括遗传图谱、物理图谱、 转录图 谱) ， 核昔酸序列分 析， 基因定 位和基因功能分析的一门 科学。 因此， 基因组 研究应 该包括两方面的内容:以 全基因 组测序 为目 标的结构 基因 组学 ( sttu c h u a l g e n o m ic s ) 和以 基因功 能鉴 定为目 标的功能 基因 组学 ( f u n c t i o n a l g e n o m ic s ) . 结构墓因组学代表基因 组分 析的 早期阶段， 以 建立生物体高分辨率遗 传、 物理和转录图 谱为主。 功能基因组学 代表基因分析的 新阶段， 是利用结 构基因组学提供 的 信息 系 统 地 研 究荃 因 功 能 ， 它 以 高 通量 、 大 规 模 实 验 方 法以 及 统 计与 计 算 机 分 析 为 特 征 。 1 9 9 。 年开始的 人类基因组计划( h u m a n g e n o m e p r o j e ct , h g p ) 已取得了巨 大成就，同 时模式 生物( m o d e l o r g a n is m s ) 基因 组计划也 在进行，并 先后 完成了 几个物种的 序列分析. 就人类基因组来说，得到序列仅仅是第一步，后一步的工作是所谓后基因组时代 (p o s t-g e a o m e e r a ) 的 任务 ， 即 收 集 、 整 理 、 检 索 和 分 析 序 列 及 其 表 达 的 蛋白 质 结 构 与 功能 的 信息， 找出 规律。 生物信息学将在其中 扮演至关重要的角色。 而基因芯片的应用将为上述研 究提供最 基本和必要的信息及依据， 将成为基因 组信息学研究的主要技术支撑。 1 . 2生物信息学 生物信息学是 8 0年代末随着基因 组测 序数据迅猛增加而逐渐兴起的一门 新的学科领 域。 随着生物学和医学的迅速发展， 特别是人类基因 组计划的顺利推进， 人类己 获得大量的 生物分子数据， 并且生 物分子数据的积累速度在不断地增加。 这些数据具有丰富的内涵， 其 背后隐藏着人类目前尚不知道的生物学知识。 充分利用这些数据， 通过数据分析、处理，揭 示这些数据的内涵， 得到对人类有用的信息， 这将是生物学家和数学家所面临的一个严峻的 挑战。 生物信息学是为迎接这种挑战 而发展起来的一 个新型交叉 学科。 生物信息数据量大并 且复杂 ( 序列、结构、功能) ，靠人工难以完成数据处理和分析的任务，更谈不上发现隐藏 东南大学硕士学位论文 在这些信息之中的内在规律。同时，对于生物分子信息，仅靠某一学科的专家，也无法进行 分析研究，因此， 在生物信息学研究领域中， 要求生物学家、 数学家和计算机科学工作者协 力合作， 发展新的分子生物学计算理论和方法， 运用 先进的计算 机技术收 集、 存储、 集成和 分析处理生物信息。 生 物信息学的发展将深刻揭示生物界遗传信息的本质， 使人类彻底了解、 掌 握遗传信息 的编码、传递及表达，从而加快人类了解自身的进程。 就实用意义而言，生物信息学有助于 了 解疾病的 机理， 帮助确定新药作用的目 标。 揭示人类及 重要 动植物种类的基因 的信息， 继 而开 展生物大分子结构模拟和药物设计， 是当今国 际上正在迅速 发展的自 然科学领 域最重大 的课 题之一，不仅对认识生物体和生物信息的起源、遗传、 发育与 进化的 本质有重要惫义， 而且 将为人类疾患的 诊治开辟全新的 途径，还可为动植物的 物种改良 提供坚实的理论基 础。 目 前生物信息学的 研究对 象主 要是d n a序列和蛋白 质序列， 其主要任务是分析研究序 列数据中所含的 各种信息， 特别是d n a序列中的 遗传及调控信息， 研究蛋白质 序列与结构 及功能的关系。 1 .3基因芯片 基因芯片技术是随着 “ 人类基因组计划”的进展而发展起来的， 它是 9 0年代中期以来 影 响最深远的重大科技进展之一， 它是融微电 子学、 生物学、 物理学、 化学、 计算机科学为 一 体的高度交叉的新技术飞具有重大的基础 研究价值，又具 有明显的 产业化前景。 1 .3 . 1 基本概念 基因芯片 ( g e n e c h i p ) 也叫d n a芯片、 d n a微阵 列( d n a m i c r o a r r a y ) . 寡核昔酸阵列 ( o li g o n u c l e o t i d e a r r a y ) ， 是指采用原位合成 ( in s i t u s y n t h e s i s ) 或显 微打印 手段，将 数以 万计的 d n a探针固化于支持物表面上，产生二维 d n a探针阵列，然后与标记的样品进行杂交， 通过检测杂交信号来实现对生物 样品快速、 并行、 高 效地检测或医学诊断，由 于常用硅芯片 作为固相支持物，且在制备过程运用了计算机芯片的制备技术，所以称之为基因芯片技术。 绪 论 1 .3 .2 基因芯片的应用 (1) 测序:基因芯片利用固 定探针与样品进行分子杂交产生的杂交图谱而排列出待测 样品的 序列，这种测定方法快速而具有十分诱人的前景。m a r k c h e e 等用 含 1 3 5 0 0 0 个寡核 营酸探针的阵列测定了全长为 1 6 . 6 k b的人线粒体基因组序列， 准确率达 9 9 %. ha c 。等用含 有4 8 0 0 0 个寡核昔酸的高密度微阵列分析了 黑猩猩和人b r c a i 基因序列差异， 结果发现在 外显子 1 1 约 3 .4 k b长度范围内的核酸序列同源性在 9 8 .2 %到 8 3 . 5 %之间，提示了二者在进 化上的高度相似性。 ( 2 )基因表达水平的检测: 用基因芯片进行的表达水平检测可自动、 快速地检测出成 千上万个基因的 表达情况。 s c h e n a 等采用拟南芥基因组内 共4 5 个基因的c d n a微阵 列 ( 其 中 1 4个为完全序列，3 1 个为e s t )检测该植物的根、叶组织内这些基因的表达水平，用不 同颜色的荧 光素 标记 逆转录产 物后分别与该 微阵 列杂交， 经激光共聚焦显 微扫描， 发现该植 物根和叶组 织中 存在2 6 个基因的 表达差异， 而参与叶绿素合成的c a b 1 基因在叶组织较根 组织表达高5 0 0 倍。 s c h e n a 等用人外周血淋巴 细胞的。 d n a文库构建一个 代表 1 0 4 6 个基因 的。 d n a微阵 列， 来检测体外培养的t 细胞对热休克反应后不同 基因 表达的差异， 发现有5 个基因 在处理后存在非常明 显的高表达。该结果还用荧光 素交换标记对照和处理组及 r n a 印 迹方法证实。在h g p 完成之后，用于植测在不同生理、病理 条件下的 人类 所有基因 表达 变化的基因组芯片为期不远了。 ( 3 )基因诊断: 从正常人的基因组中分离出d n a与d n a芯片杂交就可以得出标准 图 谱。从病人的基因 组中分 离出d n a与d n a芯片杂交就可以得出病变图谱。通过比 较、 分析这两种图 谱， 就可以得出 病变的d n a信息。这种基因芯片诊断技术以 其快速、高效、 敏感、经济、平行化、自 动化等特点， 将成 为一项现代化诊断 新技术。 例如， a 丙n e t r i x 公 司，把 p 5 3 基因 全长序 列和已 知突 变的 探针集成在芯片上，制成p 5 3 基因芯片，将在癌症 早期诊断中 发挥作用。 又如， h e l l e r 等构建了%个基因的c d n a微阵， 用于检测分析风湿 性关节炎 ( r a ) 相关的 基因，以 探讨d n a芯片在感染性疾病诊断 方面的 应用。 现在， 肝炎 病毒检测诊断 芯片、 结核杆菌耐药性检测芯片、 多 种恶性肿瘤相关病毒基因 芯片等一系列诊 断芯片 逐步开 始进入市场。基因诊断是 基因芯片中 最具 有商业化价值的应用。 ( 4 ) 药物筛选: 如何分离和鉴定药的有效成份是目 前中药产业和传统的西药开发遇 到的重大障碍， 基因芯片技术是解决这一障碍的有效手段，它能够大规模地筛选药物的有效 成份， 能够从基因水平解释药物的作用机理， 即可以利用基因芯片分析用药前后机体的不同 东南大学硕士学位论文 组织、器官基因表达的差异。如果再用mr n a构建c d na表达文库，然后用得到的肤库制 作肤芯片， 则可以 从众多的药 物成分中筛 选到 起作 用的 部分 物质。 生物芯片技术使得药物筛 选，靶基因鉴别和新药测试的速度大大提高， 成本大大降低。基因芯片药物筛选技术工作目 前刚刚起步， 美国 很多制药公司已开始前 期工作， 即正 在建立表达谱数据库， 从而为药物筛 选提供各种靶基因及分析手段。 此外，基因 芯片在 新基因发现、药物基因组图、中药 物种鉴定、 d n a计算机研究等方 面都有巨大应用价值. 1 .4生物信息学在基因芯片中的应用 图i s基因芯片数据流 随着基因芯片需求和应用的不断增 长， 基因 芯片及其相关的研究内 容将会越来越丰富， 基因芯片的应用己 产生或即 将产生大量 的生物分子信息。 生物信息学是分析处理生物分子信 息、 揭示生物分子信息内 涵的一种技 术， 它在基因 芯片研究与应用中 起着重要的作用。 从确 定基因芯片检测对象到 基因芯片设计， 从芯片检测结果分析到实验 数据管理和信息 挖掘， 无 不需要生物信息学的 支持和帮助。 通过合理的 芯片设计和芯片优化， 可以 提高基因芯片获取 生物信息的 效率和可 靠性， 而通过芯片实验数据分 析， 可以 得到 更多 的、 反映生物分子 作用 机理的信息。图 1 - 1 是基因芯片的数据流程图，该图反映了基因芯片数据的流向，更重要的 绪 论 是反映了生物信息学在基因芯片中的作用。 对于一个具体的高密度基因芯片研究或应用而言歹 主 要的 信息学 工作包括确定芯片待检 测的目 标序列、芯片设计、 检 测结果 分析和 数据管理。 首先， 通过核酸数 据库查询和序列分 析，确定基因芯片所要检测的目标对象。 然后根据芯片具体的功能要求，采用特定的方法进 行探针设计和布局，并进行芯片优化， 将设计结果存放到数据库之中。根据芯片设计结果制 备芯片， 进行杂交实验。 最后采集并 处理芯片 杂交后的荧光图像， 结 合数据库中的芯片描述 ( 各探针的 序列和探针在芯片 上的 位点) 确定基因芯片 检测结果， 井对 检测结果进行可靠性 分析。 将经过处理的检测数据 送入数据 库，以 便于 今后的利用。图1 - 1 中有一 个综合模块， 即“ 生物分子信息管理、 数据挖掘和可视化” ，其 主要目 的是将芯片 所检测到的信息与已 知 的 生物分子信息相结合， 通过 数据关联分 析， 发现数据之间的联 系， 挖掘隐含在数据中的 新 生物学知识， 并以直观理解的图 形方式显示分 析结果。 下面着重讨论生物信息学在确定基因 芯片检测目标、芯片设计和实验数据分析与管理三个方面的应用。 1 . 4 . 1 确定待检测的目 标序列 对于一个具体的基因芯片， 首先根据基因芯片 类型和所要解决的问 题， 利 用生 物信息学 方法确定芯片所要检测的目标序列 。最直接的方法是查询生物分子信息数据库 ，如 g e n b a n k ， 取得相应的d n a或m r n a序列数据， 直接作为基因芯片探针设计的参照目 标序 列。 这种方法适用于再测序或研究基因多态 性的 芯片， 根据参照序列设计一系列探针， 以 检 测序列每个位置上可能发生的变化。 若一个基因 芯片的目 标是检测大且特定的 基因， 则 检测对象不需要是整个基因序列， 只 要是代表该 基因的一小段 特征序列即 可。 所谓 特征序列就是一段高度特异的 序列， 独一无二， 它 代表一个基因。 从一个给定的序列中 任选 一段并不一定是 特异的序列片段， 因为 序列之间 可能存在着相似性， 必 须通 过数据库的 序列搜索比 较， 才能 确定一段序列是否是 特异的。 在 这种情况下， 首先从核酸数 据库中 取得基因序 列， 然后通过序列比对分析， 找出 其特征序列， 作为探针设 计的参照序列。 序列比对分析是生 物信息学中最常用的方法， 可以直接利用现 有 的软件。生 物信息学中常用的 核酸序列搜索比 较算法 是 b l a s t 。上述确定目 标序列的方 法 多用于基因检测型芯片或基因表达型芯片。 东 南 大 学 醒 主塾丝 主一 一一一 1 .4 . 2 高密度基因芯片的设计 芯片设计的目 的在于; 通过设计， 提取更 多的 生物分子信息， 并提高信息的可靠性。 高密度基因芯片设计包括寡核昔酸探针设计、 探针布局和芯片优化。 根据参照序列设计探针， 尽可能使最终芯片的荧光检测图 像中 完全互补杂交信号突出，提高基因芯片检测的可靠性。 芯片优化是指在设计后续阶段对芯片 制备过程进行优化，如减少制备芯片所需要的掩膜板， 精简探针合成环节。 在芯片设计的不同 阶段，都 要用到信息学中的优化方法，如探针优化、 布局优化及芯片优化。 各种基因芯片的功能不同， 相应的芯片设计要 求和设 计方法也有所不同， 必须根据其体 的芯片功能采用不同的 设计方法。 根据我们的经验，从信息学角度 提出以 下设计准则: ( 1 )互补性:探针与待检测的目 标序列片段互补: ( 2 )敏感性和特异性:既 有较高的 敏感性，也 有较高的特异性，要求探针仅对特定目 标序 列片段敏感，而对其 他序列不产生杂交信号; c 3 ) 容错性: 通过 探针设计，提高基因芯片检测的 容错 性， 常用的方 法是 使用冗余探针: ( 4 )可靠性:通过探针设计，提高基因芯片 检测的可 靠性; ( s )可控性:在基因芯片上设置质7a监控探针，以便于监 控墓因芯片 产品 的质且; ( 6 ) 可读性:通过探针布局， 使得最终的杂交检测图像便于观察理解， 如将检测相关基因 的 探针放在芯片上相 邻的区域。 在 探 针 设 计 方 面 ， 为 了 提 高 芯 片 检 侧 wt 靠 性 ， 我 们 提 出 一 种 优 化 设 计 方 法 。 该 方 法 的 基本思想是通过动态 调节各个 探针的 长度及探针之间 的覆盖长度， 使所设计的各个 探针的解 链温 度 t m 最大程度地保持一致， 从而有效地提高对 碱基 杂交错配的辨别能 力， 提高基因芯 片检测结果的可靠性. 我们采用生 物信息 学中 常用的动态规划算法进行优 化， 以 各探针具有 相近解链温度作为优化目 标， 筛选并 优化组 合各候选探针。 在优 化组合时 要求各探针的 长度 和相邻探针之间 的交叠长 度满 足给定的 约束条件， 经过优化组合以后得到 一组覆盖目 标序列 的探针 。 对于高密度基因芯片， 往往需要同时 检测多个目 标序列。 只要将上述基 本方法稍作改进， 就可以设计出多个目 标序列的探针。 对于表达分析型基因 芯片， 一 般是设计多 组探针以 监控多个基因的表达水 平， 并且使同 一块芯片所 能s 的 基因越多 越好。 要求探针之间相互独立， 尽可能不重叠 或少重叠， 以提 绪 论 高探针的 特异性。设计的关键是探针冗余，用不同的探针检 测同 一个目 标序列的不同区 域， 这提高了信号噪声比，同时也提高了定量检钡目标序列的精确程度。另一种冗余来 自于错配 检测探针， 所谓错配检测探针与正常探针基本相同， 仅仅是 探针的中心位置有一个碱基替换， 利用这种探针用来辨别完全匹配与非完全匹配 基因芯片设计的结果是形 成芯片合成方 案和步 骤， 产生制 作掩膜板的 方案。 为提高基因 芯片制作效率，需要对芯片设计结果进行优化。通过优化减少制作芯片所需的掩膜板个数， 减少芯片上寡核昔酸探针的循环合成次数。 1 .4 .3 基因芯片检测结果分析及数据管理 基因芯片与经过荧光标记的样品杂交以 后， 产 生荧光图 像。 用图 像扫描仪器捕获芯片上 的 荧光图像， 并对图 像进行处 理， 去 除图 像上的污点以 及其它形 式的 嗓声。 由 于芯片 制备的 原因， 每个芯片单元的大小和 位里可能 会发生变化， 这影响解释芯片图 像。 自 动对准是芯片 图 像处理中 的一个关键问题，需要 用图 像分割技术 来解决该问 题。 分析经过处理的 荃因芯片荧光图像， 根据芯片的功能给出 检测结果。 如果 芯片检测的目 的是测定样本序列， 则需要根据芯片上每个探针的杂交 结果 判断样本中是否含 有对应的互补 序列片段， 并 利用生 物信息学中的片段组装算 法连接 各个片段， 形成更长的目 标序列。 片 段 组装算法有基于片段硕盖图的贪婪算法和非循环子图方 法。 如 果芯片检测的目 的是进行序列 变 异 分 析， 则 要 根 据 全匹 配 探 针以 及 错 配 探 针 在 基因 芯 片 对 应 位 置 上 的 荧 光信 号 强 度 ， 给 出 序列变化的位点， 并指明 发生什么变化。 如果芯片检测的目 的 是进行基因 表达分析， 则需要 给出芯片上各个基因的 表达图 谱， 定量描述 基因的 表达水平。 进 一步的分 析还包括根据基因 表达模式进行聚类， 寻找 基因 之间的 相关性， 发现协同工作的基因。 基因芯片是一个非常复 杂的系统， 包 括许多 环节， 由 于目 前技术上的限制， 在基因 芯片 制备、杂交及检测等方面都可能出 现误差，芯片检 测结 果并非1 0 0 % 可靠。 因此，必须对芯 片检测结果作出 可靠性的评价。 可靠性分 析可以从两个方面进 行， 一是根据实验统计误差( 如 探针合成的 错误率、全匹配探针与错配探针的误识率 等) ，分析 基因芯片 最终实验结果的可 靠性。 二是对基因 芯片与样 本序列杂交过程进行分子动力学研究， 建立芯片杂交过程的 计算 机仿真实验 模型， 以 便在制作芯片之前分析所设计芯 片的 性能， 预 测芯片实验结果的可靠性。 基因芯片实验将产生大量的数据， 如何有效地管理这些数据是生物信息学所面临的一个 东南大学硕士学位论文 挑战。 数据管理的目 的是为了更好地利 用和 共享数 据。 基因芯片产生的数据主要是基因 表达 数据。目前 在国际 互连网 上有许多公 共基因表达数据库， 如欧洲生物信息学研究所 e b i 建 立的a r r a y e x p r e s s 数据库。 基因 组信息是相互关联的， 不仅要建立基因芯片数据库， 还要与 其它生物分 子数据库、 分析工具集 成在一 起， 建立交 叉索引 ， 使基因芯片数据成为更 有价值 的生物学资 源。 在此基础上， 引入数据挖掘技术， 进行深层次的数据分析， 从大量的基因芯 片实验数据及其他相关实验数据中提取隐含的生物学信息，并上升为生物学知识。 咭 . 5本课题的任务及成果 ( i ) 任务: 影响基因芯片检测可靠 性的一个关 键因 素就是 特侧序列与探针的杂交错配。 杂交错配可能导致基因芯片检测的 误判断，而杂 交错配是由于 各探针 杂交解链温度 ( t . ) 不同引起的。 本课题的 任务就是要研究并实现探针设计的优化算 法，设计出t m 值一致的探 针， 从而提高芯片检测的 可靠 性。 为了 保证探针的特异性， 我们对与 探针互补的 序列片段进 行数据库的相似性搜索。 最后， 为了 评估芯片的设 计效果， 要对探针及检 测序列进行杂交模 拟。 ( 2 )成果: 利用变长变理盖法设t 出了 杂交条 件一致的变长探针; 提出了基于距离的优化 算法，设计出了 杂交条件一致的定长探针; 利用遗传算法，设计出了一组 杂交条件 一致的定 长探针集合: 利用动态规划算法，实 现了对 特异性 探针的 数据库筛选; 将上述算法在 l i n w c 服务器上编程实现，并利用 c g i 技术提供网络计算 ( h tt p :1/2 0 2 .1 1 9 .1 8 .1 4 8 /d rv l a b / ) ， 供 局 域网 内 的 用 户 访问 ; 模拟了 芯片的 探针杂交，对两条全配序 列的模拟取 得了 一定的 效果。 ( 3 )论文结构: 第一章: 简要 介绍基巴组 学、 生物信息学、 基因芯片、 生 物信息 学在芯片设计中的 应用，并说明了 本次课题的 任务及成果。 第二章: 介绍现有的 探针设计、序列比 较的方法，并对分子动力学作了简要介绍。 第三章: 介绍并实现了 变长变覆盖算法， 对于给定的目 标序 列， 设计出杂交解链温 绪 论 度一致的变长探针。 第四章:对于设计解链温度一致的定长探针，研究并实现了基于距离的优化方法， 并对算法作了改进。 第五章: 利用遗传算法设计一组解链温度一致的定长探针集合， 研究了不同参数对 算法性能的影响。 第六章: 对基本的 动态规划 算法进行了改 进， 通过数据 库的 相似性搜索来筛选出特 异性的探针。 第七章: 初步尝试了用计算机模拟芯片杂交， 对两条全配序列的杂交取得了一定的 效果。 第八章:对本次课题作出总结，并对后续工作提出展望. 东南大学硕士学位论文 第二章探针设计相关算法及分子模拟 从基因芯片设计到制作微印章， 从探针合成、 探针定位到与样本杂交， 直到最终检测杂 交信号 并判断 样本中是否含有目 标序列， 这是一个完整的系统过程， 芯 片设计是其中关键的 一步， 是整个芯片制备过程的前提保证， 由它 产生后继的印章设 计方案和探针合成方案。因 此芯片设计 将直接影响所制备芯片的 信息量、 准 确性、 可靠性和容错性。 一个优秀的芯片设 计方案不仅能有效地减少所需印章的 个数和缩减探 针合成的次数， 并且能 够保证所有探针杂 交条件尽量一致， 同时还应有助于避免探针发夹结 构的形成， 从而大大降 低了碱基错配的 可 能性， 最终 为杂交检测信号的质量和可靠性提供保证。 芯片设计包括两 个方面: 探针生成方 案的设计 和探针布局方案的设计。 前 者是指 根据目 标 序列 如何生 成探针的问 题， 后者指探针 生成之后如何在芯片布局的问题。 本章第一节介绍了 用于探针设计的等长移位法， 并指出了 其缺陷。在后面的第三、四、 五章中我们将介绍探针设计的优化算法。 对于检测特定基因的 芯片， 我们要设计出 特异性的探针来提高芯片检测的特异性。 而筛 选特异性的探针， 就要用到序列比 对算法. 本章第二节介绍了序 列比 对常 用的b l a s t算法 以及动态规划算法。 在第 六章中， 我们 对基本的动态规划算法作了 改进， 用于筛选特异性的 探针。 本章第三节简要介绍了分子模拟的基础知识， 在第七章中我们将 利用这些知识来模拟核 酸的杂交过程。 2 . 1等长移位法 探针是基因芯片的基本信息存储单位和基本功能单位， 所以探针设计是芯片设计的关键 环节。 探针设计实际 上是研究目 标序列如何截取生成对应的 探针阵列。 设计思路应遵循以 下 原则: ( 1 ) 探针长度的选 择，一 般变 化范围 为 1 6 - 2 5 b p . ( 2 ) 相邻探针覆盖长度的 选取方式， 应综合考 虑基因芯片容纳的信息量 和容错性 过小的探针覆盖长度可能导致杂交信号不足，造成探针组装目 标序列的困难。 探针设计相关算法及分子模拟 ( 3 )保证排列于芯片上的所有探针的 杂交条件尽量一致，以 减少芯片的杂交错配。 ( 4 )从提高芯片制备效率角度而言，设计方案应尽量减少制作芯片所用的掩模版 ( 或 微印章)的个数。 目前探针设计方法主要是等长移位法。 该方法按照目标序列从头到尾的顺序依次取一定 长度的互补核昔酸序列作为探针， 相邻探针序列之间覆盖的核昔酸数 目 恒定， 如图2 - 1 所示。 3i!y o h ap 7 0摆1 g 粼巍黑叙g e.g c.7c: ic g s t a 1 l3c a c c -i at c b a g c t il c c r i- t a c ( 9a c t g c g a 0 ti ta t a c g t a c-t 了 c 令八g c 了 八心 o w l t 六 cq ? s c r t r c t ac 1 i c cp 人cq . 口 丁 c 9cq 八口 心 c s r - r a ir, ac 0 4 3 a o m at .a c o八 c t c 7 c 3 八0 已 3 么 了人口 ( 朴1人c i 图2 - 1等长移位法示意图 该方法的特点是序列信息 覆盖全面， 设计原理简单。 但是由 于难以保证所设计探针的解 链温度的一致性，可能会引起杂交错配，影响杂交结果的准确性。 2 .2序列比对算法 2 .2 . 1 b l a s t ， 算法 b l a s t是 基本的局部对比 排列搜索s具 ( b a s i c l o c a l a l i g n m e n t s e a r c h t o o l ) 的简称。 在 进行数据库搜索时， b l a s t返回 一个高 得分 的相似片段对列表，每一个片段是一个序列 的 子串。 给定两 个序列， 属于它们的一个片段对是一对等长的片 段。 由于是 等长的片段， 所 以两者之间能够形成无空白的对比排列。 对于这样的局部对比排列， 可用打分函数或打分矩 阵 进行打分， 但由于没有空白 ，所以不需 要对空白 打分。 给定一 个查询 序列，b l a s t返回 所有查询序列与 数据库 序列得分超过某个域值 s 的片 段对。 域值 5可以由用户设定， 但程序有一个缺省的推荐值。由于在对比排列过程中不考虑 空白，所以b l a s t运行速度非常快。 两个序列的最大片段对 ( ms p , m a x i m u m s e g m e n t p a i r )就是最高得分的片段对。这个 得分是序列相似性的度量。 在进行序列两两比较之前，b l as t首先寻找一颗 “ 种子” ，它是两个序列之间的一个非 1 1 东南大学硕士学位论文 常 短的片段对。 种子可以向 两个方向 扩展， 直至达到扩展的最大可能的得分。 程序对何时停 止扩展有一个判断准则，即当扩展的得分低于某个计算的下限时，停止扩展。 是正确的扩展 但未被发现的可能性非常小。 b l a s t的计算过程分为三个阶段: ( 1 )收集一系列高得分的串，形成高得分单词表; ( 2 )搜索种子; ( 3 )扩展种子。 具体的 算法步骤取决于序列搜索的类型，即是d n a序列搜索， 还是蛋白 质序列搜索。 对于蛋白 质的 搜索，单词表由 所有w个字符构成的单词组成，并且 这些单词与查询序 列的一些长度为w的 单词比 较得分超过t 。 这里， w和t 是程序的两个参数，对于蛋白 质 序列搜索推荐的 w值 ( 即 种子的长度) 为 4 。 这一步所得到的高得分单词表实际上是一些 候选的种子。 接下来一步是扫描 数据， 搜索那些处于单词表中 的种子。 有两 种方法 可用于 扫描数据库。 第一种方法是将这些单词组 织在一个哈 希表 ( h a s h ) 中， 然后对于数据库中的 每个长度为w 的单词， 取 它们在哈希表中的 对应下标， 并将它们与哈 希表该位置上的所有单词 ( 高 得分单 词表的一 部分)进行比较.若 相同则找到一颗种子。 第二种方法是利用有限自 动机搜索种子. 有限自 动机具有一系列的 状态和状态转换操 作， 它起始于一个固定的 初始状态。 对于字母 表中的 每个字符， 有一 个转换操 作。 具体实现 时， 将高 得分单词 表作为 输入， 构造一 个自 动 机， 该自 动机可以 根据状态 和转换操 作， 识别 单词表中的 单词， 因而可 用于 扫描 数据库， 搜索种子。自 动机只需构 造一次。 这种搜索的速 度相当 快 ( 关于自 动机技术可参阅 有关编译原理的书籍) 。 最后一步扩展过程比较直观。当扩展时的得分低于该扩展前面的最佳得分的某个下限 时， 扩展停止。扩展是 双向的，并 保存 从对 应种 子扩展而得到的高得分片 段对。 对于d n a序列搜索， 最初的单词 表包含查 询序列长度为w的 所有单 词。由于对d n a 的打分 相对比较容易， 所以从实际应用的角度来看， 上述处理能 够满足需 要。 数据库搜索策 略不同于处理蛋白 质序列的情况。 利用字母表大小 仅为4 的 特点， 首先压 缩数据库， 每个核 酸仅用2 位 ( b i t ) 表示， 4 个核酸组成一个字 节。 这样做除了 减少程序运行空间之外， 还可 以提高搜索速度， 因为现 在每次比较 一个字节 相当 于比 较4 个字符。 不过 这里需 要一个额外 的过滤步骤，以便从最初的单词表去掉常见的公共单词，避免得到太多的种子。 探针设计相关算法及分子模拟 2 .2 .2动态规划算法 动态规划是一种常用的规划方法，往往用于在一个复杂的空间中寻找一条最优路径。 在 运用动态规划时，有以下儿个要求:首先，搜索问题能够划分成一系列相继的阶段。起始阶 段包含基本子问 题的 解; 在后续阶段中， 能 够按递归 方式 根据前 面阶 段的 部分结果计 算每个 部分解;而最后阶段包含全局解。下面介绍动态规划算法在序列两两比对中的应用。 设 序 列s , t 的 长度 分 别 为m 和n 考 虑 两 个前 缀， a :s :】 和。 :t -.j , i, j _ 1 . 假 如已 知 序 列s 和 t所有较短子列的最优对比排列，即己知: ( 1 ) o :s :ci-)和。 :t:(j-1) 的 最 优 对 比 排 列; ( 2 ) o :s :(i-1) 和 。 a :j的 最 优 对 比 排 列 ; ( 3 ) o:s :,和 。a :g -1) 的 最 优 对 比 排 列 。 则。 :s :; 和。 :t y的 最 优对比 排 列 一 定 是 上 述 三 种 情 况 之 一 的 扩 展 : 0) 替 换低， 写 ) 或 匹 配 恤 ， 乌)， 这 取决 于s ; 是 否 等 于