生物信息学基础——第三章.ppt

* * * * * * We first compute T[i, j] for the smallest possible values of i and j, then for increasing values of i and j Usually performed with a table of size (n + 1) X (m + 1) 多序列比对 目前使用最广泛的多重序列比对程序是ClustalW ClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映了每对序列的关系 EBI的CLUSTALW网址是： http://www.ebi.ac.uk/clustalw/ 7、统计特征分析 对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示 —H—LVV G—VLVG GN—LVV LHCLV- VHCL-- （1）保守序列 表示序列每个位置上最可能出现的字符（或者所有可能出现的字符） ATNTSC (N - A,T,C,G ; S - G,C) （2）特征统计图（Profile） 令P=(P1,P2,…,PL)，P表示在?的每一列上各种字符出现的概率分布 Pj=(pj0,pj1,…,pj|A|) A代表字母表，Pjk代表字母表A中第k个字符在第 j 列出现的概率。 第0个字符是特殊的空位符号“-”。 ATTAT AACTT CTTAT ACTTT AGAAT 1 2 3 4 5 (位置) A 0.8 0.2 0.2 0.6 0.0 T 0.0 0.4 0.6 0.4 1.0 C 0.2 0.2 0.2 0.0 0.0 G 0.0 0.2 0.0 0.0 0.0 （碱基） 利用保守序列或者特征统计图可以判断一个序列是否满足一定的特征 给定一个序列s=a1a2…am，定义字符a在第j位的代价为 其中，|A|代表字母表A的长度，Ak代表A的第k个字符，特别地A0代表空缺字符“-”。整个序列s的代价为 一条序列与特征统计图相对照，如果代价值小，说明该序列具有相应的特征，否则该序列不具备相应的特征。 第四节 DNA片段组装 大规模基因组测序 得到待测序列的一系列序列片段 这些序列片段覆盖待测序列 序列片段之间也存在着相互覆盖或者重叠。 目标序列 序列碎片 1、片段组装问题 定义： 给定一组取自特定字母表的字符串集合F，寻找一个最短的字符串s，使得F中的每一个字符串都是s的一个连续子串。这里，集合F的字符串相当于待组装的序列片段，而s则是序列片段组装的结果。 Input Answer ACCGT --ACCGT-- CGTGC ----CGTGC TTAC TTAC----- TACCGT -TACCGT-- TTACCGTGC （1）碱基标识错误 4个主要问题 （2）不知道片段的方向 （3）存在重复区域 . . （4）缺少覆盖 2、序列片段组装模型 序列片段组装过程： 三个步骤 （1）首先进行序列片段的两两比较，确定可能的片段之间的覆盖（或者重叠）； （2）确定所有片段统一的覆盖模式，即确定各个序列片段的相对位置； （3）最后确定片段组装结果，即确定目标序列。 （1）最短公共超串模型 三种片段组装模型 给定一个字符串集合F，求出一个最短的字符串S，使得对于所有属于F 的字符串f，S是 f 的超串（或者 f 是 S 的子串）。 设F={ACT，CTA，AGT} 则S=ACTAGT 是 F 的超串 由于S必须是各片段严格的超串，因此不允许片段的实验误差， 各片段的方向必须是已知的。 （2）重建模型 考虑到片段的误差和未知方向的问题 近似子串 假设f、g是代表两条序列的字符串，f 作为 g 近似子串的代价为： S(g)代表 g 所有子串的