转录剪切位点

1、核酸序列分析及结构预测核酸序列分析及结构预测主 讲 张 军细胞生物学及遗传学教研室第一节第一节 核酸序列的数据形式核酸序列的数据形式1. 串（string）符号或字符的有序排列，符号或字符来自有限集合A, T, G, C。序列（sequence）与串是同一概念。s=ATTGCATATG；串的长度|s|; 串s某个位置的字符表示为si ，1 i |s|。特别的，长度为0的串称为空串（empty string），用符号 表示。2. 子串（substring）和子序列（subsequence），二者不是相同的概念。子串和超串s=ATGCGGTA; t=TGCGG; s是t的超串子序列和超序列s=AT

2、GCGGTA; t=TGTA； s是t的超序列区间（interval）s=ATGCGGTACGTATACG; u=CG, si, i+13. 串u和w的拼接(concatenation),表示为uw。例如s = ATGCGGTA; t=TGCGGst = ATGCGGTATGCGGts = TGCGGATGCGGTA串的冥s = AT；sss= AT AT AT=s3串的前缀（prefix）s = ATGCGGTAGC; prefix(s,3)=ATG; prefix(s,0) = 存在且只存在s的另1个子串u, 使得s=tu, t是u的前缀。串的后缀（suffix）s = ATGCGGTAG

3、Csuffix(s,3) =AGC； suffix(s,2) =GC ；suffix(s,0) = 存在且只存在s的另1个子串u, 使得s=ut, t是u的后缀。杀手因子(killer agent)，假定存在1个特别的串 |-1 在与其它串拼接的时候，起到删除相邻字符的作用例如, s = ATGCGGTAGC s= TGCGGTAGCs = ATGCGGTAG ATGC GGTAG ? 无意义 (ATGC ) GGTAG ATGC ( GGTAG )stu=(st)u=s(tu); |s| -1, |t| -1, |u| -1 |st| = |s| + |t| ,s和t可以是任何串利用杀手因子

4、可以表示1个串的子串，前缀和后缀sij= i-1 s |s| -jprefix(s, k) = s |s| -kSuffic(s, k) = |s| -k s 第二节第二节 序序 列列 比比 较较序列比较的根本任务： 发现序列之间的相似性 辨别序列之间的差异序列比较的目的： 相似序列 相似的结构，相似的功能 判别序列之间的同源性 推测序列之间的进化关系 序列的相似性同源（同源（homologyhomology）- - 具有共同的祖先具有共同的祖先直向同源（直向同源（OrthologousOrthologous ） 共生同源（共生同源（paralogousparalogous ）相似（相似（si

5、milaritysimilarity）同源序列一般是相似的同源序列一般是相似的相似序列不一定是同源的相似序列不一定是同源的进化趋同（同功能）进化趋同（同功能）直向同源（直向同源（a1 in species I, a1 in species II)共生同源（共生同源（a1 and a2 in species I）进化趋同进化趋同水平转移水平转移基因复制基因复制序列相似性的描述序列相似性的描述 定性的描述定性的描述 定量的数值定量的数值 相似性相似性 距离距离序列比较的基本操作是比对序列比较的基本操作是比对（Alignment） 两个序列的比对是指这两个序列中各个字符的两个序列的比对是指这两个序列

6、中各个字符的一种一一对应关系，或字符的对比排列一种一一对应关系，或字符的对比排列 。例如，设有两个序列：s=GACGGATTAG，t=GATCGGAATAGAlignment2: GA-CGGATTAGGATCGGAATAGAlignment1:GACGGATTAG GATCGGAATAG字母表和序列字母表和序列字母表字母表( (字符或符号集合字符或符号集合) )4字符DNA字母表：A, C, G, T扩展的遗传学字母表或IUPAC编码单字母氨基酸编码符 号含 义说 明GGGuanine AAAdenine TTThymine CCCytosineRG or APurine YT or CPy

