生物信息学生物信息学算法：数据库检索高歌北京大学生物信息学算法：数据库检索●问题的提出●BLAST：实例●BLAST：算法()()()()()()⎪⎩⎪⎨⎧+-+-+--==d j i F dj i F y x s j i F j i F F j i 1,,1,1,1max ,00,0()()()()()()⎪⎪⎩⎪⎪⎨⎧+-+-+--==01,,1,1,1max ,00,0d j i F dj i F y x s j i F j i F F j i 全局比对 (Needleman-Wunsch)局部比对(Smith-Waterman)( 改自Russ Altman BMI214)S T S - - T→相似的结构→相似的功能The “Sequence-to-Structure-to-Function Paradigm”→共同的祖先A→相似的结构→相似的功能The “Sequence-to-Structure-to-Function Paradigm”→共同的祖先序列数据库检索查询序列取一条数据库中的序列进行双序列（全局/局部）比对()1,1--j i F ()j i F ,()j i F ,1-()1,-j i F dd()j i y x s ,XY()()()()()()⎪⎩⎪⎨⎧+-+-+--==d j i F dj i F y x s j i F j i F F j i 1,,1,1,1max ,00,0x i 比对到 y j x i 比对到空位 y j 比对到空位动态规划矩阵(dynamic programming matrix)大小为n ×m查询序列 X ：长度为 m数据库序列Y ：长度为 n假定每次操作需要常数时间c ，则一次比较所需的时间为c ×m ×n●假定我们用人血红蛋白α亚基(HBA_HUMAN)作为查询序列，它的长度是142个氨基酸●检索蛋白质数据库 Swiss-Prot，其中包含 540958 条序列，总计192206270个氨基酸(AA)(即平均每条序列长192206270/540958 = 355.30 AA)●以c = 1 us = (0.000001 s)●则一次检索需要约7.8h !()1,1--j i F ()j i F ,()j i F ,1-()1,-j i F dd()j i y x s ,XY()()()()()()⎪⎩⎪⎨⎧+-+-+--==d j i F dj i F y x s j i F j i F F j i 1,,1,1,1max ,00,0x i 比对到 y j x i 比对到空位 y j 比对到空位y xXY()1,1--j i F ()j i F ,()j i F ,1-()1,-j i F d d ()j i y x s ,A GA G 00 0 0 C 40 0 0 G 0 2 2 0 A 00 0 0 G A A(改自/cours/Turin/UniProtKB_Turin.ppt)改自/cours/Turin/UniProtKB_Turin.ppt)2D PAGE 胶图 2DBase-Ecoli ANU-2DPAGE Aarhus/Ghent-2DPAGE (no server) COMPLUYEAST-2DPAGE Cornea-2DPAGE DOSAC-COBS-2DPAGE ECO2DBASE (no server) OGP PHCI-2DPAGE PMMA-2DPAGERat-heart-2DPAGEREPRODUCTION-2DPAGE Siena-2DPAGE SWISS-2DPAGE UCD-2DPAGE World-2DPAGE 蛋白功能域 Gene3D HAMAP InterPro PANTHER Pfam PIRSF PRINTS ProDom PROSITE SMART SUPFAM TIGRFAMs 模式生物数据库 AGDArachnoServer CGDConoServer CTDCYGDdictyBase EchoBASE EcoGene euHCVdb EuPathDB FlyBaseGeneCards GeneDB_Spombe GeneFarm GenoList Gramene H-InvDB HGNCHPALegioList LepromaMaizeGDB MGIMIMneXtProtOrphanet PharmGKB PseudoCAP RGDSGDTAIRTubercuList WormBase Xenbase ZFIN 蛋白家族 Allergome CAZy MEROPS PeroxiBase PptaseDB REBASE TCDB 基因组注释数据库 Ensembl EnsemblBacteria EnsemblFungi EnsemblMetazoa EnsemblPlants EnsemblProtists GeneID GenomeReviews KEGG NMPDR TIGR UCSC VectorBase 酶与代谢通路 BioCyc BRENDA Pathway_Interaction_DBReactome 生理/病理 BindingDB DrugBank NextBio PMAP-CutDB DNA/RNA 序列数据库 EMBL IPI PIR RefSeq UniGene 3维结构 DisProt HSSP PDB PDBsum ProteinModelPortal SMR 翻译后修饰 GlycoSuiteDB PhosphoSite PhosSite 蛋白组数据库 PeptideAtlas PRIDE ProMEX 蛋白互作数据库 DIP IntAct MINT STRING 分子演化数据库 eggNOG GeneTreeHOGENOM HOVERGEN InParanoid OMAOrthoDBPhylomeDB ProtClustDB 遗传多样性 dbSNP 基因表达数据库 ArrayExpress Bgee CleanEx Genevestigator GermOnline 本体(Ontology) GO （改自/cours/Turin/UniProtKB_Turin.ppt)查询序列与被搜索数据库基本情况功能域信息详细匹配信息(Hits)HBA_HUMANHBB_HUMANNeedleman-WunschSmith-WatermanBLASTyx XY确定“种子”(seeding)查询序列M V L S P A D K T N V K A A WD K T 数据库oooooo o查询序列数据库候选序列o o数据库候选序列查询序列 连续片段(hit cluster)数据库候选序列 查询序列()()()()()()⎪⎪⎩⎪⎪⎨⎧+-+-+--==01,,1,1,1max ,00,0dj i F dj i F y x s j i F j i F F j i (改编自: Bedell et al . 2003)延伸长度分数⎪⎪⎪⎭⎫ ⎝⎛=∏i i N n L L K !!log 1窗口长度字符集数目(核酸：4，氨基酸：20)第i 个字符出现的频率 基于序列信息量，检测重复性的低复杂度区域CACACACACACACACAKLKLKLKLKLKL36.020log 61!3!*3!6log 61!0!*0!*3!*3!6log 61!!*!*!*!6log 614444==⎪⎭⎫ ⎝⎛=⎪⎭⎫ ⎝⎛=⎪⎪⎭⎫ ⎝⎛=T G C A n n n n K 以常见微卫星序列 “CACACACACACACACA”为例 设窗口长度=6× × × × × × ×DKT 16 DRT 13 DET 12 DKS 12 DQT 12EKT 12DKA 11DKN 11DKV 11DNT 11DST 11 NKT 11 DAT 10 DDT 10 DHT 10 DKC 10DKD 10DKE 10DKI 10DKK 10DKL 10DKM 10DKP 10DKQ 10DKR 10DMT 10DPT 10DTT 10QKT 10SKT 10 D K T | | 6+2+5=13 D R T(引自https:///doc /35e4a50968fd14221c11cbaa)p1=120随机匹配概率=1.56×10−8×192206270对于长为L的序列=1206=1.56×10−8检索蛋白质数据库Swiss-Prot，其中共含192206270个氨基酸(AA)p L=120LE=p×N≈3在随机情况下，获得比当前比对分数相等或更高分数的可能比对条数。
