PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

暮卜
5 years ago
Views:

1 生物信息学序列分析与比对吴凌云中国科学院数学与系统科学研究院

2 目录序列的组成单一序列分析序列比对序列搜索多序列比对

3 碱基分类嘌呤 (purine) A:adenine, 腺嘌呤, 氨基, 弱键 G:guanine, 鸟嘌呤, 酮基, 强健嘧啶 (pyrimidine) C:cytosine, 胞嘧啶, 氨基, 强健 T:thymine, 胸腺嘧啶, 酮基, 弱键氨基 : A, C / 酮基 : T, G 弱键 : A, T / 强键 : C, G

4 IUB/IUPAC 代码代码碱基说明 R A 或 G 嘌呤 Y T 或 C 嘧啶 W A 或 T 弱键 S C 或 G 强键 M A 或 C 氨基 K G 或 T 酮基 B C,G 或 T 非 A D A,G 或 T 非 C H A,C 或 T 非 G V A,C 或 G 非 T N A,G,C 或 T 任意碱基

5 碱基分布四个碱基的分布不同相邻碱基的分布不独立与遗传密码的关系

6 目录序列的组成单一序列分析序列比对序列搜索多序列比对

7 重复序列 (repeats) 重复序列的查找记分法 (Karlin 1983) A, C, G, T: 0, 1, 2, 3 逐步查找长度为 k 的重复,k=2,3,

8 重复序列 (repeats) 最长重复序列的统计学估计用于搜索重复序列时 k 的初始值

9 几何学分析碱基计数第 n 个碱基对应的点 :

10 几何学分析

11 几何学分析大肠杆菌 ayop 基因族序列 Z 曲线的三个分量

12 目录序列的组成单一序列分析序列比对序列搜索多序列比对

13 什么是比对? 为了评估序列的相似程度和同源的可能性, 将两个或者多个序列排列起来, 以得到最高级别的一致性 ( 在氨基酸序列中为保守性 ) 一致性 : 两个序列保持不变的区域保守性 : 序列中某个位置的氨基酸发生了改变, 但保留了原来残基的物理化学性质

14 Why align sequences? Functional predictions based on identifying homologues Assumption: Conservation of sequence Conservation of function DNA Sequence Protein Structure

15 Implicit Assumption DNA Sequence Protein Structure DNA Sequence Protein Structure

16 Sequence Similarity How to measure sequence similarity? What s the last common ancestor? a a g t a a a g c t t g a g g a c g a g t a a g c t t c g a g g a c g a g t a a a g c t g g a g g a c

17 Last Common Ancestor a a g t a a a g c t t - g a g g a c g a g t a a - g c t t c g a g g a c g a g t a a a g c t g - g a g g a c? g a g t a a a g c t t g a g g a c

18 Sequence Evolution

19 Infer Edit Operators

20 Methods Dot matrix analysis (intuitive) DP algorithm (exact) Word or k-tuple (FASTA, BLAST) (heuristic)

21 Dot Matrix G T T C A G C T G C G T A C G A T C A A C T G A C G T A

22 Filtered Dot Matrix G T T C A G C T G C G T A C G A T C A A C T G A C G T A 4 bases window 3 stringency

23 Dot Matrix with Real Data The amino acid sequences of the phage λci (horizontal sequence) and phage P22 c2 (vertical sequence) repressors. The window size and stringency are both 1.

24 Global vs. Local

25 Needleman-Wunsch 算法

26 Needleman-Wunsch 算法例子

27 Needleman-Wunsch 算法例子

28 Smith-Waterman 算法

29 Smith-Waterman 算法例子

30 Smith-Waterman 算法例子

31 算法比较 Needleman-Wunsch 1. 全局比对 2. 距离分数 : 必须非负 3. 不需要 gap 惩罚 4. 在一条路径中分数不会减少 Smith-Waterman 1. 局部比对 2. 相似性分数 : 可以是正数或者负数 3. 必须有 gap 惩罚 4. 在一条路径中分数可能增加减少或者不变

32 Substitution Matrix PAM (Point Accepted Mutations) Based on substitution data from alignment between similar proteins 1% expected substitutions = 1PAM PAMn = (1PAM) n BLOSUM (BLOck Scoring Matrix) Multiple alignment of distantly related proteins BLOSUMn = sequences with n% or more of identical residues were clustered to compute log-odds ratio

33 Substitution Matrix

34 目录序列的组成单一序列分析序列比对序列搜索多序列比对

35 序列搜索将查询序列和数据库中的所有记录进行比对将每个比对打分按照分值对数据库中的所有记录排序报告具有高分值的那些数据库记录

36 BLAST 主页

37 BLAST 算法 BLAST 使用预先索引好的数据库每个单词在数据库记录中的位置都已经被记录下来将待查询的序列分解成单词在数据库中搜索相似的单词, 用替换矩阵 (substitution matrix) 进行打分, 相似的要求为分值不低于阈值 T

38 BLAST 算法查询序列中两个不重叠的单词, 而且相互距离在一定范围内, 如果都与数据库中的记录匹配上, 而且之间没有间隙, 则该区域称为 segment pair 将 segment pair 向两个方向扩展, 直到其分值比其最高值下降了 X 报告所有 E value 低于指定值的结果

39 High-scoring Segment Pair

40 BLAST 算法的参数单词长度 W DNA 序列 :W=11 蛋白质序列 :W=3 Segment pair 的最低分值 T 较低的 T 可以查找更远的相似关系 Segment pair 扩展截止 X 较高的 X 可以增加 HSP 的长度 E value 过滤阈值对分值没有影响, 只影响报告的结果数量

