生物信息学课件英文原版课件 (56)

Tue Sep 18 Intro 1: Computing, statistics, Perl, MathematicaTue Sep 25 Intro 2: Biology, comparative genomics, models & evidence, applications Tue Oct 02 DNA 1: Polymorphisms, populations, statistics, pharmacogenomics, databasesTue Oct 09 DNA 2: Dynamic programming, Blast, multi-alignment, HiddenMarkovModelsTue Oct 16 RNA 1: Microarrays, library sequencing & quantitation concepts Tue Oct 23 RNA 2: Clustering by gene or condition, DNA/RNA motifs.Tue Oct 30 Protein 1: 3D structural genomics, homology, dynamics, function & drug designTue Nov 06 Protein 2: Mass spectrometry, modifications, quantitation of interactionsTue Nov 13 Network 1: Metabolic kinetic & flux balance optimization methodsTue Nov 20 Network 2: Molecular computing, self-assembly, genetic algorithms, neural-netsTue Nov 27 Network 3: Cellular, developmental, social, ecological & commercial modelsTue Dec 04 Project presentationsTue Dec 11 Project PresentationsTue Jan 08 Project PresentationsTue Jan 15 Project Presentations,Bio 101: Genomics & Computational Biology,DNA1: Last weeks take-home lessons,Types of mutantsMutation, drift, selection Binomial & exponential dx/dt = kxAssociation studies c2 statisticLinked & causative allelesAlleles, Haplotypes, genotypesComputing the first genome, the second . New technologiesRandom and systematic errors,DNA2: Todays story and goals,Motivation and connection to DNA1Comparing types of alignments & algorithms Dynamic programming Multi-sequence alignmentSpace-time-accuracy tradeoffsFinding genes - motif profilesHidden Markov Model for CpG Islands,DNA 2,figure,Applications of Dynamic Programming,To sequence analysisShotgun sequence assemblyMultiple alignmentsDispersed & tandem repeatsBird song alignmentsGene Expression time-warpingThrough HMMsRNA gene search & structure predictionDistant protein homologiesSpeech recognition,Alignments & Scores,Global (e.g. haplotype) ACCACACA :xx:x: ACACCATAScore= 5(+1) + 3(-1) = 2,Suffix (shotgun assembly) ACCACACA : ACACCATAScore= 3(+1) =3,Local (motif) ACCACACA :ACACCATAScore= 4(+1) = 4,Increasingly complex (accurate) searches,Exact (StringSearch) CGCGRegular expression (PrositeSearch) CGN0-9CG = CGAACG,Substitution matrix (BlastN) CGCG = CACG Profile matrix (PSI-blast) CGc(g/a) = CACG,Gaps (Gap-Blast) CGCG = CGAACGDynamic Programming (NW, SM) CGCG = CAGACG,Hidden Markov Models (HMMER),WU,Hardness of (multi-) sequence alignment,Align 2 sequences of length N allowing gaps. ACCAC-ACA ACCACACA :x:x:x: :xxxxxx: AC-ACCATA , A-CACCATA , etc. 2N gap positions, gap lengths of 0 to N each: A nave algorithm might scale by O(N2N).For N= 3x109 this is rather large. Now, what about k2 sequences? or rearrangements other than gaps?,Separate Training set and Testing setsNeed databases of non-redundant sets.Need evaluation criteria (programs)Sensistivity and Specificity (false negatives & positives)sensitivity (true_predicted/true) specificity (true_predicted/all_predicted)Where do training sets come from?More expensive experiments: crystallography, genetics, biochemistry,Testing search & classification algorithms,Pearson WR Protein Sci 1995 Jun;4(6):1145-60 Comparison of methods for searching protein sequence databases. Methods Enzymol 1996;266:227-58 Effective protein sequence comparison.Algorithm: FASTA, Blastp, BlitzSubstitution matrix:PAM120, PAM250, BLOSUM50, BLOSUM62Database: PIR, SWISS-PROT, GenPept,Comparisons of homology scores,Switch to protein searches when possible,M,Adjacent mRNA codons,F,3 uac 5. aug,3aag uuu .,A Multiple Alignment of Immunoglobulins,Scoring matrix based on large set of distantly related blocks: Blosum62,Scoring Functions and Alignments,Scoring function:(match) = +1; (mismatch) = -1; (indel) = -2;(other) = 0.Alignment score: sum of columns.Optimal alignment: maximum score., substitution matrix,Calculating Alignment Scores,DNA2: Todays story and goals,Motivation and connection to DNA1Comparing types of alignments & algorithms Dynamic programming Multi-sequence alignmentSpace-time-accuracy tradeoffsFinding genes - motif profilesHidden Markov Model for CpG Islands,What is dynamic programming?,A dynamic programming algorithm solves every subsubproblem just once and then saves its answer in a table, avoiding the work of recomputing the answer every time the subsubproblem is encountered.- Cormen et al. Introduction to Algorithms, The MIT Press.,Recursion of Optimal Global Alignments,Recursion of Optimal Local Alignments,Computing Row-by-Row,min = -1099,Traceback Optimal Global Alignment,Local and Global Alignments,Time and Space Complexity of Computing Alignments,Space & Time Considerations,Comparing two one-megabase genomes.Space:An entry: 4 bytes;Table: 4 * 106 * 106 = 4 Terabytes memory (one row at a time)Time:1000 MHz CPU: 1M entries/second;1012 entries: 1M seconds = 10 days.,Time & Space Improvement for w-band Global Alignments,Two sequences differ by at most w bps (w logP(N) - logP(M) Example, say a/b hydrolase fold is rare in the database, about 10 in 10,000,000. The threshold is 20 bits. If considering 0.05 as a significant level, then the threshold is 20+4.4 = 24.4 bits.,C rare due to lack of uracil glycosylase (cytidine deamination)TT rare due to lack of UV repair enzymes. CG rare due to 5methylCG to TG transitions (cytidine deamination)AGG rare due to low abundance of the corresponding Arg-tRNA.CTAG rare in bacteria due to error-prone repair of CTAGG to C*CAGG.AAAA excess due to polyA pseudogenes and/or polymerase slippage.AmAcid Codon Number /1000 Fraction Arg AGG 3363.00 1.93 0.03Arg AGA 5345.00 3.07 0.06Arg CGG 10558.00 6.06 0.11Arg CGA 6853.00 3.94 0.07Arg CGT 34601.00 19.87 0.36Arg CGC 36362.00 20.88 0.37ftp:/sanger.otago.ac.nz/pub/Transterm/Data/codons/bct/Esccol.cod,Plausible sources of mono, di, tri, & tetra- nucleotide biases,C+,A+,G+,T+,P(G+|C+) ,P(A+|A+),CpG Island + in a ocean of - First order Markov Model,MM=16, HMM= 64