7、rimidine MA or CAmino KG or TKeto SG or CStrong interaction (3 H bonds) WA or TWeak interaction (2 H bonds) HA or C or TNot-GBG or T or Cnot-AVG or C or Anot-T(not-U) DG or A or Tnot-C NG or A or T or CAny 扩展的遗传学字母表或扩展的遗传学字母表或IUPACIUPAC编码编码序列比对的生物学背景分子生物学实验技术和大规模测序方法的发展，使复杂序列之间的比较成为实验室的常规数据分析。基因组学的发

8、展，物理图谱的构建，DNA的拼接求。一个或一些序列与其它数据序列的比较。两个序列之间是否存在相同的子串。个序列与数据库中序列是否存在相似的子串。 序列比较可以分为五种基本情况序列比较可以分为五种基本情况：（1 1）两条长度相近序列相似性分析，找出序列的差别）两条长度相近序列相似性分析，找出序列的差别（2 2）判断一条序列的前缀与另一条序列的后缀相似）判断一条序列的前缀与另一条序列的后缀相似（3 3）判断一条序列是否是另一条序列的子序列）判断一条序列是否是另一条序列的子序列（4 4）判断两条序列中是否有非常相似的子序列）判断两条序列中是否有非常相似的子序列（5 5）对多个序列进行上述）对多个序列

9、进行上述4 4种分析种分析第三第三 节节 两个序列的比较两个序列的比较1. 全局比较基本算法通过全局比对(global alignment)，了解序列的相似性例如，s=ATTGCATATG；t=ATTGATATCs=ATTGCATATGt=ATTG ATATC记分系统的引入与比对打分匹配1空配2错配1对s, t进行相似性比较，得到的最大记分值，称为2序列的相似性，表示为sim(s, t)=maxscore is=ATTGCATATG； s=ATTGCATATG t=ATTG ATATC; t=ATTG ATATC8(-2)(-1)=5 4+ (-2) + (-1) 5 =-12. 局部比较序列

10、s和t的局部比较是通过局部比对(local alignment)实现的，是s和t子串之间的比对。例如，s=AATTGCATATG；t=ATTGT，对它们进行局部相似性比较，表示s(2,3,4,5)=t(1,2,3,4)3. 半全局部比较序列s和t的比对，序列长度相差较大例如，s=AATTGCATATG；t=ATTGT，对它们进行全局相似性比较，表示s=AATTGCATATG； s=AATTGCATATGt= - ATTGT - - - - - ； t= A- TTG - - T - - -半全局比对的核心是2个序列前缀与后缀第四第四 节节 相似性和距离相似性和距离1. 相似性 相似性的度量是基

11、于比对，2个序列的相似性可以由sim(s, t)maxscore i2. 距离 对任何的一个串实施一系列的变换后，可以转化为另一个串 s t; t=AGCTT; s=TTA TTA - - TTA AGTTA AGCTAAGCTT变换的操作： 1 字符的替换 2 空格插入和删除 给予每个变换特定的开销(cost) dist(s,t)=mincost i扩展的编辑操作ACCGACAATATGCATA ATAGGTATAACAGTCAACCGACAATATGCATA ACTGACAATATGGATA 第二条序列头尾颠倒可以通过基本操作实现 反向互补序列反向互补序列RNA发夹式二级结构发夹式二级结构

12、第五节第五节 通过点矩阵进行序列比较通过点矩阵进行序列比较“矩阵作图法矩阵作图法” ” 或或 “ “对角线作图对角线作图” 序列序列1 序列序列2 实实 例例 序列序列1 序列序列1 自我比较自我比较滑动窗口技术滑动窗口技术两条序列中有很多匹配的字符对，因而在点矩阵中两条序列中有很多匹配的字符对，因而在点矩阵中会形成很多点标记。会形成很多点标记。滑动窗口技术滑动窗口技术使用滑动窗口代替一次一个位点的比较是解决这个使用滑动窗口代替一次一个位点的比较是解决这个问题的有效方法。问题的有效方法。假设窗口大小为假设窗口大小为1010，相似度阈值为，相似度阈值为8 8，则每次比较，则每次比较取取1010个

