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

Outline for Todays Discussion,basic facts about DNA, RNA, and proteinsexamples of computational problemsexamples of algorithmic techniques,Main Bio-molecules,DNA: encodes genetic information.RNA: copies and transports such information to produce proteins.Protein: performs various biological functions.,Basic Facts about DNA,4 nitrogenous bases: Adenine, Cytosine, Guanine, Thyminenucleotide = base + phosphate + sugar strand = a polymer of nucleotidesdouble strands: two complementary strandsbinding rule: A-T and C-G3D structure: double helixchromosome = a complete DNA molecule in a cellgenome = the whole set of chromosomes in a cell,DNA Structure,Genome at 4 Levels of Details,Example of Chromosome Sizes,Basic Facts about RNA,4 nitrogenous bases: Adenine, Cytosine, Guanine, Uracilnucleotide = base + phosphate + sugar strand = a polymer of nucleotidessingle strandbinding rule: A-U, C-G, and others.3D structure: much more complex than double helix,Basic Facts about Protein,20 amino acid residuesstrand = a polymer of amino acidssingle strandbinding rule: complicated.3D structure: much more complex than RNAs 3D structure function of a protein,Importance of Protein Folding,The 3D structure significantly determines the function.,Key Facts about Genes,gene = segment of a chromosomegene proteincodon = 3 consecutive DNA basescodon protein charactergene = partitioned into introns and exonsexon = codonsintron = “meaningless” regionGenes may be nested,DNA RNA Protein,Functional Assignment using Gene Ontology,13,601 Genes,Drosophila,Gene Number in the Human Genome,The Gene Counting Problem,The number probably will be never known exactly.,Current estimates: 30,000-40,000,Other estimates: 120,000,Gene discovery:,sequence analysis motif recognition matches to mRNA computational predictions mouse data matches experimental validation,Some Main Areas of Bioinformatics,A key goal of bioinformatics: To study biological systems based on global knowledge of genomes, transcriptomes, and proteomes.Genome: entire sets of materials in the chromosomes.Transcriptome: entire sets of gene transcripts.Proteome: entire sets of proteins.,Perspectives,A key goal of bioinformatics: To study biological systems based on global knowledge of genomes, transcriptomes, and proteomes.Genome: entire sets of materials in the chromosomes.Transcriptome: entire sets of gene transcripts.Proteome: entire sets of proteins.,Proteomics,Proteome: all proteins encoded within a genomehalf millions distinct proteins (temporal, spatial, modifications)30,000 human genesmRNA and protein expressions may not correlateProteomics: study of protein expression by biological systemsrelative abundance and stability; post-translational modificationsfluctuations as a response to environment and altered cellular needscorrelations between protein expression and disease stateprotein-protein interactions, protein complexesTechnologies:2D gel electrophoresis mass spectrometryyeast two-hybrid systemprotein chips,Protein Identification: HPLC-MS-MS,Mass/ChargeTandem Mass Spectrum,Mass/Charge,Proteins,Peptides,One Peptide,B-ions / Y-ions,Protein Identification: HPLC-MS-MS,Mass/ChargeTandem Mass Spectrum,Mass/Charge,Proteins,Peptides,One Peptide,B-ions / Y-ions,Peptide Fragmentation and Ionization,B-ion,Y-ion,Complementary: Mass(B-ion)+Mass(Y-ion) = Mass(peptide)+4H+O,Tandem Mass Spectrum,Mass / Charge,Abundance (100%),200,50,88.033,100,400,175.113,274.112,361.121,430.213,448.225,Raw Tandem Mass Spectrum,Protein Database Search,Find the peptide sequences in a protein database that optimally fit the spectrum.It does not work if the target peptide sequence is not in the database.It does not work if there is an unknown modification at some amino acid.It is very slow because it must search the entire database.E.g., SEQUEST, Yates, Univ. of Washington.,De Novo Peptide Sequencing Problem,Input: (1) the mass W of an unknown target peptide, and (2) a set S of the masses of some or all b-ions and y-ions of the peptide.Output: a peptide P such that (1) mass(P)=W and (2) S is a subset of all the ion masses of P.,Mass / Charge,Abundance (100%),50,100,274.112,361.121,Peptide Mass 429.212 Daltons,P = SWR,Mass(P) = 429.212,Ions(P) = 88.033, 175.113, 274.112, 361.121, 430.213, 448.225,Amino Acid Mass Table,Importance of Protein Folding,The 3D structure significantly determines the function.,Two Complementary Problems for Protein Folding,Protein Folding Prediction - Given a protein sequence, determine the 3D folding of the sequence. Protein Sequence Design - Given a 3D structure, determine the fittest protein sequence for the structure, i.e., one that has the smallest energy among all possible sequences when folded into the structure.,Complexity for Protein Folding Problems,Protein Folding Prediction - Given a protein sequence, determine the 3D folding of the sequence. NP-hard under various models.Protein Sequence Design - Given a 3D structure, determine the fittest protein sequence for the structure, i.e., one that has the smallest energy among all possible sequences when folded into the structure. Solvable in polynomial time under the Grand Canonical model.,Protein Identification: HPLC-MS-MS,Mass/ChargeTandem Mass Spectrum,Mass/Charge,Proteins,Peptides,One Peptide,B-ions / Y-ions,Key Steps of Sequencing DNA,Goal = determine the character sequence of a DNA molecule.Duplicate many copies.Cut the copies into fragments.Determine the character sequence of small fragments (by means of recursion or lab instruments).Compare, align, and order the fragments into the original sequence.,Polymerase Chain Reaction,Cutting DNAs,BLAST (Basic Local Alignment Search Tool),A suite of sequence comparison algorithms optimized for speed used to search sequence databases for optimal local alignments to a protein or nucleotide query,Mapping and Walking Mapping and Clone by Clone Shotgun Whole Genome Shotgun with Mate Pairs,Lab-Intense (SLOW),Compute-Intense (FAST),Comparison of Sequencing Strategies,DNA target sample,SHEAR & SIZE,e.g., 10Kbp 8% std.dev.,End Reads / Mate Pairs,CLONE & END SEQUENCE,590bp,10,000bp,Mate-Pair Shotgun DNA Sequencing,Mapping and Shotgun,Clone by Clone Shotgun sequencing,Whole Genome Sequencing Approaches,Key Steps of Sequencing DNA,Goal = determine the character sequence of a DNA molecule.Duplicate many copies.Cut the copies into fragments.Determine the character sequence of small fragments (by means of recursion or instruments).Compare, align, and order the fragments into the original sequence.,Sequencing reactions produce short reads (550bp).,Human Genome3 billion bases,Sequence read550 bases,The human genome is repeat-rich.,Many short reads look identical to each other.,GCATTA.GACCGT,CGGATAGACATAAC,CGGATAGACATAAC,CGGATAGACATAAC,CAGCAGCAGCAGCA,CAGCAGCAGCAGCA,CAGCAGCAGCAGCA,Obstacles to Genome Sequencing,Order & Orientation is Essential to Finding Genes,Exon 1,Exon 2,Exon 3,Exon 4,Exons are shuffled and unoriented, significantly impacting the ability of gene finding programs to make a correct prediction.Users consistently report finding genes that they cant find elsewhere.,But if contigs are not correctly put together:,1,4,3 reversed,2,Celeras Sequencing / SNP Discovery Center,Celera Supercomputing Facility,Celeras system is one of the most powerful civilian super-computing facilities in the worldCurrently over 1.5 teraflop of computing power in a virtual compute farm of Compaq processors with 100 terabytes storageNext phase a 100 teraflop computer,Human Genome Sequence from 5 Humans (3 females-2 males) completed,Human sequencing started 9/8/99Over 39X coverage of the genome in paired plasmid readsFirst Assembly announced June 26 2.9 billion bpPublished in Science, February 16, 2001,Evolutionary Trees,definition: a tree with distinct labels at leavesleaf labels: species, organisms, DNAs, RNAs, proteins, features, etc.,ancestralspecies,bird,plum,peach,rice,wheat,present-day species,(Just a joke!),Evolutionary Trees,leaf labels: DNA sequences,bird,plum,peach,rice,wheat,AAGT,CCAG,CCAT,CGGG,CGGC,(Just a joke!),Problem Formulation,bird,plum,peach,rice,wheat,AAGT,CCAG,CCAT,CGGG,CGGC,Input: DNA sequences of present-day speciesOutput: the true evolutionary treeQuestion: What is “true”?,Need a model!,(Just a joke!),A Fundamental Problem of Biology,Since the time of Charles Darwin, Problem: reconstruct the evolutionary history of all known species.Importance: intellectually fascinating practical benefits medicine, food Charles Robert Darwin - 1809-1882 Origin of Species - 1859,Protein Evolution,Tree of Life & Evolution of Protein Families (Dayhoff, 1978)Othologus Gene Family: Organismal and Sequence Trees Match Well,Evolutionary Tree,Relationships Between IMP Dehydrogenase Families,Evolutionary Tree,Relationships Between G-Protein-Coupled Receptor Families (One of the Largest and Most Diversified),Main Difficulties,Availability of data Hundreds of millions of species - unlikely to be all available any time soon or ever. But DNA sequences of more and more species are becoming available. Extracting information from data,Data Mining Flowchart,true tree(unknown),collect & processindividual sequences,compare & alignmultiple sequences,tree reconstructionalgorithms,tree verification(compare & refine),evolution models,generatesequences,further process,parameters,distance or characters,trees,information,refine,infer,parameters,Other Applications of Evolutionary Trees,A tree that conceptually models the evolutionary relationship of species or organismsApplications outside biology: linguistics - evolution of wordsstatistical classificationstracking computer viruses,Primary Information Captured in Evolutionary Trees,most recent common ancestor,X1,X2,X3,X4,X5,AAGT,CCAG,CCAT,CGGG,CGGC,yes,no,omit to simplify computation/structure,Why Need to Compare Trees?,For the same given set of species or organisms,different (1) data, (2) evolution models, (3) biological intuitions, or (4) tree construction algorithms may yield different trees.Tree comparison is a data mining tool for gaining information from multiple trees.,What Information to Gain from Comparison?,dissimilarity measures I.e., determine how different the given trees mon structures in multiple trees I.e., extract common evolutionary history from the trees.,How to Use InformationGained from Comparison?,dissimilarity measures Reexamine (1) data, (2) evolution models, (3) biological intuitions, or (4) tree construction mon structures in multiple trees Common information is more reliable than non-common information.,Examples of Tree Comparisons,Key points:There are lots of tree comparisons!How does one design or use tree comparisons?new tree comparison = new type of information data mining flow chart: a hunch for a certain kind of information a math definition for tree comparison algorithms find new information,Examples #1 of Tree Comparisons,Emphasis: dissimilarity measures1. Good versus Bad Edges (Robinson-Foulds distance)2. Subtree Transfer Distance-Emphasis: common information3. Maximum Common Refinement Subtree4. Maximum Agreement Subtree (more technical details),Good Edges,X1,X2,X4,X3,X5,X3,X2,X4,X1,X5,good,Tree #2,Tree #1,good,Definition: good edge = same clustering,Bad Edges,X1,X2,X4,X3,X5,X3,X2,X4,X1,X5,bad,Tree #2,Tree #1,bad,Definition: bad edge = different clusterings,External Edges are Always Good Edges,X1,X2,X4,X3,X5,X3,X2,X4,X1,X5,good,Tree #2,Tree #1,good,Definition: good edge = same clustering,Good versus Bad Edges,X1,X2,X4,X3,X5,X3,X2,X4,X1,X5,bad,good,Tree #2,Tree #1,good,bad,Robinson-Foulds distance = (1) # of bad edges (2) % of the internal edges being bad,Robinson-Foulds Distance,Measure:Robinson-Foulds distance = (1) # of bad edges (2) % of the internal edges being badIntuitions:This measure counts how often two trees have different clusterings.Computational Complexity:n = size of input treesNave Algorithm: O(n2) time.Best Algorithm: optimal O(n) time.(Day, 1985),Examples #4 of Tree Comparisons,Emphasis: dissimilarity measures1. Good versus Bad Edges (Robinson-Foulds distance)2. Subtree Transfer Distance-Emphasis: common information3. Maximum Common Refinement Subtree4. Maximum Agreement Subtree (more technical details),Basics of Maximum Agreement Subtrees,Assumption: rooted binary evolutionary trees.Concepts:Information contents of a treeEvolutionary subtreesAgreement subtreesMaximum agreement subtrees,Information Content of Evolutionary Trees,Number