41 E value 在数据库中随机进行搜索时, 找到分值高于或等于 S 的不同比对的期望次数 E value 越小, 则该分值的统计显著性越大和查询序列的长度有关

42 极值分布 (EVD) the sum of a large number of independent identically distributed (i.i.d) random variables tends to a normal distribution the maximum of a large number of i.i.d. random variables tends to an extreme value distribution

43 Bit scores 标准化后的 HSP 分数等价于如下的极值分布

44 P-value 在数据库搜索中, 发现至少一个相同分值或者更高分值的比对发生的概率 E-value 比 P-value 直观当 E<0.01 时, 两者很接近

45 BLAST 程序 Sequence Database blastn nucleotide nucleotide blastp protein protein blastx nucleotide protein tblastn protein nucleotide tlbastx nucleotide nucleotide PSI-blast protein protein PHI-blast protein protein

46 FASTA 算法速度介于 Smith-Waterman 算法和 BLAST 之间敏感度 (sensitivity) 也介于 Smith- Waterman 算法和 BLAST 之间是 Smith-Waterman 算法的快速近似 FASTA 算法可以进行全局比对, 而 BLAST 只是局部比对

47 FASTA 算法 (step 1)

48 FASTA 算法 (step 2)

49 FASTA 算法 (step 3)

50 FASTA 算法 (step 4)

51 目录序列的组成单一序列分析序列比对序列搜索多序列比对

52 多序列比对 (MSA) Needleman-Wunsch 算法和 Smith-Waterman 算法可以直接推广到 K 条序列比较 DP 算法的计算复杂性从 O(n 2 ) 增长为 O(n k ) k>6 基本上就无法求解 MSA 问题是 NP-hard( 对于 k 来说 )

53 解决方法启发式算法 (heuristic) 固定参数复杂性 (fixed parameter complexity) 多项式时间近似算法 (polynomial time approximation algorithm)

54 启发式算法 (1) Bains (1986): consensus alignment 每个序列都和 consensus 序列做比对产生新的 consensus 直到 consensus 不再变化依赖于每个序列比对的顺序

55 启发式算法 (2) Higgins and Sharp (1989): Clustal 计算所有两两比对的分值建立相似性矩阵, 对序列进行聚类用 consensus 方法对类进行比对对类中的序列依次进行比对 ClustalW: 局部比对 ClustalV: 全局比对

56 MSA 和进化树 MSA 的结果会影响进化树的推断不同的进化树会导致不同的 MSA 鸡和蛋的问题同时考虑 MSA 和构建进化树 Jotun Hein: TREEALIGN

57 MSA 数据格式 TGCACACATGT TGCACACATGT

58 Partial Order Alignment

61 Progressive Aligment

62 一些网址 BLAST EMBOSS (Pairwise Alignment): ClustalW (Multiple Alignment):

63 生物信息学基因识别吴凌云中国科学院数学与系统科学研究院

64 Gene Finding Homology sequences (BLAST) Statistical difference of sequences Gene Prediction (HMM)

65 CpG Island 大约 70% 的人类启动子区域有很高的 CpG 含量.

66 离散 Markov 过程

67 Hidden Markov Model

68 HMM

69 HMM 的三大问题

70 HMM for CpG Island

71 Structure of Typical Gene

72 Genescan

73 Accuracy on Vertebrate Genes Accuracy per nucleotide Accuracy per exon Method Sn Sp AC Sn Sp (Sn+Sp)/2 ME WE GENSCAN FGENEH GeneID GeneParser GenLang GRAILII SORFIND Xpound

74 生物信息学 Motif 预测吴凌云中国科学院数学与系统科学研究院

75 What are Motifs Motifs: a recurring element in bio-sequence or structure A motif typically has functional implications since it is preserved (recurring) during evolution There are different types of motifs in biological data sequence motifs structure motifs network motifs

76 Sequence Motif DNA sequence motifs: they generally function as regulatory elements in biological systems transcription regulatory motifs Protein sequence motifs: they are generally functional sites

77 Transcription Regulation

78 Transcription Factors Different classes of transcription factors regulate the on and off of transcription as well as the efficiency activators (general or specific) enhancers (general or specific) repressors (general or specific) inhibitors (general or specific) specificity regulators

79 Transcription Factors A transcription factor could regulate multiple genes Knowing the genes regulated by a transcription factor can help to elucidate a biological process responsible for a complex task a systems biology view

80 Regulatory Binding Site In a genome, find genes that are transcriptionally (co-)regulated by the same transcription factor Identify genes sharing common regulatory binding sites Binding sites of the same transcription factor does not have to be exactly the same in their sequences; rather they should be conserved

81 Identify Motif

82 Sequence Logo

83 Problem A group of sequence motifs are considered as conserved if their aligned positions have high information content How to find blocks of DNA that have high information content? Simple if the sequences are already aligned! But How to find the conserved sites?

84 Brute-force Method Basic idea assume that we know that the length of the conserved sites is K (K typically from 5 to 30) go through all possible combinations of K-mers, one K-mer from each sequence, and calculate the information content call a particular combination a conserved site if the IC is high Too many combinations to consider!

85 Approaches Heuristic methods Multiple sequence alignment MEME Suite

Microsoft PowerPoint - 04 Models of Amino Acid and Codon Substitution.ppt

Microsoft PowerPoint - 04 Models of Amino Acid and Codon Substitution.ppt Nei and Gojobori(986) ATG GTC ACT CAT TTA ATA AAT CGG ATA TAA M V T H L I N R I * ATG GTT ACG CAA CTC ATG ACG AGG ATT TGA M V T Q L M T R I * Pathway I: Pathway II: Pathway I: Pathway II: AAT(N) ACT(T)