聚類與樹Clustering2024/9/91主要內容Microarrays（微陣列）HierarchicalClustering（層次聚類或系統聚類）K-MeansClustering（K-均值聚類）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系統聚類例：微陣列數據2024/9/928評估表達模式的相似性兩行數據之間的相似性或者距離如何量化。歐幾里德距離。采用pearson相關系數r(-1,1)。如果兩個基因之間r為1，說明兩個數據表達模式吻合得很好如果兩個基因之間r為-1，也說明兩個數據表達模式吻合得很好（一上升，一下降）r＝0，則說明表達模式之間沒什么相關性2024/9/929數據標準化計算第2個和第10個基因的平均值和標準方差減去平均值，然后除以標準方差，得到每行的標準化數據2024/9/930求pearson相關系數求經過標準化以后的兩向量的內積，再除以元素個數2024/9/931分析基因2，11與基因6，10之間表達比值正好各自相反，因此相關系數r(2,11)，r(6,10)應該是-1。2024/9/932數據標準化以后基因兩兩之間的相關系數2024/9/933根據相關系數進行聚類（層次聚類法）1，計算所有元素兩兩之間的距離（相關系數），創建一個距離矩陣。每個元素就是一個類，僅僅包含它自己。2，尋找距離最小的兩個類（相關系數最大）。3，將這兩個類合并為一個新的類。新的類替換這兩個類，重新計算所有的距離，修改相似性矩陣。4，重復2，3步驟直到所有的類聚集為一個類。2024/9/934迭代過程首先會發現r(5,10)=1，然后把基因5和10歸為一類，然后需要重新計算距離矩陣。2024/9/935聚類圖2024/9/936主要內容Microarrays（微陣列）HierarchicalClustering（層次聚類或系統聚類）K-MeansClustering（K-均值聚類）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