バイオインフォマティクス - Sakakibara Lab

1 CGTCCGT----------TCCGTAT-----------GTATC ------------ATCCAT------------CATCG===== ==========CGTCCGTATCCATCG1423 CGTCCGTTCCGTATATCCATGTATC425 CATCG3213252111 LCS sis PDGF sis: simian sarcoma virus Doolittle Doolittle BLAST DNA CDK4 GENBANK GENBANK GENBANK

2 2 DNA GAGGTTATCAAAAGCTACTAGTCCAGAGGATAACAAGGCT ACTATCACA GAGGTTATCAA-AA-GCTACTAGTC-CAGAGG--AT-AAC AAGGCTACTA-TCACA** ** ** ** ** ** ** MVHLTPEEKSAVTALWGKVNVDEVGGEALGRLLVVYPWTQ RFFESFGDLSTPDAVMGNPKVKAHGKKVLGMVHLTPEEKS AVTALWGKVNVDEVGGEALGRLLVVYPWTQRFFESFGDLS TPDAVMGNPKVKAHGKKVLG** AFSDGLAHLDNLKGTFATLSELHCDKLHVDPENF-RLLGN VLVCVLAHHFGKEFTPPVQAAYQKVVAGVAAFSDGLAHLD NLKGTFATLSELHCDKLHVDPENFK-LLGNVLVCVLAHHF GKEFTPPVQAAYQKVVAGVA**

3 **NALAHKYHNALAHKYH**MV-HL--TPEEK-SAV-TAL W-GKVN--VDEVGGEALGRLLVVYPWTQRFF-ESFGDLS- TP-DAVMGNP-VQ-LSG--EEKA-AVL-ALWD-KVNEE-- EVGGEALGRLLVVYPWTQRFFD-SFGDLSN-PG-AVMGNP * * ** ** ** ** ** ** * **KVKAHGKKVL---G-AFSDG--LAHLDNLKGTF-ATLS ELHCDKLHVDPENFRLLGNVL-VCVLA-HHFGKVKAHGKK VLHSFGE----GVH--HLDNLKGTFAA-LSELHCDKLHVD PENFRLLGNVLVV-VLAR-HFG** * * ** * ** * ** **K-EFTP--PVQA-AYQKVVAGVANALAHKYHKD-FTPE L--QAS-YQKVVAGVANALAHKYH* ** ** ** AGCGTAG GTCAGA AG-C-GTAG-GTCAG-A-* * * * 0+1+0+1+0+1+0+1+0 = 4 AGCGTAG-GTC--AGA* ** (-1)+(-1)+1+0+0+1+1+0 = 1 AGCGTAGGTCAGA-* * (-1)+(-1)+1+(-1)+(-1)+1+0 = -2 n nnnnnnn 22)!

4 (!()!2(2 GAGGTTATCAAAAGGAGGATAACAAGGCG G T T C A GG A A T A C Ak knCknCnnnkknknCCC21 dynamic programming, DP Optimal substructure: Overlapping subproblems: Needleman-Wunsch Optimal substructure of LCS: LCS ,212121 YXzzzZyyyYxxxXknm LCS (1)111 nmknmknmYXZyxzyxLCS (2)1 YXZxzyxmmknm LCS (3)1 nnknmYXZyzyx 1 1 0123456789100W1WW2345678910W L ),(jiFixxx 21jyyy 21djjFdiiFF ) ,0( ,)0 ,( ,0)0 ,0( d djiFdjiFyxsjiFjiFji)1,( ),1( ),())

5 1,1( max) ,(),(nmFXY),(nmF)0 ,0(F),(nmFi0123456jGTCAGA01A2G3C4G5T6A7G 0000000000111111122112222112230000000312 2233122334122344 i0123456jGTCAGA000000001A00001112G011112 23C01122224G01122335T01222336A01223347G0 122344 GGGGCCAA-GTCAG-A-AG-C-GTAG Smith-Waterman 0 0) ,0( ,0)0 ,( ,0)0 ,0( jFiFF djiFdjiFyxsjiFjiFji)1,( ),1( ),()1,1( 0 max) ,(XY),(jiF DNA)

6 PAM Dayhoff BLOSUM PAM Dayhoff 100 1 PAM 1 PAM i j BLOSUM BLOSUM50, BLOSUM62, BLOSUM80, BLOSUM62 BLOSUM50 BLOSUM62 BLAST CLUSTALW BLOSUM BLOSUM50 baabqqpbas log) ,( a aq a b a b abpab a b BLOSUM L L a b pab a qa s a,b)=log(pab/qaqb)

7 BLOSUM 75 75% block 1block 2 BABABABCAACCCBBCBBABCAAC BLOSUM75 qa ABC172/11 17234 175 17281172/13 17235 block 1block 2 BABABABCAACCCBBCBBABCAACBLOSUM75 A to AA to BA to CB to BB to CC to C132/31331311322/1 132/513333342 132 block 1block 2 BABABABCAACCCBBCBBABCAAC 172/11172/11172/111752175175172/11172/13 2175172/132172/13172/13 ABBA pabqaqbBLOSUM75 A to AA to BA to CB to BB to CC to C132/3133131132/5133132 2894/12128955289252892/143289652894/169 log22 010100 i012345678j01234567

8