聚類(lèi)和樹(shù)-微陣列與分子系統(tǒng)發(fā)育分析

聚類(lèi)與樹(shù)Clustering2024/9/91主要內(nèi)容Microarrays（微陣列）HierarchicalClustering（層次聚類(lèi)或系統(tǒng)聚類(lèi)）K-MeansClustering（K-均值聚類(lèi)）2024/9/92ApplicationsofClusteringViewingandanalyzingvastamountsofbiologicaldataasawholesetcanbeperplexingItiseasiertointerpretthedataiftheyarepartitionedintoclusterscombiningsimilardatapoints.2024/9/93InferringGeneFunctionalityResearcherswanttoknowthefunctionsofnewlysequencedgenesSimplycomparingthenewgenesequencestoknownDNAsequencesoftendoesnotgiveawaythefunctionofgeneFor40%ofsequencedgenes,functionalitycannotbeascertainedbyonlycomparingtosequencesofotherknowngenesMicroarraysallowbiologiststoinfergenefunctionevenwhensequencesimilarityaloneisinsufficienttoinferfunction.2024/9/94MicroarraysandExpressionAnalysisMicroarraysmeasuretheactivity(expressionlevel)ofthegenesundervaryingconditions/timepointsExpressionlevelisestimatedbymeasuringtheamountofmRNAforthatparticulargeneAgeneisactiveifitisbeingtranscribedMoremRNAusuallyindicatesmoregeneactivity2024/9/95MicroarrayExperimentsProducecDNAfrommRNA(DNAismorestable)AttachphosphortocDNAtoseewhenaparticulargeneisexpressedDifferentcolorphosphorsareavailabletocomparemanysamplesatonceHybridizecDNAoverthemicroarrayScanthemicroarraywithaphosphor-illuminatinglaserIlluminationrevealstranscribedgenesScanmicroarraymultipletimesforthedifferentcolorphosphor’s2024/9/96MicroarrayExperiments(con’t)PhosphorscanbeaddedhereinsteadTheninsteadofstaining,laserilluminationcanbeused2024/9/97UsingMicroarraysEachboxrepresentsonegene’sexpressionovertime

TrackthesampleoveraperiodoftimetoseegeneexpressionovertimeTracktwodifferentsamplesunderthesameconditionstoseethedifferenceingeneexpressions2024/9/98UsingMicroarrays(cont’d)Green:expressedonlyfromcontrolRed:expressedonlyfromexperimentalcellYellow:equallyexpressedinbothsamplesBlack:NOTexpressedineithercontrolorexperimentalcells2024/9/99MicroarrayDataMicroarraydataareusuallytransformedintoanintensitymatrix(below)Theintensitymatrixallowsbiologiststomakecorrelationsbetweendiferentgenes(eveniftheyaredissimilar)andtounderstandhowgenesfunctionsmightberelatedTime:TimeXTimeYTimeZGene110810Gene21009Gene348.63Gene4783Gene5123Intensity(expressionlevel)ofgeneatmeasuredtime2024/9/910MicroarrayData-REVISION-showinthematrixwhichgenesaresimilarandwhicharenot.Microarraydataareusuallytransformedintoanintensitymatrix(below)Theintensitymatrixallowsbiologiststomakecorrelationsbetweendiferentgenes(eveniftheyaredissimilar)andtounderstandhowgenesfunctionsmightberelatedClusteringcomesintoplayTime:TimeXTimeYTimeZGene110810Gene21009Gene348.63Gene4783Gene5123Intensity(expressionlevel)ofgeneatmeasuredtime2024/9/911ClusteringofMicroarrayDataPloteachdatumasapointinN-dimensionalspaceMakeadistancematrixforthedistancebetweeneverytwogenepointsintheN-dimensionalspaceGeneswithasmalldistancesharethesameexpressioncharacteristicsandmightbefunctionallyrelatedorsimilar.Clusteringrevealgroupsoffunctionallyrelatedgenes2024/9/912ClusteringofMicroarrayData(cont’d)Clusters2024/9/913HomogeneityandSeparationPrinciplesHomogeneity:ElementswithinaclusterareclosetoeachotherSeparation:Elementsindifferentclustersarefurtherapartfromeachother…clusteringisnotaneasytask!Giventhesepointsaclusteringalgorithmmightmaketwodistinctclustersasfollows2024/9/914BadClusteringThisclusteringviolatesbothHomogeneityandSeparationprinciplesClosedistancesfrompointsinseparateclustersFardistancesfrompointsinthesamecluster2024/9/915GoodClusteringThisclusteringsatisfiesboth

