InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息课件

《InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息课件》由会员分享，可在线阅读，更多相关《InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息课件（76页珍藏版）》请在装配图网上搜索。

1、InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息1Microarray Data AnalysisClass discovery and Class prediction:Clustering and DiscriminationInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息2Gene expression profiles Many genes show definite changes of expression between conditions T

2、hese patterns are called gene profilesInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息3Motivation(1):The problem of finding patterns It is common to have hybridizations where conditions reflect temporal or spatial aspects.Yeast cycle data Tumor data evolution after chemotherapy CNS data in

3、 different part of brain Interesting genes may be those showing patterns associated with changes.Our problem seems to be distinguishing interesting or real patterns from meaningless variation,at the level of the geneInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息4Finding patterns:Two appr

4、oaches If patterns already exist Pro(Distance analysis)Find the genes whose expression fits specific,predefined patterns.Find the genes whose expression follows the pattern of predefined gene or set of genes.If we wish to discover new patterns Cluster analysis(class discovery)Carry out some kind of

5、exploratory analysis to see what expression patterns emerge;InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息5Motivation(2):Tumor classification A reliable and precise classification of tumours is essential for successful diagnosis and treatment of cancer.Current methods for classifying hum

6、an malignancies rely on a variety of morphological,clinical,and molecular variables.In spite of recent progress,there are still uncertainties in diagnosis.Also,it is likely that the existing classes are heterogeneous.DNA microarrays may be used to characterize the molecular variations among tumours

7、by monitoring gene expression on a genomic scale.This may lead to a more reliable classification of tumours.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息6Tumor classification,contThere are three main types of statistical problems associated with tumor classification:The identification o

8、f new/unknown tumor classes using gene expression profiles-cluster analysis;The classification of malignancies into known classes-discriminant analysis;1.The identification of“marker”genes that characterize the different tumor classes-variable selection.InformationEncodinginBiologicalMoleculesDNAand

9、生物分子DNA编码的信息7Cluster and Discriminant analysis These techniques group,or equivalently classify,observational units on the basis of measurements.They differ according to their aims,which in turn depend on the availability of a pre-existing basis for the grouping.In cluster analysis(unsupervised learn

10、ing,class discovery),there are no predefined groups or labels for the observations,Discriminant analysis(supervised learning,class prediction)is based on the existence of groups(labels)InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息8Clustering microarray data Cluster can be applied to gen

11、es(rows),mRNA samples(cols),or both at once.Cluster samples to identify new cell or tumour subtypes.Cluster rows(genes)to identify groups of co-regulated genes.We can also cluster genes to reduce redundancy e.g.for variable selection in predictive models.InformationEncodinginBiologicalMoleculesDNAan

12、d生物分子DNA编码的信息9Advantages of clustering Clustering leads to readily interpretable figures.Clustering strengthens the signal when averages are taken within clusters of genes(Eisen).Clustering can be helpful for identifying patterns in time or space.Clustering is useful,perhaps essential,when seeking n

13、ew subclasses of cell samples(tumors,etc).InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息10Applications of clustering(1)Alizadeh et al(2000)Distinct types of diffuse large B-cell lymphoma identified by gene expression profiling.Three subtypes of lymphoma(FL,CLL and DLBCL)have different ge

14、netic signatures.(81 cases total)DLBCL group can be partitioned into two subgroups with significantly different survival.(39 DLBCL cases)InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息11Clusters on both genes and arraysTaken from Nature February,2000Paper by Allizadeh.A et alDistinct type

15、s of diffuse large B-cell lymphoma identified by Gene expression profiling,InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息12Discovering tumor subclasses DLBCL is clinically heterogeneous Specimens were clustered based on their expression profiles of GC B-cell associated genes.Two subgroup

16、s were discovered:GC B-like DLBCL Activated B-like DLBCLInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息13Applications of clustering(2)A nave but nevertheless important application is assessment of experimental design If one has an experiment with different experimental conditions,and in e

17、ach of them there are biological and technical replicates We would expect that the more homogeneous groups tend to cluster together Tech.replicates Biol.Replicates Different groups Failure to cluster so suggests bias due to experimental conditions more than to existing differences.InformationEncodin

