Unformatted text preview:

Gene and Protein Networks Monday, April 10 2006What is a network?Networks are everywhereSocial networksSexual networksTransportation networksPower gridsAirline routesInternetInternetWorld-Wide-WebGene and protein networksMetabolic networksMetabolic networksMetabolic networksProtein interaction networksGene regulatory networksSignaling networksSignaling networksSynthetic sick or lethal (SSL)SSL networksOther biological networksWhat they really look like…We need models!Traditional graph modelingIntroduce small-world networksSmall-world NetworksSmall-world measuresWatts-Strogatz small-world modelMeasures of the W-S modelSmall-world measures of various graph typesAnother network property: Degree distribution P (k)Degree distribution of E-R random networksDegree distribution of many real-world networksC of 43 metabolic networksScaling of the clustering coefficient C(k)Many real-world networks are small-world, scale-freeThere is information in a gene’s position in the networkConfidence assessmentConfidence assessmentUse clustering coefficient, a local propertyMutual clustering coefficientMutual clustering coefficientPredictionConfidence assessmentThe synthetic lethal network has many triangles 2-hop predictors for SSLMulti-color motifsSSL “hubs” might be good cancer drug targetsPredict protein function from function of neighboring proteinsPredict protein function from neighboring proteins (2)LethalityDegree anti-correlationBeware of biasProtein abundanceDegree correlationCommunity structureCommunity structureFinding the communitiesHierarchical clustering (1) Using natural edge weightsHierarchical clustering (2) Topological overlapHierarchical clustering (3) Adjacency vector“Betweenness” centralityDense subgraphs Similar subgraphsSpectral clusteringParty and date hubsNetwork connectivityRemoving date hubs shatters network into communitiesTemporal partitioningFinal wordsGene and Protein NetworksMonday, April 10 2006CSCI 7000-005: Computational GenomicsDebra [email protected] is a network?• A collection of objects (nodes, vertices)• Binary relationships (edges)• May be directed• Also called agraphNetworks are everywhereSocial networksfrom www.liberality.orgNodes:PeopleEdges:FriendshipSexual networksNodes:PeopleEdges:Romantic and sexual relationsTransportation networksNodes:LocationsEdges:RoadsPower gridsNodes:Power stationEdges:High voltage transmission lineAirline routesNodes:AirportsEdges:FlightsInternetNodes:MBone RoutersEdges:Physical connectionInternetNodes:Autonomous systemsEdges:Physical connectionWorld-Wide-WebNodes:Web documentsEdges:HyperlinksGene and protein networksMetabolic networksNodes:MetabolitesEdges:Biochemical reaction(enzyme)from web.indstate.eduMetabolic networks• Drug targets predictedNodes:MetabolitesEdges:Biochemical reaction(enzyme)from www.bact.wisc.eduMetabolic networksNodes:MetabolitesEdges:Biochemical reaction(enzyme)Protein interaction networks• Gene function predictedfrom www.embl.deNodes:ProteinsEdges:Observed interactionGene regulatory networks• Inferred from error-prone gene expression datafrom Wyrick et al. 2002Nodes:Genes or gene productsEdges:Regulation of expressionSignaling networksNodes:Molecules(e.g., Proteins orNeurotransmitters)Edges:Activation orDeactivationfrom pharyngula.orgSignaling networksNodes:Molecules(e.g., Proteins orNeurotransmitters)Edges:Activation orDeactivationfrom www.life.uiuc.eduSynthetic sick or lethal (SSL)Cells live(wild type)Cells liveCells liveCells dieor grow slowlyXYXYXYXYSSL networks• Gene function, drug targets predictedNodes:Nonessential genesEdges:Genes co-lethalfrom Tong et al. 2001XYOther biological networks• Coexpression– Nodes: genes– Edges: transcribed at same times, conditions• Gene knockout / knockdown– Nodes: genes– Edges: similar phenotype (defects) when suppressedWhat they really look like…We need models!Traditional graph modelingRandom Regularfrom GD2002Introduce small-world networksSmall-world Networks• Six degrees of separation• 100 – 1000 friends each• Six steps: 1012-1018•But…We live in communitiesSmall-world measures• Typical separation between two vertices– Measured by characteristic path length• Cliquishness of a typical neighborhood– Measured by clustering coefficientvCv= 1.00vCv= 0.33Watts-Strogatzsmall-world modelMeasures of the W-S model• Path length drops faster than cliquishness• Wide range of phas both small-worldpropertiesSmall-world measures of various graph typesCliquishnessCharacteristic Path LengthRegular graphHigh LongRandom graphLow ShortSmall-world graphHigh ShortAnother network property: Degree distribution P(k)•The degree (notation: k) of a node is the number of its neighbors•The degree distribution is a histogram showing the frequency of nodes having each degreeDegree distribution of E-R random networksBinomial degree distribution, well-approximated by a PoissonDegree = kP(k)Erdös-Rényi random graphsNetwork figures from Strogatz, Nature 2001Degree distribution of many real-world networksScale-free networksDegree distribution follows a power lawP(k = x) = α x-β05Degree = kP(k)log klog P(k)Hierarchical NetworksRavasz, et al., Science 20023. Scaling clustering coefficient (DGM)2. Clustering coefficientindependent of NProperties of hierarchical networks1. Scale-freeC of 43 metabolic networks• Independent of NRavasz, et al., Science 2002Scaling of the clustering coefficient C(k)• Metabolic networksRavasz, et al., Science 2002Many real-world networks aresmall-world, scale-free• World-wide-web• Collaboration of film actors (Kevin Bacon)• Mathematical collaborations (Erdös number)• Power grid of US• Syntactic networks of English• Neural network of C. elegans• Metabolic networks• Protein-protein interaction networksThere is information in a gene’s position in the networkWe can use this to predict• Relationships– Interactions – Regulatory relationships• Protein function–Process– Complex / “molecular machine”Confidence assessment• Traditionally, biological networks determined individually– High confidence –Slow• New methods look at entire organism– Lower confidence (≥ 50% false positives)• Inferences made based on this dataConfidence assessment• Can use topology to assess confidence if true edges and false edges have different network properties• Assess how well each edge fits topology of true network• Can also predict unknown


View Full Document

CU-Boulder CSCI 7000 - Gene and Protein Networks

Download Gene and Protein Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Gene and Protein Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Gene and Protein Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?