HomogeneityandSeparationprinciples2024/9/916ClusteringTechniquesAgglomerative:Startwitheveryelementinitsowncluster,anditerativelyjoinclusterstogetherDivisive:StartwithoneclusteranditerativelydivideitintosmallerclustersHierarchical:Organizeelementsintoatree,leavesrepresentgenesandthelengthofthepathesbetweenleavesrepresentsthedistancesbetweengenes.Similargenesliewithinthesamesubtrees2024/9/917HierarchicalClustering2024/9/918HierarchicalClustering:Example2024/9/919HierarchicalClustering:Example2024/9/920HierarchicalClustering:Example2024/9/921HierarchicalClustering:Example2024/9/922HierarchicalClustering:Example2024/9/923HierarchicalClustering(cont’d)HierarchicalClusteringisoftenusedtorevealevolutionaryhistory2024/9/924HierarchicalClusteringAlgorithmHierarchicalClustering(d

,n)FormnclusterseachwithoneelementConstructagraphTbyassigningonevertextoeachclusterwhilethereismorethanoneclusterFindthetwoclosestclustersC1andC2

MergeC1andC2intonewclusterCwith|C1|+|C2|elementsComputedistancefromCtoallotherclustersAddanewvertexCtoTandconnecttoverticesC1andC2RemoverowsandcolumnsofdcorrespondingtoC1andC2Addarowandcolumntod

corrspondingtothenewclusterC

returnTThealgorithmtakesanxndistancematrixdofpairwisedistancesbetweenpointsasaninput.2024/9/925HierarchicalClusteringAlgorithmHierarchicalClustering(d

,n)FormnclusterseachwithoneelementConstructagraphTbyassigningonevertextoeachclusterwhilethereismorethanoneclusterFindthetwoclosestclustersC1andC2

MergeC1andC2intonewclusterCwith|C1|+|C2|elements

ComputedistancefromCtoallotherclustersAddanewvertexCtoTandconnecttoverticesC1andC2RemoverowsandcolumnsofdcorrespondingtoC1andC2Addarowandcolumntod

corrspondingtothenewclusterC

returnTDifferentwaystodefinedistancesbetweenclustersmayleadtodifferentclusterings2024/9/926HierarchicalClustering:RecomputingDistances

dmin(C,C*)=mind(x,y)

forallelementsxinCandyinC*Distancebetweentwoclustersisthesmallestdistancebetweenanypairoftheirelements

davg(C,C*)=(1/|C*||C|)∑d(x,y)