13、连续的字符，如相同的字符超过个连续的字符，如相同的字符超过8 8个，则标个，则标记记基于滑动窗口的点矩阵方法可以明显地降低点阵图基于滑动窗口的点矩阵方法可以明显地降低点阵图的噪声，并且明确无误的指示出了两条序列间具有的噪声，并且明确无误的指示出了两条序列间具有显著相似性的区域。显著相似性的区域。 （a a）对人类（）对人类（Homo sapiensHomo sapiens）与黑猩猩（）与黑猩猩（Pongo pygmaeusPongo pygmaeus）的）的球蛋白基球蛋白基因序列进行比较的完整点阵图。（因序列进行比较的完整点阵图。（b b）利用滑动窗口对以上的两种球蛋白基）利用滑动窗口对以上的

14、两种球蛋白基因序列进行比较的点阵图，其中窗口大小为因序列进行比较的点阵图，其中窗口大小为1010个核苷酸，相似度阈值为个核苷酸，相似度阈值为8 8。 (a) (b) 具有连续相似区域的两条具有连续相似区域的两条DNADNA序列的简单点阵图序列的简单点阵图第六节第六节 DNA片断的组装片断的组装1. 生物学背景 DNA测序技术的发展2. 片断的组装(fragment assembly) 片断（fragment）的产生理想情况 例如ATTGGGCA; CGATT; TGGGCAGA组装 - - ATTGGGCA - -CGATT - - - - - - - - - - - TGGGCAGACGAT

15、TGGGCAGA 表决序列 复杂情况 碱基识别错误 序列方向未知 重复序列 缺乏覆盖 序列污染 复杂情况的组装模型 最短公共超串(shortest common superstring) 重构(reconstruction) 多连叠(multicontig) DNA序列分析基因序列基因表达调控信息 寻找基因牵涉到两个方面的工作寻找基因牵涉到两个方面的工作 ：识别与基因相关的特殊序列信号预测基因的编码区域结合两个方面的结果确定基因的位置和结构 基因表达调控信息隐藏在基因上游区域，在组成上基因表达调控信息隐藏在基因上游区域，在组成上具有一定的特征，可以通过序列分析识别这些特征。具有一定的特征，可以

16、通过序列分析识别这些特征。 在DNA序列中，除了基因之外，还包含许多其它信息，这些信息大部分与核酸的结构特征相关联，通常决定了DNA与蛋白质或者DNA与RNA的相互作用。 存放这些信息的DNA片段称为功能位点如启动子（Promoter）、基因终止序列（Terminator sequence）、剪切位点（Splice site）等。发现重复元素数据库搜索分析功能位点序列组成统计分析综合分析一个基本的DNA序列分析方案 功能序列分析的准确性来自于对“功能序列”和“非功能序列”的辨别能力。 两个集合： 训练集（training set） 用于建立完成识别任务的数学模型。测试集或控制集（control

17、 set） 用于检验所建模型的正确性。 用训练集中实例对预测模型进行训练，使之通过学习后具有正确处理和辨别能力。然后，用模型对测试集中的实例进行“功能”与“非功能”的判断，根据判断结果计算模识别的准确性。收集已知的功能序列和非功能序列实例收集已知的功能序列和非功能序列实例（这些序列之间是非相关的（这些序列之间是非相关的 ）训练集训练集（training set）测试集或控制集测试集或控制集（control set）建立完成识别任务的模型建立完成识别任务的模型检验所建模型的正确性检验所建模型的正确性对预测模型进行训练，对预测模型进行训练，使之通过学习后具有使之通过学习后具有正确处理和辨别能力。正

18、确处理和辨别能力。进行进行“功能功能”与与“非功能非功能”的的判断，根据判断结果计算判断，根据判断结果计算模识别的准确性。模识别的准确性。识别识别“功能序列功能序列”和和“非功能序列非功能序列”的过程的过程 Sn 敏感性敏感性 Sp 特异性特异性 Tp是正确识别的功能序列数， Tn为正确识别的非功能序列数， Fn是被错误识别为非功能序列的功能序列数， Fp是被错误识别为功能序列的非功能序列数。pnnpnppnFTTSFTTS敏感性和特异性的权衡 对于一个实用程序，既要求有较高的敏感性，也要求有较高的特异性。 如果敏感性很高，但特异性比较低，则在实际应用中会产生高比率的假阳性； 相反，如果特异性

