第七章序列比对和数据库搜索 页码,5/2 PLaU 90 EPKKVKDHCSKHSPCQKGGTCVNMP-SGPH-CLCPOHLTGNHCOKEK---CFE 137 PLAT 23 ELHQVPSNCD----CLNGGTCVSNKYFSNI HWCNCPKKFGGOHCEI DKSKTCYE 72 图7.5、点阵、路径图和比对:所有这三种视图都表示人类尿激酶血纤蛋白溶酶原活化因子 ( PLAU. Swiss- Prot pc749)和组织血纤蛋白溶酶原活化因子(PLAT: Swiss- Prot p00750) 中同EGF相似的模块的比对结果。a).整个蛋白都由D0TER程序进行比较:这里只显示了同 EOGF模块相似的较小区域的放大图;b)由 BLASTP得到的比对的路径图;.C).用普通的字符形式 显示的 BLASTP空位比对 要理解路径图,先想象一个二维格子,顶点表示序列残基之间的点(与点阵中表示残基本身 相反),沿线段上连接两个顶点的边缘对应两个序列上匹配的残基,水平和竖直线段的边缘 对应一个序列拥有而另一个序列上没有的残基,换句话说,这些边缘平台组成了比对中的空 位,全图对应了所有可能的比对中必须审视的搜索空间,这个空间中每条可能的路径都对应 于一种比对。 最佳比对方法 除了某些很不重要的问题,对于众多问题而言,比对方法多种多样,很有必要从中挑选出最 好的一个或几个方法,这就是把一种比对描述成一个路径的概念所指。许多计算机科学的问 题都可以简化为通过图表寻求最优路径(比如寻找从纽约打电话到旧金山的最有效的途 径)。为了这一目的已经确立了许多行之有效的算法,对每一种路径都有必要对其进行某种 意义上的打分,通常是对沿这一途径的每一步的增量进行加和。更精密的打分程序将在下文 叙述,在这里我们只假定相同残基加正分,有插入或缺失的残基就加负分(扣分),根据这 定义,最合适的比对方法会得到最高分,也就是我们寻找的最佳路径 今天我们所熟悉的Meed∥eman-msc算法就是针对寻求最佳序列比对这一问题所设计的动态 规划寻优策略( Need eman and Wunsch,1970)。动态规划的思想是这样的,如果一条路径终 止于最佳路径上的一点,那么这条路径本身就是起点到这个中间点的最佳路径,也就是说, 任何一个终止于最佳路径上的一点的次级路径必然就是终止于这一点的最佳路径本身。这 样,最佳路径就可以通过把各个最佳的次级路径连接而成。在基本的№ leed eman- Wunsch公式 表达中,最佳比对必然对每个序列都由始至终,就是说从搜索空间的左上角直至右下角。换 句话说,它搜索全程比对。 然而,对这种基本策略稍作修改就可以实现最佳的局部比对。这种比对的路径不需要到达搜 索图的尽头,只需要在内部开始和终结。如果某种比对的打分值不会因为增加或减少比对队 的数量而增加时,这种比对就是最佳的。这个过程依赖于打分系统的性质,就是说某种路径 的打分会在不匹配的序列段位置减少(以下叙述的打分系统合乎这个标准)。当分值降为零 时,路径的延展将会终止,一个新的路径就会应运而生。这样,我们会得到许多独立的路 径,它们以不匹配的序列段为界限而不是像在全程比对中以序列的结尾作为界限。在这些路 径中,拥有最高分的一个就是最佳的局部比对 应该意识到,寻优方法总是把最佳的比对方法表达出来,而不在意它是否具有生物学意义, 另一方面,寻求局部比对时可能会发现若干个重要的比对,因此,不能仅仅注意最佳的 个。改良的Sm/th- terman( Al tschul and eri ckson,1986; Waterman and eggert,1987)算法 把寻找K种最好的但不相互交叉的比对方式最为目标,这些思想后来都在S|M算法( Huang et 1990)的发展中得以体现。一个名叫LAG(在 FASTA程序包中)的程序提供了有用的S|M file://E:wcb生物信息学(中译本)\第七章序列比对和数据库搜索.htm 2005-1-18c PLAU 90 EPKKVKDHCSKHSPCQKGGTCVNMP—SGPH-CLCPQHLTGNHCQKEK---CFE 137 PLAT 23 ELHQVPSNCD----CLNGGTCVSNKYFSNIHWCNCPKKFGGQHCEIDKSKTCYE 72 ೒7.5ǃ⚍䰉ǃ䏃ᕘ೒੠↨ᇍ˖᠔᳝䖭ϝ⾡㾚೒䛑㸼⼎Ҏ㉏ሓ▔䝊㸔㑸㲟ⱑ⒊䝊ॳ⌏࣪಴ᄤ ˄PLAU:Swiss-Prot P00749˅੠㒘㒛㸔㑸㲟ⱑ⒊䝊ॳ⌏࣪಴ᄤ˄PLAT:Swiss-Prot P00750˅ ЁৠEGFⳌԐⱘ῵ഫⱘ↨ᇍ㒧ᵰDŽa) .ᭈϾ㲟ⱑ䛑⬅DOTTER⿟ᑣ䖯㸠↨䕗˖䖭䞠াᰒ⼎њৠ EGF῵ഫⳌԐⱘ䕗ᇣऎඳⱘᬒ໻೒˗b)⬅BLASTPᕫࠄⱘ↨ᇍⱘ䏃ᕘ೒˗.c).⫼᱂䗮ⱘᄫヺᔶᓣ ᰒ⼎ⱘBLASTPぎԡ↨ᇍDŽ 㽕⧚㾷䏃ᕘ೒ˈܜᛇ䈵ϔϾѠ㓈Ḑᄤˈ乊⚍㸼⼎ᑣ߫⅟෎П䯈ⱘ⚍˄Ϣ⚍䰉Ё㸼⼎⅟෎ᴀ䑿 Ⳍড˅ˈ⊓㒓↉Ϟ䖲᥹ϸϾ乊⚍ⱘ䖍㓬ᇍᑨϸϾᑣ߫Ϟऍ䜡ⱘ⅟෎ˈ∈ᑇ੠オⳈ㒓↉ⱘ䖍㓬 ᇍᑨϔϾᑣ߫ᢹ᳝㗠঺ϔϾᑣ߫Ϟ≵᳝ⱘ⅟෎ˈᤶহ䆱䇈ˈ䖭ѯ䖍㓬ᑇৄ㒘៤њ↨ᇍЁⱘぎ ԡˈܼ೒ᇍᑨњ᠔᳝ৃ㛑ⱘ↨ᇍЁᖙ乏ᅵ㾚ⱘ᧰㋶ぎ䯈ˈ䖭Ͼぎ䯈Ё↣ᴵৃ㛑ⱘ䏃ᕘ䛑ᇍᑨ Ѣϔ⾡↨ᇍDŽ ᳔Շ↨ᇍᮍ⊩ 䰸њᶤѯᕜϡ䞡㽕ⱘ䯂乬ˈᇍѢӫ໮䯂乬㗠㿔ˈ↨ᇍᮍ⊩໮⾡໮ḋˈᕜ᳝ᖙ㽕ҢЁᣥ䗝ߎ᳔ དⱘϔϾ៪޴Ͼᮍ⊩ˈ䖭ህᰃᡞϔ⾡↨ᇍᦣ䗄៤ϔϾ䏃ᕘⱘὖᗉ᠔ᣛDŽ䆌໮䅵ㅫᴎ⾥ᄺⱘ䯂 乬䛑ৃҹㅔ࣪Ў䗮䖛೒㸼ᇏ∖᳔Ӭ䏃ᕘ˄↨བᇏᡒҢ㒑㑺ᠧ⬉䆱ࠄᮻ䞥ቅⱘ᳔᳝ᬜⱘ䗨 ᕘ˅DŽЎњ䖭ϔⳂⱘᏆ㒣⹂ゟњ䆌໮㸠П᳝ᬜⱘㅫ⊩ˈᇍ↣ϔ⾡䏃ᕘ䛑᳝ᖙ㽕ᇍ݊䖯㸠ᶤ⾡ ᛣНϞⱘᠧߚˈ䗮ᐌᰃᇍ⊓䖭ϔ䗨ᕘⱘ↣ϔℹⱘ๲䞣䖯㸠ࡴ੠DŽ᳈㊒ᆚⱘᠧߚ⿟ᑣᇚ೼ϟ᭛ ভ䗄ˈ೼䖭䞠៥Ӏা؛ᅮⳌৠ⅟෎ࡴℷߚ᳝ˈᦦܹ៪㔎༅ⱘ⅟෎ህࡴ䋳ߚ˄ᠷߚˈ˅ḍ᥂䖭 ϔᅮНˈ᳔ড়䗖ⱘ↨ᇍᮍ⊩Ӯᕫࠄ᳔催ߚˈгህᰃ៥Ӏᇏᡒⱘ᳔Շ䏃ᕘDŽ Ҟ໽៥Ӏ᠔❳ᙝⱘNeedleman-Wunschㅫ⊩ህᰃ䩜ᇍᇏ∖᳔Շᑣ߫↨ᇍ䖭ϔ䯂乬᠔䆒䅵ⱘࡼᗕ 㾘ߦᇏӬㄪ⬹˄Needleman and Wunsch,1970˅DŽࡼᗕ㾘ߦⱘᗱᛇᰃ䖭ḋⱘˈབᵰϔᴵ䏃ᕘ㒜 ℶѢ᳔Շ䏃ᕘϞⱘϔ⚍ˈ䙷М䖭ᴵ䏃ᕘᴀ䑿ህᰃ䍋⚍ࠄ䖭ϾЁ䯈⚍ⱘ᳔Շ䏃ᕘˈгህᰃ䇈ˈ ӏԩϔϾ㒜ℶѢ᳔Շ䏃ᕘϞⱘϔ⚍ⱘ⃵㑻䏃ᕘᖙ✊ህᰃ㒜ℶѢ䖭ϔ⚍ⱘ᳔Շ䏃ᕘᴀ䑿DŽ䖭 ḋˈ᳔Շ䏃ᕘህৃҹ䗮䖛ᡞ৘Ͼ᳔Շⱘ⃵㑻䏃ᕘ䖲᥹㗠៤DŽ೼෎ᴀⱘNeedleman-Wunsch݀ᓣ 㸼䖒Ёˈ᳔Շ↨ᇍᖙ✊ᇍ↣Ͼᑣ߫䛑⬅ྟ㟇㒜ˈህᰃ䇈Ң᧰㋶ぎ䯈ⱘᎺϞ㾦Ⳉ㟇েϟ㾦DŽᤶ হ䆱䇈ᅗ᧰㋶ܼ⿟↨ᇍDŽ ✊㗠ˈᇍ䖭⾡෎ᴀㄪ⬹⿡԰ׂᬍህৃҹᅲ⦄᳔Շⱘሔ䚼↨ᇍDŽ䖭⾡↨ᇍⱘ䏃ᕘϡ䳔㽕ࠄ䖒᧰ ㋶೒ⱘሑ༈ˈা䳔㽕೼ݙ䚼ᓔྟ੠㒜㒧DŽབᵰᶤ⾡↨ᇍⱘᠧߚؐϡӮ಴Ў๲ࡴ៪ޣᇥ↨ᇍ䯳 ⱘ᭄䞣㗠๲ࡴˈᯊ䖭⾡↨ᇍህᰃ᳔ՇⱘDŽ䖭Ͼ䖛⿟ձ䌪ѢᠧߚLTD㒳ⱘᗻ䋼ˈህᰃ䇈ᶤ⾡䏃ᕘ ⱘᠧߚӮ೼ϡऍ䜡ⱘᑣ߫↉ԡ㕂ޣᇥ˄ҹϟভ䗄ⱘᠧߚLTD㒳ড়Т䖭Ͼᷛޚ˅DŽᔧߚؐ䰡Ў䳊 ᯊˈ䏃ᕘⱘᓊሩᇚӮ㒜ℶˈϔϾᮄⱘ䏃ᕘህӮᑨ䖤㗠⫳DŽ䖭ḋˈ៥ӀӮᕫࠄ䆌໮⣀ゟⱘ䏃 ᕘˈᅗӀҹϡऍ䜡ⱘᑣ߫↉Ў⬠䰤㗠ϡᰃڣ↨⿟ܼ೼ᇍЁҹᑣ߫ⱘ㒧ሒ԰Ў⬠䰤DŽ೼䖭ѯ䏃 ᕘЁˈᢹ᳔᳝催ߚⱘϔϾህᰃ᳔Շⱘሔ䚼↨ᇍDŽ ᑨ䆹ᛣ䆚ࠄˈᇏӬᮍ⊩ᘏᰃᡞ᳔Շⱘ↨ᇍᮍ⊩㸼䖒ߎᴹˈ㗠ϡ೼ᛣᅗᰃ৺݋⫳᳝⠽ᄺᛣНˈ ঺ϔᮍ䴶ˈᇏ∖ሔ䚼↨ᇍᯊৃ㛑Ӯথ⦄㢹ᑆϾ䞡㽕ⱘ↨ᇍˈ಴ℸˈϡ㛑ҙҙ⊼ᛣ᳔Շⱘϔ ϾDŽᬍ㡃ⱘSmith-Waterman(Altschul and Erickson,1986;Waterman and Eggert,1987)ㅫ⊩ ᡞᇏᡒ.⾡᳔དⱘԚϡⳌѦѸঝⱘ↨ᇍᮍᓣ᳔ЎⳂᷛˈ䖭ѯᗱᛇৢᴹ䛑೼SIMㅫ⊩(Huang et al.,1990)ⱘথሩЁᕫҹԧ⦄DŽϔϾৡিLALIGN˄೼FASTA⿟ᑣࣙЁ˅ⱘ⿟ᑣᦤկњ᳝⫼ⱘSIM ㄀ϗゴᑣ߫↨ᇍ੠᭄᥂ᑧ᧰㋶ 义ⷕˈ5/28 file://E:\wcb\⫳⠽ֵᙃᄺ˄Ё䆥ᴀ˅?㄀ϗゴᑣ߫↨ᇍ੠᭄᥂ᑧ᧰㋶.htm 2005-1-18 Click to buy NOW! PDF-XCHANGE www.docu-track.com Click to buy NOW! PDF-XCHANGE www.docu-track.com