生物信息学第四章序列比对与算法

第四章序列比对与算法生物科学与技术学院布什和猩猩的“比对”什么是序列比对(sequenceAlignment)▪早在1950s就有人进行序列比对，如oxytocin(催产素，CYIQNCPLG)和Asopressin(后叶加压素，CYFQNCPRG)；羊的corticotropin(促肾上腺皮质激素，AGEDDE)和猪的corticotropin(DGAEDE)。AG-EDDE||||DGAE-DEAG-EDDE||||DGAED-ECYIQNCPLG|||||||CYFQNCPRG比对的不确定性2、发现蛋白质的基序(motif)和域(Domain)，如锌指结构基序，在数据库里搜索类似序列序列比对：为评价相似性(similarity)的程度或同源性(homology)的可能，将两个或更多的序列排列起来以得到最大一致性(identity)（即相同或相似性）的过程。homologyorthologyparalogyFrog-αchick-αmouse-αmouse-βchick-βFrog-βorthology▪序列比对是最基本的生物信息学操作，其作用是：1、发现序列之间的结构或功能相关性，以进一步探索同源性和进化关系；同源性(homolog)：序列源于共同的祖先而产生的相似性直系(直向)同源(orthology)：同祖同功不同种[如哺乳动物的胰岛素基因]旁系(共生)同源(paralogy)：同祖同种不同功[如起源于珠蛋白的α珠蛋白和肌红蛋白]序列比对可分为：1、双序列比对2、多序列比对3、全局比对4、局部比对序列比对双序列比对多序列比对全局序列比对局部序列比对全局序列比对局部序列比对1、计分矩阵(scoringmatrix)计分矩阵也叫替换矩阵(substitutionmatrix)，用来给一个比对打分，以衡量两个序列相似程度，由大量训练集比对产生，最有名的是PAM和BLOSUM。训练集用于建立模型，测试集用于评估模型。随机选出一些数据作为模型（训练集），发现其规律，然后把剩下的数据作为一个类似模型（就叫测试集），计算检测这个模型的规律与训练集的误差等，从而确定这个规律是否正确（机器学习方法）。PAM(“Point-Acceptedmutations”)由Dayhoff等(1978)根据相近的序列进行全局比对(globalAlignment)产生的。其中PAM1是从差别不大于1%的序列比对产生，其他的PAM矩阵都由PAM1外推得到，如PAM0、PAM10、PAM250、PAM2000、…BLOSUM(blockssubstitutionmatrix)由序列进行局部比对(localAlignment)产生，BLOSUM62是从差别不小于62%的序列比对产生，其余类推，如BLOSUM30、BLOSUM80、…PAM1矩阵（替换矩阵）ARNDCQEGHIA9867291038172126R199131011000103N419822360466213D604298590653641C1100997300011Q394509876271231E1007560359865423G2111211137993510H181831201099120I2231212009872矩阵的元素表示由原来的氨基酸(上行，蓝色)替换为另一个氨基酸(左列，绿色)的概率例CKHVFCRVCICKKCFC-KCVCKHVFCRVCICKKCFCK-CVC-KHVFCRVCICKKC-FC-CKVCKH-VFCRVCICKKC-FC-KCVCKHVFCRVCICKKCFCKCVScorewithPAM250andgappenalty-10计算如下比对CKHVFCRVCICKKCFC-KCVCKHVFCRVCICKKCFCK-CVC-KHVFCRVCICKKC-FC-CKVCKH-VFCRVCICKKC-FC-KCVScorewithPAM250andgappenalty-1036+5+0–2+9–2+5–10=4136+5+0–2+9+5+4–10=4736+5–3+9–2+4–3x10=1936+5+0+9–2+4–3x10=22Gappenaltyisimportant;biologydoesnotlikegapsBLOSUM62较为著名，其是BLAST的缺省矩阵，对亲缘远近的序列性能都很好。BLOSUM62（替换矩阵）A4R-15N-206D-2-216C0-3-3-39Q-1100-35E-1002-425G0-20-1-3-2-26H-201-1-300-28I-1-3-3-3-1-3-3-4-34L-1-2-3-4-1-2-3-4-324K-120-1-111-2-1-3-25M-1-2-2-3-10-2-3-212-15F-2-3-3-3-2-3-3-3-100-306P-1-2-2-1-3-1-1-2-2-3-3-1-2-47S1-110-1000-1-2-20-1-2-14T0-10-1-1-1-1-2-2-1-1-1-1-2-115W-3-3-4-4-2-2-3-2-2-3-2-3-11-4-3-211Y-2-2-2-3-2-1-2-32-1-1-2-13-3-2-227V0-3-3-3-1-2-2-3-331-21-1-2-20-3-14ARNDCQEGHILKMFPSTWYV练习CKHVFCRVCICKKCFC-KCVCKHVFCRVCICKKCFCK-CVC-KHVFCRVCICKKC-FC-CKVCKH-VFCRVCICKKC-FC-KCVScorewithBLOSUM62andgappenalty-10A4R-15N-206D-2-216C0-3-3-39Q-1100-35E-1002-425G0-20-1-3-2-26H-201-1-300-28I-1-3-3-3-1-3-3-4-34L-1-2-3-4-1-2-3-4-324K-120-1-111-2-1-3-25M-1-2-2-3-10-2-3-212-15F-2-3-3-3-2-3-3-3-100-306P-1-2-2-1-3-1-1-2-2-3-3-1-2-47S1-110-1000-1-2-20-1-2-14T0-10-1-1-1-1-2-2-1-1-1-1-2-115W-3-3-4-4-2-2-3-2-2-3-2-3-11-4-3-211Y-2-2-2-3-2-1-2-32-1-1-2-13-3-2-227V0-3-3-3-1-2-2-3-331-21-1-2-20-3-14ARNDCQEGHILKMFPSTWYV（1）建立矩阵sequence1ABCNJRQCLCRPMsequence2AJCJNRCKCRBP行列字母相同就填1PAM1矩阵（非替换矩阵）的比对过程（2）给矩阵打分倒数第一行剩余空格填0自右向左填倒数第二行，即每一格取它的“子行”中的最大值，再加本身的值。其子行为阴影部分自右向左填倒数第三行，即每一格取它的“子行”和“子列”中的最大值，再加本身的值。其子行和子列为阴影部分其子行和子列为阴影部分得到优化比对从最大的数值开始，按同样的方法回溯找到最优化路径sequence1ABCNJ-RQCLCR-PMsequence2AJC-JNR-CKCRBP-sequence1ABC-NJRQCLCR-PMsequence2AJCJN-R-CKCRBP-（3）得到优化比对课堂练习：Sequence1：ACTGCTAAACGTSequence2：ACCGTCAGATACTGCTAAACGTA1111C111C111G11T111C111A1111G11A1111T111ACTGCTAAACGTA1111C111C111G11T111C111A1111G11A1111T001001000001ACTGCTAAACGTA1111C111C111G11T111C111A1111G11A432221222110T001001000001ACTGCTAAACGTA1111C111C111G11T111C111A1111G322322221120A432221222110T001001000001ACTGCTAAACGTA1111C111C111G11T111C111A433222333210G322322221120A432221222110T001001000001ACTGCTAAACGTA755543444210C665553333310C565453333310G554543333220T445434333211C343343332310A433222333210G322322221120A432221222110T001001000001Sequence1：ACTGCT-A-AACGTSequence2：ACCG-TCAGA---TSequence1：ACTG-CTA-AACGTSequence2：ACCGTC-AGA---TSequence1：ACTG-CTA-AACGTSequence2：ACCGTC-AG-A--T混乱原因：计分方式？算法本身？（局部比对）……………………作业：Sequence1：ACTGCTACGTSequence2：ACCGTCAGATACTGCTACGTA11C111C111G11T111C111A11G11A11T1112、汉明距离汉明距离(Hammingdistance)：是两个字符串对应位置的不同字符的个数。汉明距离忽略了DNA中的插入、删除和替换的现象。如：序列V：ATATATAT序列W：TATATATAdH(v,w)=8，8指不同字符的个数，但从这两个序列发现其具有很大的相似性。如果通过简单的移位，则：序列V：--ATATATAT序列W：TATATATA--此时dH(v,w)=2。例ACTGCTAAACGTA755543444210C665553333310C565453333310G554543333220T445434333211C343343332310A433222333210G322322221120A432221222110T001001000001序列V：AAACGT序列W：AGAT----dH(v,w)=4移动序列V：AAACGT序列W：AGA---TdH(v,w)=3序列V：AAACG--T序列W：A-----GATdH(v,w)=4序列V：AAACG--T序列W：---A--GATdH(v,w)=43、编辑距离编辑距离(EditDistance)：将一个字符串变为另一个字符串的最少基本操作(包括插入、删除、替代）数目。如序列TGCATAT序列ATCCGAT的编辑操作步骤：Step1：TGCATA(deletelastT)Step2：TGCAT(deletelastA)Step3：ATGCAT(insertAatfront)Step4：ATCCAT(substituteCfor3rdG)Step5：ATCCGAT(insertGbeforelastA)=================Step1：ATGCATAT(insertAatfront)Step2：ATGCATA(delete6thT)Step3：ATGCGTA(substituteGfor5thA)Step4：ATCCGTA(substituteCfor3rdG)编辑距离是5吗？编辑距离可以是3吗？--TGC--ATATATCCGAT----dH(v,w)=5--TGCATATATCC--GATdH(v,w)=44、比对网络通过对网格中街道的每一个交叉点引入一个顶点，可以构建一个图，称之为编辑图(editgraph)，此方法基于曼哈顿游客问题的动态规划算法。曼哈顿游客问题如何设计路径使游客能够游览到所有景点（*）而不走重复的路径。例：序列V=ATGTTAT序列W=ATCGTAC0123456701234567ATCGTACATGTTAT0122345677VAT-GTTAT-WAACGT-A-C0123455667序列W序列V012