forallelementsxinCandyinC*Distancebetweentwoclustersistheaveragedistancebetweenallpairsoftheirelements2024/9/927系統(tǒng)聚類(lèi)例：微陣列數(shù)據(jù)2024/9/928評(píng)估表達(dá)模式的相似性?xún)尚袛?shù)據(jù)之間的相似性或者距離如何量化。歐幾里德距離。采用pearson相關(guān)系數(shù)r(-1,1)。如果兩個(gè)基因之間r為1，說(shuō)明兩個(gè)數(shù)據(jù)表達(dá)模式吻合得很好如果兩個(gè)基因之間r為-1，也說(shuō)明兩個(gè)數(shù)據(jù)表達(dá)模式吻合得很好（一上升，一下降）r＝0，則說(shuō)明表達(dá)模式之間沒(méi)什么相關(guān)性2024/9/929數(shù)據(jù)標(biāo)準(zhǔn)化計(jì)算第2個(gè)和第10個(gè)基因的平均值和標(biāo)準(zhǔn)方差減去平均值，然后除以標(biāo)準(zhǔn)方差，得到每行的標(biāo)準(zhǔn)化數(shù)據(jù)2024/9/930求pearson相關(guān)系數(shù)求經(jīng)過(guò)標(biāo)準(zhǔn)化以后的兩向量的內(nèi)積，再除以元素個(gè)數(shù)2024/9/931分析基因2，11與基因6，10之間表達(dá)比值正好各自相反，因此相關(guān)系數(shù)r(2,11)，r(6,10)應(yīng)該是-1。2024/9/932數(shù)據(jù)標(biāo)準(zhǔn)化以后基因兩兩之間的相關(guān)系數(shù)2024/9/933根據(jù)相關(guān)系數(shù)進(jìn)行聚類(lèi)（層次聚類(lèi)法）1，計(jì)算所有元素兩兩之間的距離（相關(guān)系數(shù)），創(chuàng)建一個(gè)距離矩陣。每個(gè)元素就是一個(gè)類(lèi)，僅僅包含它自己。2，尋找距離最小的兩個(gè)類(lèi)（相關(guān)系數(shù)最大）。3，將這兩個(gè)類(lèi)合并為一個(gè)新的類(lèi)。新的類(lèi)替換這兩個(gè)類(lèi)，重新計(jì)算所有的距離，修改相似性矩陣。4，重復(fù)2，3步驟直到所有的類(lèi)聚集為一個(gè)類(lèi)。2024/9/934迭代過(guò)程首先會(huì)發(fā)現(xiàn)r(5,10)=1，然后把基因5和10歸為一類(lèi)，然后需要重新計(jì)算距離矩陣。2024/9/935聚類(lèi)圖2024/9/936主要內(nèi)容Microarrays（微陣列）HierarchicalClustering（層次聚類(lèi)或系統(tǒng)聚類(lèi)）K-MeansClustering（K-均值聚類(lèi)）2024/9/937SquaredErrorDistortion（平方誤差失真）Givenadatapoint

vandasetofpointsX,definethedistancefromvtoX

d(v,X)asthe(Eucledian)distancefromvtotheclosestpointfromX.Givenasetofndatapoints

V={v1…vn}andasetofkpointsX,definetheSquaredErrorDistortion

d(V,X)=∑d(vi,X)2/n1<

i

<

n

2024/9/938K-MeansClusteringProblem:FormulationInput:Aset,V,consistingofnpointsandaparameterkOutput:AsetXconsistingofkpoints(clustercenters)thatminimizesthesquarederrordistortiond(V,X)overallpossiblechoicesofX。2024/9/9391-MeansClusteringProblem:anEasyCaseInput:Aset,V,consistingofnpointsOutput:Asinglepointsx(clustercenter)thatminimizesthesquarederrordistortiond(V,x)overallpossiblechoicesofx。

2024/9/9401-MeansClusteringProblem:anEasyCaseInput:Aset,V,consistingofnpointsOutput:Asinglepointsx(clustercenter)thatminimizesthesquarederrordistortiond(V,x)overallpossiblechoicesofx

1-MeansClusteringproblemiseasy.However,itbecomesverydifficult(NP-complete)formorethanonecenter.AnefficientheuristicmethodforK-MeansclusteringistheLloydalgorithm

2024/9/941K-MeansClustering:LloydAlgorithmLloydAlgorithmArbitrarilyassignthekclustercenterswhiletheclustercenterskeepchangingAssigneachdatapointtotheclusterCi correspondingtotheclosestcluster representative(center)(1≤i≤k)Aftertheassignmentofalldatapoints, computenewclusterrepresentatives

accordingtothecenterofgravityofeach cluster,thatis,thenewclusterrepresentativeisforallvinCforeveryclusterC

*Thismayleadtomerelyalocallyoptimalclustering.2024/9/942x1x2x32024/9/943x1x2x32024/9/944x1x2x32024/9/945x1x2x32024/9/946ConservativeK-MeansAlgorithmLloydalgorithmisfastbutineachiterationitmovesmanydatapoints,notnecessarilycausingbetterconvergence.AmoreconservativemethodwouldbetomoveonepointatatimeonlyifitimprovestheoverallclusteringcostThesmallertheclusteringcostof