18、ginBiologicalMoleculesDNAand生物分子DNA编码的信息14Basic principles of clusteringAim:to group observations that are“similar”based on predefined criteria.Issues:Which genes/arrays to use?Which similarity or dissimilarity measure?Which clustering algorithm?It is advisable to reduce the number of genes from the

19、 full set to some more manageable number,before clustering.The basis for this reduction is usually quite context specific,see later example.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息15Two main classes of measures of dissimilarity Correlation DistanceManhattanEuclideanMahalanobis dist

20、anceMany more.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息16Two basic types of methodsPartitioningHierarchicalInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息17Partitioning methods Partition the data into a pre-specified number k of mutually exclusive and exhaustive groups.It

21、eratively reallocate the observations to clusters until some criterion is met,e.g.minimize within cluster sums of squares.Examples:k-means,self-organizing maps(SOM),PAM,etc.;Fuzzy:needs stochastic model,e.g.Gaussian mixtures.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息18Hierarchical me

22、thods Hierarchical clustering methods produce a tree or dendrogram.They avoid specifying how many clusters are appropriate by providing a partition for each k obtained from cutting the tree at some level.The tree can be built in two distinct ways bottom-up:agglomerative clustering;top-down:divisive

23、clustering.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息19Agglomerative methods Start with n clusters.At each step,merge the two closest clusters using a measure of between-cluster dissimilarity,which reflects the shape of the clusters.Between-cluster dissimilarity measures Mean-link:av

24、erage of pairwise dissimilarities Single-link:minimum of pairwise dissimilarities.Complete-link:maximum&of pairwise dissimilarities.Distance between centroidsInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息20Distance between centroidsSingle-linkComplete-linkMean-linkInformationEncodinginBi

25、ologicalMoleculesDNAand生物分子DNA编码的信息21Divisive methods Start with only one cluster.At each step,split clusters into two parts.Split to give greatest distance between two new clusters Advantages.Obtain the main structure of the data,i.e.focus on upper levels of dendogram.Disadvantages.Computational di

26、fficulties when considering all possible divisions into two groups.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息2215 2 34152341,2,53,41,51,2,3,4,5AgglomerativeIllustration of points In two dimensional space15342InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息2315 2 34152341,2,

27、53,41,51,2,3,4,5AgglomerativeTree re-ordering?153421 5234InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息24Partitioning or Hierarchical?Partitioning:Advantages Optimal for certain criteria.Genes automatically assigned to clusters Disadvantages Need initial k;Often require long computation

28、times.All genes are forced into a cluster.Hierarchical Advantages Faster computation.Visual.Disadvantages Unrelated genes are eventually joined Rigid,cannot correct later for erroneous decisions made earlier.Hard to define clusters.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息25Hybrid M

29、ethods Mix elements of Partitioning and Hierarchical methods Bagging Dudoit&Fridlyand(2002)HOPACH van der Laan&Pollard(2001)InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息26Three generic clustering problemsThree important tasks(which are generic)are:1.Estimating the number of clusters;2.A

30、ssigning each observation to a cluster;3.Assessing the strength/confidence of cluster assignments for individual observations.Not equally important in every problem.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息27Estimating number of clusters using silhouetteDefine silhouette width of th

31、e observation as:S=(b-a)/max(a,b)Where a is the average dissimilarity to all the points in the cluster and b is the minimum distance to any of the objects in the other clusters.Intuitively,objects with large S are well-clustered while the ones with small S tend to lie between clusters.How many clust

32、ers:Perform clustering for a sequence of the number of clusters k and choose the number of components corresponding to the largest average silhouette.Issue of the number of clusters in the data is most relevant for novel class discovery,i.e.for clustering samplesInformationEncodinginBiologicalMolecu