19、很高，而敏感性比较低，则会产生高比率的假阴性。 对于敏感性和特异性需要进行权衡，给出综合评价指标。 功能位点分析功能位点分析 功能位点（functional site） 与特定功能相关的位点，是生物分子序列上的一个功能单元，或者是生物分子序列上一个较短的片段。 功能位点又称为功能序列（functional sequence）、序列模式（motif）、信号（signal）等。 核酸序列中的功能位点包括转录因子结合位点转录因子结合位点、转录剪切位点转录剪切位点、翻译起始位点翻译起始位点等。 在蛋白质序列分析中，常使用序列模式这个名词，蛋白质的序列模式往往与蛋白质结构域或者作用部位有关。功能位点示意

20、功能位点示意 基因组序列中若干个相邻的功能位点组合形成功能区域（functional region）。 功能位点分析的任务 发现功能位点特征 识别功能位点A 利用共有序列搜索功能位点 共有序列（common consensus）又称一致性片段 共有序列是关于功能位点特征的描述，它描述了功能位点每个位置上核苷酸进化的保守性 例如: NTATN 利用共有序列进行功能位点分析牵涉到两个方面的问题， 如何构造共有序列 如何利用共有序列在给定的核酸序列上搜索寻找功能位点，并计算所找到的功能位点的可靠性 共有序列具有以下几个方面的特征：（1）共有序列中既有保守的位置，也有可变的位置；（2）任何位置上的核苷

21、酸可以用15种类型之一来表示：核苷酸表示符号核苷酸表示符号符符 号号含含 义义说说 明明GG腺嘌呤腺嘌呤AA鸟嘌呤鸟嘌呤TT胸腺嘧啶胸腺嘧啶CC胞嘧啶胞嘧啶RG or A嘌呤嘌呤YT or C嘧啶嘧啶MA or C氨基氨基KG or T羧基羧基SG or C强氢键强氢键(3个氢键个氢键)WA or T弱氢键弱氢键(2个氢键个氢键)HA or C or T非非GBG or T or C非非AVG or C or A非非T(非非U)DG or A or T非非CNG or A or T or C任意碱基任意碱基 共有序列构造过程: (1) 初始化共有序列为一系列可变位置，以“N”代表(2) 在可变

22、位置寻找出现次数最多的核苷酸，并将该位置转化为保守位置(3) 对当前所得到的共有序列进行特异性检查，若通过检查，转（5），否则转（4）(4) 形成与当前共有序列一致的位点子集，剔除不一致的位点子集，转（2）(5) 从原位点集合中删除与当前共有序列一致的位点，用确定的碱基替换“N”；若还有剩余位点，则转（1），构造另外的共有序列。TTATGATATATACGCTTGTC TCCAC TTATGATATATACGCTTGTC TCCAC TNNNN tTATG tACGC tTGTC tCCAC tTATG tACGC tTGTC tCCAC TNNNC 1 2 3 4 2 3 NNNNNTNN

23、NN非特异非特异 TNNNC非特异非特异 tACGc tTGTc tCCAc 4 2 tACGc tTGTc tCCAc 3 TNSNC 特异特异 5 Consensus1： TNSNC 剩余位点：剩余位点： TTATG ATATA 5 Consensus2： NTATN TNSNC 在给定的序列中搜索与共有序列一致的序列片段 数据库搜索 共有序列表示方法的缺点： 是关于序列特征的一种定性描述，对于DNA序列，它能够说明序列每个位置可能出现的碱基类型，但是不能准确地说明各位置上不同类型碱基出现的可能性大小。B 用感知矩阵分析功能位点 用权系数描述功能位点各位置上每种核苷酸的相对重要性 感知矩阵

