【毕业学位论文】（Word原稿）双序列排比分析的视觉化软体工具之建置-義守大學资讯管理研究所

义 守 大 学 资 讯 管 理 研 究 所 硕士论文 双序列排比分析的视觉化软体工具之建置 究 生：陈钦贤 指导教授：陈孟峰博士 中华民国九十三年六月 2 双序列排比分析的视觉化软体工具之建置 究 生： 陈钦贤 导教授： 陈孟峰博士 守 大 学 资 讯 管 理 研 究 所 硕 士 论 文 A of 2004 华民国九十三年六月 I 致 谢 本论文的完成最感谢的是我的指导教授 陈孟峰 博士，在这两年的研究所过程，给予我相当充裕的资源，无论在学业或做人处事方面，亦提供相当多的宝贵意见，让我在学习的过程中获益良多，其亦师亦友的态度，更让人倍感温馨。同时还要感谢口试委员 王隆仁 博士、 杨崇宏 博士，于口试期间给予指正及建议，让本论文完善严谨 ，不胜感激。 大学时期是化工背景的我，因对着电脑技术有着高度的热忱，大学毕业后就加入了资讯管理的行列，然而在 陈孟峰 老师的指引后，毅然投入生物资讯的领域。开始时是一股新鲜感与懵懂的热忱，接踵而来的是意料之中的茫然与灰心。但是，我并不后悔走入这项领域，况且这是个新兴的研究主题，对着人类生物有着极大的贡献及发展。虽然这条路我走的并非十分顺遂，但是老师的指导与激励之下让我有走下去的动力，因此最感谢的是老师对我的耐心指导。 对于从没离开大台北地区念书的我，南下来义守读研究所真是个新的尝试。就如同南台湾的太阳一样，这边 的同学们都充满了人情味及热忱，于研究所两年求学的时间中，与同学间建立深厚的情谊，让我这个台北来的学子得到许多温馨的友情支持。圣峰、小蔡、智德，这些我学校宿舍的室友们；阿昌、俊豪、兴国、日焜，我的球友们；素真、小龟、姿蓉、阿郎 ，真想列出每个人的名字，因为大家的感情是这么的好，只好说一句纸短情长，我的好友们，钦贤非常谢谢你们两年来的照顾及指教。 最后，感谢父母亲的关怀与支持，让我顺利完成学业，因此将本论文特地献给我的父母亲、爷爷，对于您们对我的期许及鼓励，我都一定会尽全力的去完成。同时也要跟全部关心我的人分享 这份荣耀。 陈钦贤 谨志于观音山 民国九十三年六月序列排比分析的视觉化软体工具之建置 研究生：陈钦贤 指导教授：陈孟峰 博士 义守大学资讯管理研究所 中 文 摘 要 生物资讯 (11215在硬体与软体的支援下，促使分子生物学在 2000年 6月 26日，完成了整个人类基因体序列草图。其中主要的工作 - 序列分析 24，即是研究 是通常在网路上的大型资料库如 ，其使用介面共同的缺点在于分析的结果，往往以大量的文字显示，因此不易解读。本研究即在改善此缺点，以提升其效率。 我们针对双序列排比分析之介面做设计，使得操作更加容易，结果的呈现更加清晰。此外也利用动态规划 (计算最佳的序列排比，配合 阵图，以及资料点亮度的调整，以适于视觉接受的方式展现出排比的结果，改善传统的呈现方式。利用本程式去做几组双序列的蛋白质排比，结果显示在排比图框中，再透过明亮度的调整， 突显相关连的位置。另外可使用卷轴来移动两序列的相对位置，其相似度高的配对会立刻以颜色标示出来；而最佳化的全面性排比结果也同时呈现出来。 在本篇论文中，我们以视觉化的观念去设计一个序列排比程式，把序列间的关连以全面性和区域性的方式呈现出来，以改善网页传统的文字显示方式。未来发展方向，除了改善现有的演算法外，还可以利用网际网路与资料库互动，成为客户端的分析工具。 关键字：序列排比 ( of of 62000. of is NA on of a of is to is at We so is In is to is by of so it is to We to a of We to so of In we a of of so it of by on on V it on to a V 目 录 致 謝 . 错误 !未定义书签。 中 文 摘 要 . 错误 !未定义书签。 . 错误 !未定义书签。 目 錄 . 错误 !未定义书签。 圖目錄 . 错误 !未定义书签。 表目錄 . 错误 !未定义书签。 壹、概論、研究動機與目的 . 错误 !未定义书签。 貳、背景知識與文獻探討 . 错误 !未定义书签。 蛋白質的背景知識 . 错误 !未定义书签。 . 错误 !未定义书签。 白質 (. 错误 !未定义书签。 陣圖 . 错误 !未定义书签。 態規劃法 (. 错误 !未定义书签。 比 (. 错误 !未定义书签。 面性排比 ( . 错误 !未定义书签。 域性排比 ( 误 !未定义书签。 分矩陣 . 错误 !未定义书签。 核酸評分矩陣：單位矩陣 (. 15 蛋白質評分矩陣： 洛森矩陣 ) . 16 洞扣分 (. 错误 !未定义书签。 參、系統設計理念與建置流程 . 错误 !未定义书签。 統設計理念 . 错误 !未定义书签。 統建置環境 . 错误 !未定义书签。 統執行流程 . 错误 !未定义书签。 列輸入畫面 . 错误 !未定义书签。 程式畫面 . 错误 !未定义书签。 面性及區域性排比畫面 . 错误 !未定义书签。 例分析 . 错误 !未定义书签。 伍、結論與未來展望 . 错误 !未定义书签。 參考文獻 . 错误 !未定义书签。 附 錄 . 错误 !未定义书签。 附錄一、標準的一個胺基酸碼和三個 基碼的對照 . 错误 !未定义书签。 附錄二、 體 . 错误 !未定义书签。 附錄三、各種的 分矩陣 . 错误 !未定义书签。 附錄四、 料庫的蛋白質序列 (程式使用到的 ) . 错误 !未定义书签。 目录 圖 2 - 1、構成 四種鹼基 . 4 圖 2 - 2、 鹼基對及雙螺旋架構 . 4 圖 2 - 3、胺基酸的基本結構 . 5 圖 2 - 4、二十種胺基酸之名稱、支鏈構造及縮寫 . 6 圖 2 - 5、肽鍵 . 6 圖 2 - 6、蛋白質一級結構表示法 . 7 圖 2 - 7、蛋白質各級結構的示意圖 . 8 圖 2 - 8、 蛋白質之關係 . 9 圖 2 - 9、 由轉錄及轉譯到合成 示意 . 9 圖 2 - 10、利用 對之示意圖 . 10 圖 2 - 11、利用動態規劃的全面性排比計分矩陣計算之路徑 . 12 圖 2 - 12、 . 13 圖 2 - 13、利用動態規劃的區域性排比計分矩陣計算之路徑 . 14 圖 2 - 14、 . 15 圖 2 - 15、 . 17 圖 2 - 16、各種 陣的關係圖 . 17 圖 3 - 1、序列比對 料庫所產生的資訊 . 19 圖 3 - 2、利用 念建構出的點陣圖 . 20 圖 3 - 3、系統流程圖 . 21 圖 4 - 1、程式功能鍵 . 26 圖 4 - 2、序列輸入視窗 . 27 圖 4 - 3、選擇欲使用的評分矩陣與未輸入資料的主程式畫面 . 28 圖 4 - 4、主程式畫面 . 29 圖 4 - 5、手動比對 . 29 圖 4 - 6、序列排比畫面 . 30 圖 4 - 7、任意兩蛋白質 . 31 圖 4 - 8、兩蛋白質間有一小段序列一樣 . 32 目录 表 2 - 1、單位矩陣 (. 15 1 壹、概论、研究动机与目的 西元 1953年， 已经决定敞开分子生物学领域的大门，到了 2000年 6月 26日，人类联合发表对于完成整个人类基因体序列草图的绘制，从此便进入了后基因体时代。从过去几十年，生物学家不论是用化学的方式定序或配合科技 (累积了非常大量的基因序列资料，因此只是利用人力的分析是无效率且不切实际的。于是，生物资讯学 (应孕而生，生物资讯学意指所有电脑处理、分析生物学研究过程，包含利用电脑、网路进行资料的收集与整合、利用影像处理设备将研究过程所得的图像比对，及大多数分子生物学者比较熟悉的巨分子序列分析比对、结构预测等。 所以，生物资讯学的成员是一个大集合，包含生物学家、病理家、数学家及程式设计者等，集合多个不同领域的专家。在后基因体时代，面对如此庞大的资料，便要依靠高度的电脑运算能力。在基因定序阶段，主要依赖资讯业人才从事生物资讯工具的开发，然而在蛋白质体与基因功能的分析，就需要生物学家的协助 ，生物学家面临了资 讯整理与资讯分析的挑战。生物资讯的资料日渐扩增，生物、医学、药学等领域研究人员想藉由生物资讯资料库加快实验目标的设定，一般而言研究人员会以已定序但未知功能的生物序列，从已知的资料库内查询此序列是否存在，或者是否存在相似的序列 。另外，基因分析和资讯的管理，更是需要资讯与生物科技的整合性人才，这也是现阶段各国在发展生物科技上最需要解决的问题。 序列分析技术可以应用到 胺基酸 )序列。因此 们所面临的问题通常是手上有一段没有任何注解的片段的序列，我 们想要看看知道这一段序列与哪一段已知的序列相似性及其功能为何，在比较序列之前，序列之间的排比是必要的。 2 找出最佳序列排比的想法是很简单的，先将两条序列任意配对，对此配对的品质给予评分，然后将其中一条序列相对于另一条序列移动，并再次计分，直找到分数最高的比对为止。这个原理很简单，但要靠人工排比的话就会令人感叹人生苦短，因此，必须将挑出最佳结果程式以自动化的方式产生。所以一个好的程式是必须的，现今网路的发达，很多的生物资料库都提供比对的程式，但往往提供的功能有限，或是每个功能都是分离的且又有对特定的功能作呈现， 常常让人不知所然 (熟悉的研究者除外 )；还有在输入了序列，比对后是以文字或是以非常简单的图形呈现给使用者了解，常常让人觉得好像还有很多资讯还没被呈现或是太过繁杂。于是在本研究中将设计一个双序列排比的介面以简化其操作，并以图形的方式展示其排比结果，以符合视觉化的效果。 3 贰、背景知识与文献探讨 本文内容将对于生物体的相关知识、及序列如何运算分成下列各小节探讨。 生命体是由数十种不同种类的元素所组成，其中碳 (C)、氢 (H)、氧 (O)、氮 (N)等元素占了 99%。所以生命体是由上述等 元素所制作出复杂的有机化合物，如碳水化合物 (醣类 )、脂质、蛋白质、核酸等物质，这些都是生物体组成的根本。 核酸中包含有 种。 作去氧核糖核酸， 1955 年 J. D. F. H. C. 现 于核苷酸上的碱基 (含氮碱基 )的四种去氧核糖核酸 (组成，分别是 腺嘌呤 (称A)、胸腺嘧啶 (称 T)、胞嘧啶 (称 C)、鸟嘌呤 (称G)四种 (如图 2， 是由两条单股所构成的一双股螺旋结构 17，而两条单股行进的方向相反，为互补反平行，一股是由 5端 3端，另一股则为 3端 5 端， 5 端及 3 端分别代表核糖 (的第 5和第 3个碳 ，形成二个及三个氢键而得到安定的结构，所以 J. D. F. H. C. 外 E. 其共同研究者发现 、 C/据华生 . 相互间逆方向配对的 氢键多键的方式 16，如： A=T， G 图 2 4 图 2 - 1、构成 图 2 - 2、 如图 2示， 成了 股结构。而 骨架是由磷酸与核糖之间的键 结所构成。其中5 碱基的排列顺序即为生物体内的遗传密码，现已有许多的密码已经被解开了，而这些密码则是决定生物体内蛋白质如何组合键结。 而 是由四种去氧核糖核酸所组成，它的组成份和 类似，只是把 尿嘧啶 (称 U)去取代胸腺嘧啶 (称 T)，如图 2所以 人类的染色体有 23对且就是由一连串的 核苷酸 序列所组成的。 另外，蛋白质 是由碳 (C)、 氢 (H)、 氧 (O)、 氮 (N)、 硫 (S)、 磷 (P)、 铜 ( 铁( 几种元素所构成，其中碳 (C)、 氢 (H)、 氧 (O)、 氮 (N)等四种元素为比较主要的组成元素，而蛋白质含 氮元素也是其组成和醣类以及脂肪最大的不同之处。 白质 (蛋白质通常是由 20种胺基酸 (组合而成的 18，如图 2基酸的基本结构可分为三个部分，分别为胺基 ( 羧基 ( 支链 (R)，就如图 2 胺基酸的基本结构： 图 2 - 3、胺基酸的基 本结构 6 图 2 - 4、二十种胺基酸之名称、支链构造及缩写 另外在蛋白质的合成中，有一个化学性质的成分扮演着很重要的角色：那就是 肽键 (如图 2 当一个胺基酸的 羧 基与另一个胺基酸的胺基相遇而脱去一分子的水 (形成的 键结即为肽键 。 图 2 - 5、肽键 7 本研究探讨的是胺基酸序列 (即蛋白质一级结构 )，因此以下只探究蛋白质一级结构的学理。 一级结构 ( (1) 蛋白质的基本骨架： 为一胺基酸序列，是经由 的补密码与 的密码子在核糖体中互相配对，此时胺基酸会经由 经由延长作用 (结形成长链状的胺基酸链，最后利用终止作用 (胺基酸链从核糖体脱离，此为转译作用。一级结构的一端为 作 一端为 作 C 端，在转译作用中，一级结构是由 C 端结尾，而一级结构可以用下图 2 C：表示各个胺基酸上的 碳 R：表示不同胺基酸 上的支链 图 2 - 6、蛋白质一级结构表示法 (2) 一级结构是由 由核糖体的作用而形成的，而 列经转录作用决定了 序列，在转译作用中 以 序列决定了一级结构的胺基酸序列，因此 (3) 一级结构的序列意义： 一级结构的序列顺序决定了其折迭后的 结构，因为每一不同的胺基酸在胺基酸链上的不同位置出现都会使胺基酸之间的作用力改变，而影响其折迭的结果。8 还有讯息序列 (而此序列是决定一蛋白质在细胞中制造之后被送至细胞中的哪个位置。另外还由一些特殊的序列，像是 含，若是蛋白质有一个或是多个 此蛋白质易被分解，因此，此类的蛋白质的半生期较短。图 2白质各级结构的示意图，其中三级结构 (3D 决定蛋白质的功能。 图 2 - 7、蛋白质各级结构的示意图 而 2 后 录一表示的为三个 9 图 2 - 8、 图 2 - 9、 6是一种绘制点矩阵的软体，经由简单的图形输出可完整的呈现两个序列间整体相似度，最先由 1970 所提出 。 出10 的是一种表格或矩阵模式，序列比对时其中一个序列位置横列在矩阵的上方，另一个序列位置直排在矩阵的左方。如果序列比对结果相同 (单一位置 )，就将相同的序列 碱基 (入相对应的矩阵空白处 ;如果比对结果不同，则保留矩阵空白。因此，序列比对结果对应相同的残基会 从左上方延伸到右下方。 图 2基础的例子。如果比对移动方向是连续的对角线，表示两个序列间没有插入的现象，如果是水平方向，表示比对中有空白插入且是在矩阵左方的序列中 ; 如果是垂直方向，表示比对中有空白插入且是在矩阵上方的序列中。 图 2 - 10、利用 图中箭头所指示出的移动路线代表两个序列间明显的比对结果： 种基本的 解决的问题只能局限在比较残基完全相同的位置上，而对于以 法发挥其效用。因此，我们引用 13的处理方式，将对应的点的亮度根据两残基替换的机率的值来调整点的亮度，以利用眼睛直接观察的能力，找出关联程度高的区段。 11 动态程式规划 8解决问题的方式是一步一步的解决主要问题中较小的次问题。 若两个序列间存在着适当的相异程度，则这两条序列排序的结果通常不是只有一个最佳的排序方法，而是可能有多种可能排序方法 (最适解 )。用动态程式规划寻找最佳序方式，通常会用回溯 (技巧并且运用各种参数 (如缺洞扣分 验不同的路径，比较所有路径中最好的一条 (最佳解路径 )就是最佳的排序方式。 以下将会介绍两种排比方 式，皆是运用动态程式规划来达到排比的目的。 面性排比 ( 德曼与王氏 ( 1970年提出这个演算法 7。在这演算法中，两个序列间的最佳配对定义为：能够使第一条序列中最多的 面性排序的作法是将两条序列以二度空间的方式形成的计分矩阵，然后从左上到右下角进行分数加总的动作，其执行加总方式如下图 2 ),(),1(m a x),( ； ),()1,( ； (1) ji )1,1( D ( i - 1 , j - 1 ) D ( i , j - 1 )D ( i - 1 , j ) D ( i , j )D ( - d ( )- d ( , 2 其中： ),( ,(：表示 (插入空白 )的相似函数； (插入空白 )的相似函数； ji ：表示),( 目前这个排比位置的分数。 图 2 - 11、利用动态规划的全面性排比计分矩阵计算之路径 矩阵中的每个排比位置，依据横向、纵向及斜对角 (三个不同方向 )的最高分数为此位置的最佳分数。 排序时则由右下角找得分最高的格子往左上角移动并且不断加上分数 3。 举个例子来说：图 2开始先由最左上角当作起点往右下方走，如果是空白 ( )对上字母或往右、往下，则处罚扣分 8分，若是有字母对上的话，则依每组字母的比对有不同的得分。于是每个点都有往左、往下及右下三个方向可以走，每次都挑最大值的方向走，且沿途记录走过的路径。在图中可以见到走到最右下角时其值为 1；然后就要进行回溯 (步骤，往回走时就要依走下来的路径回 去，且如果同一位置有二条以上的路则选值较大者；或是其值相同时，则任选一个方向走，所以如果路径的输出只能有一个的话，有可能其路径走法不会唯一，但看程式演算法的设计，另外当路径往上时代表上方序列要插入空白，而往左走则是左方序列要插入空白。当回溯到最左上角 (0,0)时，全面性的排比路径就计算完成了，就如图 2比过后的两条序列间都有插入些许个空白，以让这两序列排的更好。 13 图 2 - 12、 区域性排 比 ( 常用的序列排比工具，是以 区域性排比策略为基础的方法 9。上一段所提到的全面性排比是假设两序列都已知，才可以用全长来做排比。不过，我们常常遇到的序列排比目的，是以一个未知的序列对序列资料库中的已知序列进行搜寻，或是在一段很长的 列中寻找与查询序列相符的部分片段。用动态程式规划演算法，用来解决两段已知序列的部分排比问题，它与 算法相似，但在回溯时加了一个额外的选择：不需要由两段序列的起点到终点做延伸；如果累积到某点时的积分为负，于是这个排比停止并且开始新的排比。因此，排比可以在矩阵的任一部分停止。 D ( i - 1 , j - 1 ) D ( i , j - 1 )D ( i - 1 , j ) D ( i , j )D ( - d ( )- d ( , 4 0m a x),( ； ),(),1( ； (2) ),()1,( ； ji )1,1( 其中 : ),( ,(：表示 (插入空白 )的相似函数； (插入空白 )的相似函数： ji ：表示 相似函数 ),( 目前这个排比位置的分数。 图 2 - 13、利用动态规划的区域性排比计分矩阵计算之路径 其作法如同全面性排比，唯一不同之处是当决定每个排比位置的最佳分数时，在推导最佳排比过程中会发生某排比位置的最大值为 0，则此条最佳排比终止，因此造成区域性最佳排比 811。 图 2算过程和全面性排比一样，最大的不同点在于每个位置上最小值为 0(没有负值 )，如果某个位置其值为负，就要令其值为 0(根据演算法 )。当由左上累加并且记录所走 的路径到右下方时停止；还有回溯时选择最大值当作起点，沿着路径走到值为 0时便停下。在图里可以看到回溯时起点的最大值为 28(粗体字 )，然后沿路径回走 (粗体 )，直遇到 0时便停止。往上走表示上方序列要插入空白，往左则是左方序列插入空白，于是区域性排比如图下方所示。 15 图 2 - 14、 核酸评分矩阵：单位矩阵 (在 、 C、 G、 (组成，所以在此的评分矩阵非常简单，碱基比对符合配对给值 +1，不符合配对则给值 0，详细请参考表 2 A C G T A 1 0 0 0 C 0 1 0 0 G 0 0 1 0 T 0 0 0 1 表 2 - 1、单位矩阵 (16 蛋白质评分矩阵： 洛森矩阵 ) 截至目前为止，我们计算序列间距离时都只有考虑到完全相同的残基，相同的残基配对得一分，这种计算序列距离的矩阵，称 为单位矩阵 (就如同 ，这种矩阵的特性是它很稀疏，因为矩阵中大部分的组成份子都是 0，这同时也意味着这种矩阵缺乏辨别力。所以，为了提高辨别力，且在不增加背景杂讯的前提下，加入其它较弱但具有生物意义的胺基酸配对讯息。这个改变正是蛋白质序列分析的重点，我们必须在仅有数学意义的高分排比方式，及具有生物意义但分数较低的排比之间作出抉择。 为了解决这位问题，科学家们设计出可以对相似 (但不相同 )的胺基酸碱配对评分的矩阵基，而给分的标准是参考许多不同亲疏远进的蛋白质序列之间其胺基酸互相取代的比率 (定出来的矩阵。这跟 确地使用种矩阵，可以提高对不同排比间差异的敏感度，尤其是在两条序列间的全等的胺基酸配对很少时，其办识力可以更清楚的突显出来。 因此 S. 1992年 11 月发展一种运算胺基酸序列排比时计算替换发生机率的 5， 可以更直接地表示序列间的遗传距离 。它是以比对蛋白质序列的 料库为基础，从其中撷取出来的序列推演而得。因此以 命名。 阵法 (后者的优点在于用来比较 85%以上相似度的序列 )，所以 S. 果以对数来表示。 此间胺基酸的差异不大，因此在计算每一点的各种胺基酸比例时，在遗传距离相近的蛋白质间共有的同一种胺基酸在其点上所占的比例会偏高，而导致计算上的偏差。所以 布洛森矩阵的方法是将各个序列片段依照最低相同比例 (予分组，每组分别计算其中每个点17 各种胺基酸的比例，事实上就像在计算一条序列的每个点各种不同的胺基酸出现的机率一样，这样就可以修正因为某些蛋白质彼此间遗传距离较近而造成的偏差。 当用不同的最低相同比例来对蛋白质序列分组时，就会得到不同的布洛森矩阵，用 62%最低相同比例做出来的就是布洛森 62 (阵，请参考图2图 2示，使用的布洛森矩阵值越大，辨识率就越高，另外还有布洛森 80矩阵，布洛森 45矩阵等以供使用 12，详见附 录三 。 图 2 - 15、 L 0 62 B L M 4 5L di t M d i n - 16、各种 洞扣分 (假如排比仅局限于将完全相同的序列排在一起，那么很容易的可以写出一个18 合理的程式来处理。但是，通常排比是要比对整段完整的序列，一个考虑完善的排比程式必须将两条完整的序列中全部的胺基酸残基都列入考虑，这意思是说有时候必须将不相同的胺基酸配对在一起。在这个情形下，缺洞位置的安排就变 的十分难以取舍。虽然可以将相同的胺基酸残基配对在一起，而在不同的地方都插入缺洞，这样的排比分数将是最高的，但却没有任何生物意义。另一种较好的方式就是每增加一个缺洞则在总分上扣分 (于是配合动态程式规划的全面性或区域性排比演算法，在插入空白时则处罚扣分。在 为碱基的比对较为单纯，不用考虑突变 (取代 )的因素，所以插入空白造成缺洞所扣的分数都是一样的。但在蛋白质序列中胺基酸比对时，因为使用的评分矩阵(不同，所以插入空白所扣的分数也会有所不同。 19 参、系统设计理念与 建置流程 统设计理念 通常在网路上的大型资料库，如 软体都有共通的缺点，就是对于使用者所输入的序列分析，往往都会有大量的资料讯息显现在浏览器上，所以使用者可能要花很多时间去找寻想要得到的资讯，这样对使用者来说是一件费心劳力的工作。图 3是用一个已定序但不知道功能的蛋白质序列对 料库进行搜索，看是否可找到类似的序列，或局部区域相似的序列，进而可以让生物学家利用这些的已知序列去推测、做实验来探究这个已定