33、lesDNAand生物分子DNA编码的信息28Estimating number of clusters using the bootstrapThere are other resampling(e.g.Dudoit and Fridlyand,2002)and non-resampling based rules for estimating the number of clusters(for review see Milligan and Cooper(1978)and Dudoit and Fridlyand(2002).The bottom line is that none wo

34、rk very well in complicated situation and,to a large extent,clustering lies outside a usual statistical framework.It is always reassuring when you are able to characterize a newly discovered clusters using information that was not used for clustering.InformationEncodinginBiologicalMoleculesDNAand生物分

35、子DNA编码的信息29LimitationsCluster analyses:Usually outside the normal framework of statistical inference;less appropriate when only a few genes are likely to change.Needs lots of experiments Always possible to cluster even if there is nothing going on.Useful for learning about the data,but does not prov

36、ide biological truth.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息30Discriminationor Class predictionor Supervised LearningInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息31Motivation:A study of gene expression on breast tumours(NHGRI,J.Trent)How similar are the gene expressio

37、n profiles of BRCA1 and BRCA2(+)and sporadic breast cancer patient biopsies?Can we identify a set of genes that distinguish the different tumor types?Tumors studied:7 BRCA1+8 BRCA2+7 SporadiccDNA MicroarraysParallel Gene Expression Analysis 6526 genes/tumorInformationEncodinginBiologicalMoleculesDNA

38、and生物分子DNA编码的信息32 Discrimination A predictor or classifier for K tumor classes partitions the space X of gene expression profiles into K disjoint subsets,A1,.,AK,such that for a sample with expression profile x=(x1,.,xp)Ak the predicted class is k.Predictors are built from past experience,i.e.,from

39、observations which are known to belong to certain classes.Such observations comprise the learning setL=(x1,y1),.,(xn,yn).A classifier built from a learning set L is denoted by C(.,L):X 1,2,.,K,with the predicted class for observation x being C(x,L).InformationEncodinginBiologicalMoleculesDNAand生物分子D

40、NA编码的信息33Discrimination and AllocationLearning SetData with known classesClassificationTechniqueClassificationruleData with unknown classesClassAssignmentDiscriminationPredictionInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息34?Bad prognosisrecurrence 5yrsReferenceL vant Veer et al(2002)G

41、ene expression profiling predicts clinical outcome of breast cancer.Nature,Jan.ObjectsArrayFeature vectorsGene expressionPredefine classesClinicaloutcomenew arrayLearning setClassificationruleGood PrognosisMatesis 5InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息35B-ALLT-ALLAMLReferenceGol

42、ub et al(1999)Molecular classification of cancer:class discovery and class prediction by gene expression monitoring.Science 286(5439):531-537.ObjectsArrayFeature vectorsGene expressionPredefine classesTumor type?new arrayLearning setClassificationRuleT-ALLInformationEncodinginBiologicalMoleculesDNAa

43、nd生物分子DNA编码的信息36Components of class prediction Choose a method of class prediction LDA,KNN,CART,.Select genes on which the prediction will be base:Feature selection Which genes will be included in the model?Validate the model Use data that have not been used to fit the predictorInformationEncodingin

44、BiologicalMoleculesDNAand生物分子DNA编码的信息37Prediction methodsInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息38Choose prediction model Prediction methods Fisher linear discriminant analysis(FLDA)and its variants(DLDA,Golubs gene voting,Compound covariate predictor)Nearest Neighbor Classificati

45、on Trees Support vector machines(SVMs)Neural networks And many more InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息39Fisher linear discriminant analysis First applied in 1935 by M.Barnard at the suggestion of R.A.Fisher(1936),Fisher linear discriminant analysis(FLDA)consists of i.finding

46、linear combinations x a of the gene expression profiles x=(x1,.,xp)with large ratios of between-groups to within-groups sums of squares-discriminant variables;ii.predicting the class of an observation x by the class whose mean vector is closest to x in terms of the discriminant variables.Information

47、EncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息40FLDAInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息41Classification rule Maximum likelihood discriminant rule A maximum likelihood estimator(MLE)chooses the parameter value that makes the chance of the observations the highest.For known cla

48、ss conditional densities pk(X),the maximum likelihood(ML)discriminant rule predicts the class of an observation X by C(X)=argmaxk pk(X)InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息42Gaussian ML discriminant rules For multivariate Gaussian(normal)class densities X|Y=k N(k,k),the ML class

49、ifier isC(X)=argmink(X-k)k-1(X-k)+log|k|In general,this is a quadratic rule(Quadratic discriminant analysis,or QDA)In practice,population mean vectors k and covariance matrices k are estimated by corresponding sample quantitiesInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息43ML discrimina

50、nt rules-special casesDLDA Diagonal linear discriminant analysisclass densities have the same diagonal covariance matrix =diag(s12,sp2)DQDA Diagonal quadratic discriminant analysis)class densities have different diagonal covariance matrix k=diag(s1k2,spk2)Note.Weighted gene voting of Golub et al.(19

51、99)is a minor variant of DLDA for two classes(different variance calculation).InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息44Classification with SVMsGeneralization of the ideas of separating hyperplanes in the original space.Linear boundaries between classes in higher-dimensional space