24、（或加权矩阵） 根据一系列功能位点的多重对比排列结果而建立的 其大小为4n 4代表碱基的种类数目，n代表功能位点的长度 矩阵的每一个元素M(aj,j)的值代表第a种核苷酸在功能位点第j个位置上出现的得分,a A,T,G,C。123456A18227-319T26142-10G3110-50-19C5-916880感知矩阵示例感知矩阵示例 对于一个序列s=a1a2an，根据对应位置上核苷酸的类型，取感知矩阵中对应的权值，加和以后得到该序列的得分 设S=ATTGCA，则 Ws = 1+6+14-5+8+19=43 T功能位点阈值 T非功能位点阈值 如果Ws T，则S是功能位点； 如果Ws T，则S

25、是非功能位点。njjsjaMW1),(感知矩阵感知矩阵M的构造算法的构造算法令A+代表功能位点集合 A-代表非功能位点集合 过程如下： （1）初始化M为零矩阵； （2）执行过程（3）-（6）的循环； （3）逐步取训练集合中的每个实例Si，如果Si A+，转 过程（4）；如果Si A-，转过程（5）； （4）如果W（Si） T，M不变，否则根据Si的核苷酸分布将M中所有对应元素的值加1；转（6）； （5）如果W（Si） T，M不变，否则根据Si的核苷酸分布将M中所有对应元素的值减1；转（6）； （6）若训练集合中的所有实例都处理过，则循环结束，转（7），否则继续执行循环体，直到处理完所有实例；

26、（7）如果M稳定，则结束；否则转（2）。 上述算法反复调整感知矩阵M的元素值，直到M矩阵能够正确识别训练集中的所有功能位点和非功能位点。 对于最终得到的感知矩阵，要求其具有敏感性和特异性，每一列上的元素值应该尽可能地有明显的差别，以便反应功能位点各个位置上的特点。基因识别的一般方法基因识别的一般方法 基因识别是生物信息学领域里的一个重要研基因识别是生物信息学领域里的一个重要研究内容究内容 生物学背景生物学背景 基因识别问题，在近几年受到广泛的重视基因识别问题，在近几年受到广泛的重视 当当基因组研究进入一个系统测序阶段时，基因组研究进入一个系统测序阶段时，急需可靠自动的基因组序列翻译解释技急需可

27、靠自动的基因组序列翻译解释技术，以处理大量已测定的但未知功能或术，以处理大量已测定的但未知功能或未经注释的未经注释的DNA序列序列 一个开放阅读框（一个开放阅读框（ORF,open reading frame）是一个没有终止编码的密码子序）是一个没有终止编码的密码子序列。列。 原核基因识别任务的重点是识别开放阅读原核基因识别任务的重点是识别开放阅读框，或者说识别长的编码区域。框，或者说识别长的编码区域。(一一) 基于基因密码子特性的识别方法基于基因密码子特性的识别方法辨别编码区域与非编码区域的一种方法辨别编码区域与非编码区域的一种方法检查终止密码子的出现频率检查终止密码子的出现频率 终止密码子

28、出现的期望次数为：终止密码子出现的期望次数为： 每每21个（个（ 64/3）密码子出现一次终止密码子）密码子出现一次终止密码子 基本思想：基本思想： 如果能够找到一个比较长的序列，其相应如果能够找到一个比较长的序列，其相应的密码子序列不含终止密码子，则这段序的密码子序列不含终止密码子，则这段序列可能就是编码区域。列可能就是编码区域。 基本算法：基本算法： 扫描给定的扫描给定的DNA序列，在三个不同的阅读序列，在三个不同的阅读框中寻找较长的框中寻找较长的ORF。遇到终止密码子以。遇到终止密码子以后，回头寻找起始密码子。后，回头寻找起始密码子。 这种算法过于简单，不适合于处理短的这种算法过于简单，

29、不适合于处理短的ORF或者交叠的或者交叠的ORF。(二二) 识别编码区域的另一种方法是分识别编码区域的另一种方法是分析各种密码子出现的频率析各种密码子出现的频率 例如，亮氨酸、丙氨酸、色氨酸分别有例如，亮氨酸、丙氨酸、色氨酸分别有6个、个、4个和个和1个密码子个密码子将一个随机均匀分布的将一个随机均匀分布的DNA序列翻译成氨基酸序列翻译成氨基酸序列，则在氨基酸序列中上述序列，则在氨基酸序列中上述3种氨基酸出现的种氨基酸出现的比例应该为比例应该为6:4:1但是在真实的氨基酸序列中，上述比例并不正确但是在真实的氨基酸序列中，上述比例并不正确这说明这说明DNA的编码区域并非随机的编码区域并非随机 假

30、设在一条假设在一条DNA序列中已经找到所有的序列中已经找到所有的ORF，那么可以利用密码子频率进一步，那么可以利用密码子频率进一步区分编码区分编码ORF和非编码和非编码ORF 利用这种方法，可以计算一个利用这种方法，可以计算一个ORF成成为编码区域的可能性。为编码区域的可能性。一个简单的统计模型一个简单的统计模型假设相继的密码子是独立的，不存在前后依假设相继的密码子是独立的，不存在前后依赖关系。赖关系。 令令fabc代表密码子代表密码子abc在编码区域出现的频率在编码区域出现的频率给定序列给定序列a1,b1,c1, a2,b2,c2, an+1,bn+1从密码子从密码子a1b1c1开始的阅读框

31、，其开始的阅读框，其n个密码子个密码子的出现概率为的出现概率为nnncbacbacbafffp.2221111第二种和第三种阅读框第二种和第三种阅读框n个密码子出现的概率分别为个密码子出现的概率分别为1322211.2nnnacbacbacbfffp11332221.3nnnbacbacbacfffp第第i个阅读框成为编码阅读框的概率个阅读框成为编码阅读框的概率计算：计算：算法：算法：在序列上移动长度为在序列上移动长度为3n的窗口，计算的窗口，计算Pi根据根据Pi的值识别编码的阅读框的值识别编码的阅读框321ppppPii(三三) 基于编码区碱基组成特征的识别方法基于编码区碱基组成特征的识别方

32、法 编码序列与非编码序列在碱基组成上有区别编码序列与非编码序列在碱基组成上有区别 单个碱基的组成比例单个碱基的组成比例 多个碱基的组成多个碱基的组成通过统计分析识别编码序列通过统计分析识别编码序列分析实例分析实例 真核基因识别的复杂性真核基因识别的复杂性 真核基因远比原核基因复杂：真核基因远比原核基因复杂： 一方面，真核基因的编码区域是非连续一方面，真核基因的编码区域是非连续的，编码区域被分割为若干个小片段。的，编码区域被分割为若干个小片段。 另一方面，真核基因具有更加丰富的基另一方面，真核基因具有更加丰富的基因调控信息，这些信息主要分布在基因因调控信息，这些信息主要分布在基因上游区域。上游区

33、域。 (一一) 基本思路基本思路 找出基因两端的功能区域找出基因两端的功能区域:转录启动区转录启动区 终止区终止区 在启动区下游位置寻找翻译起始密码子在启动区下游位置寻找翻译起始密码子 识别转录剪切位点识别转录剪切位点剪切给体位点剪切给体位点剪切接受体位点剪切接受体位点 各种不同的方法有不同的适应面，而不各种不同的方法有不同的适应面，而不同的方法有时可以结合起来以提高基因同的方法有时可以结合起来以提高基因识别的准确率。识别的准确率。 关键问题是如何提高一个识别算法的敏关键问题是如何提高一个识别算法的敏感性（感性（sensitivity，Sn）和特异性）和特异性（specificity，Sp）。

34、）。 (二二) 真核基因识别的主要方法真核基因识别的主要方法两大类识别方法：两大类识别方法： 从头计算方法从头计算方法（或基于统计的方法）（或基于统计的方法） 根据蛋白质编码基因的一般性质和特征进根据蛋白质编码基因的一般性质和特征进行识别，通过统计值区分外显子、内含子行识别，通过统计值区分外显子、内含子及基因间区域及基因间区域 基于同源序列比较的方法基于同源序列比较的方法 利用数据库中现有与基因有关的信息（如利用数据库中现有与基因有关的信息（如EST序列、蛋白质序列），通过同源比较，序列、蛋白质序列），通过同源比较，帮助发现新基因。帮助发现新基因。 最理想的方法是综合两大类方法的优点，开最理想

35、的方法是综合两大类方法的优点，开发混合算法。发混合算法。(三三) 识别编码区域识别编码区域两类方法两类方法 ： 基于特征信号的识别基于特征信号的识别 内部外显子内部外显子 剪切位点剪切位点 5端的外显子一定在核心启动子的下游端的外显子一定在核心启动子的下游 3端的外显子的下游包含多聚信号和终端的外显子的下游包含多聚信号和终止编码止编码 基于统计度量的方法基于统计度量的方法 根据密码子使用倾向根据密码子使用倾向 双联密码统计度量等双联密码统计度量等(四) 构建基因模型 基因识别最终任务是建立完整的基因结构模型 一个理想的基因识别程序应该能够发现完整的基因结构 （,e1, i1, , in-1,

36、en , ） ATG-外显子1内含子外显子外显子n-UAG 基因剪切位点基因剪切位点 剪切给体（剪切给体（donor）位点）位点- “gt” 接受体（接受体（acceptor）位点）位点- “ag”基因的可变剪切基因的可变剪切gene A基因可变剪切示意基因可变剪切示意构建基因模型方法构建基因模型方法 剪切位点形成外显子和内含子的边界剪切位点形成外显子和内含子的边界 搜集候选外显子搜集候选外显子 候选基因候选基因 候选基因是一条非相交的外显子和内含候选基因是一条非相交的外显子和内含子的链，表示为子的链，表示为 （i0, e1, i1, , en, in） 其中其中ij代表内含子（代表内含子（0

37、 j n） el代表外显子（代表外显子（1 l n） i0和和in并非真实的内含子，它们分别代表并非真实的内含子，它们分别代表基因两侧的非编码序列基因两侧的非编码序列 候选基因位于给定的候选基因位于给定的DNA序列，并满足下列一序列，并满足下列一致性条件：致性条件： （1）所有外显子加起来的长度是）所有外显子加起来的长度是3的整数倍；的整数倍； （2）在各个外显子内部（除最后一个外显子的）在各个外显子内部（除最后一个外显子的最后一个密码子），没有终止编码；最后一个密码子），没有终止编码； （3）第一个内含子）第一个内含子-外显子边界（外显子边界（i0, e1）是翻译）是翻译起始编码，而最后一个

38、外显子起始编码，而最后一个外显子-内含子边界（内含子边界（en, in）是终止编码。）是终止编码。位点图位点图（分层标注剪切位点）（分层标注剪切位点）另设两个特殊的顶点，即起点（另设两个特殊的顶点，即起点（source）和终点（）和终点（sink）。从起点到终点的任何一条路径代表一个可能的基因结构。从起点到终点的任何一条路径代表一个可能的基因结构。例如例如： 位点图上的路径位点图上的路径候选基因所对应的道路图中的路径候选基因所对应的道路图中的路径求最优路径求最优路径 每一条弧附加一个权值每一条弧附加一个权值外显子、内含子度量 每个节点附加权值每个节点附加权值剪切位点度量 综合评价综合评价 (五) 基于剪切比对的基因识别方法 基本思想是：利用数据库中的同源信息进行基因识别，包括DNA、RNA和蛋白质数据库。 其方法是： 首先通过分析所有可能的剪切接受体位点和剪切给体位点，构建一组候选的外显子。 然后进一步分析候选外显子，寻找所有可能的外显子组合，寻找一个与已知目标蛋白质或其他表达序列最匹配的组合 。基因识别程序介绍基因识别程序及访问地址基因识别程序及访问地址（HP主页；主页；ESE-mail服务器；服务器；WSweb服务器；服务器；CL客户客户/服务服务器协议；器协议；EX有可执行代码；有可执行代码