52、lead tothe non-linear boundaries in the original space.Adapted from internetInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息45Nearest neighbor classification Based on a measure of distance between observations(e.g.Euclidean distance or one minus correlation).k-nearest neighbor rule(Fix and

53、 Hodges(1951)classifies an observation x as follows:find the k observations in the learning set closest to x predict the class of x by majority vote,i.e.,choose the class that is most common among those k observations.The number of neighbors k can be chosen by cross-validation(more on this later).In

54、formationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息46Nearest neighbor ruleInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息47Classification tree Binary tree structured classifiers are constructed by repeated splits of subsets(nodes)of the measurement space X into two descendant subsets

55、,starting with X itself.Each terminal subset is assigned a class label and the resulting partition of X corresponds to the classifier.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息48Classification treesMi1 -0.5Node 2Class 1:6Class 2:9Node 4Class 1:0Class 2:4Prediction:2Node 3Class 1:4Cla

56、ss 2:1Prediction:1yesyesnonoGene 1Gene 2Mi2 2.1Node 5Class 1:6Class 2:5Node 7Class 1:5Class 2:0Prediction:1Node 6Class 1:1Class 2:5Prediction:2Gene 3InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息49Three aspects of tree construction Split selection rule:Example,at each node,choose split m

57、aximizing decrease in impurity(e.g.Gini index,entropy,misclassification error).Split-stopping:The decision to declare a node as terminal or to continue splitting.Example,grow large tree,prune to obtain a sequence of subtrees,then use cross-validation to identify the subtree with lowest misclassifica

58、tion rate.The assignment:of each terminal node to a class Example,for each terminal node,choose the class minimizing the resubstitution estimate of misclassification probability,given that a case falls into this node.Supplementary slideInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息50Othe

59、r classifiers include Support vector machines Neural networks Bayesian regression methods Projection pursuit.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息51Aggregating predictors Breiman(1996,1998)found that gains in accuracy could be obtained by aggregating predictors built from pertur

60、bed versions of the learning set.In classification,the multiple versions of the predictor are aggregated by voting.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息52Aggregating predictors1.Bagging.Bootstrap samples of the same size as the original learning set.-non-parametric bootstrap,Bre

61、iman(1996);-convex pseudo-data,Breiman(1998).2.Boosting.Freund and Schapire(1997),Breiman(1998).The data are resampled adaptively so that the weights in the resampling are increased for those cases most often misclassified.The aggregation of predictors is done by weighted voting.InformationEncodingi

62、nBiologicalMoleculesDNAand生物分子DNA编码的信息53Prediction votesFor aggregated classifiers,prediction votes assessing the strength of a prediction may be defined for each observation.The prediction vote(PV)for an observation x is defined to be PV(x)=maxk b wb I(C(x,Lb)=k)/bwb.When the perturbed learning set

63、s are given equal weights,i.e.,wb=1,the prediction vote is simply the proportion of votes for the “winning class,regardless of whether it is correct or not.Prediction votes belong to 0,1.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息54Another component in classification rules:aggregating

64、 classifiersTraining SetX1,X2,X100Classifier 1Resample 1Classifier 2Resample 2Classifier 499Resample 499 Classifier 500Resample 500Examples:BaggingBoostingRandom ForestAggregateclassifierInformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息55Aggregating classifiers:BaggingTraining Set(arrays)X1

65、,X2,X100Tree 1Resample 1X*1,X*2,X*100Lets the treevoteTree 2Resample 2X*1,X*2,X*100Tree 499Resample 499X*1,X*2,X*100Tree 500Resample 500X*1,X*2,X*100TestsampleClass 1Class 2Class 1Class 190%Class 110%Class 2InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息56Feature selectionInformationEncod

66、inginBiologicalMoleculesDNAand生物分子DNA编码的信息57Feature selection A classification rule must be based on a set of variables which contribute useful information for distinguishing the classes.This set will usually be small because most variables are likely to be uninformative.Some classifiers(like CART)perform automatic feature selection whereas others,like LDA or KNN,do not.InformationEncodinginBiologicalMoleculesDNAand生物分子DNA编码的信息58Approaches to feature selection Filter methods perform explicit fea