资源描述：
《clustering gene expression patterns》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ClusteringGeneExpressionPatternsyzAmirBen-DorRonShamirZoharYakhiniJuly141999AbstractRecentadvancesinbiotechnologyallowresearcherstomeasureexpressionlevelsforthousandsofgenessimultaneously,acrossdi erentconditionsandovertime.Analysisofdataproducedbysuchexperimentso erspotentialinsightintogenefuncti
2、onandregulatorymechanisms.Akeystepintheanalysisofgeneexpressiondataisthedetectionofgroupsofgenesthatmanifestsimilarexpressionpatterns.Thecorrespondingalgorithmicproblemistoclustermulti-conditiongeneexpressionpatterns.Inthispaperwedescribeanovelclusteringalgorithmthatwasdevelopedforanalysisofgeneex-
3、pressiondata.Wede neanappropriatestochasticerrormodelontheinput,andprovethatundertheconditionsofthemodel,thealgorithmrecoverstheclusterstructurewithhighprobability.Therunning2ctimeofthealgorithmonann-genedatasetisO(n(log(n))).Wealsopresentapracticalheuristicbasedonthesamealgorithmicideas.Theheurist
4、icwasimplementedanditsperformanceisdemonstratedonsimulateddataandonrealgeneexpressiondata,withverypromisingresults.1IntroductionInanylivingcellthatundergoesabiologicalprocess,di erentsubsetsofitsgenesareexpressedindi erentstagesoftheprocess.Theparticulargenesexpressedatagivenstageandtheirrelativeab
5、undancearecrucialtothecell'sproperfunction.Measuringgeneexpressionlevelsindi erentdevelopmentalstages,di erentbodytissues,di erentclinicalconditionsanddi erentorganismsisinstrumentalinunderstandingbiologicalprocesses.Suchinformationcanhelpthecharacterizationofgenefunction,thedeterminationofe ectsof
6、experimentaltreatments,andtheunderstandingofmanyothermolecularbiologicalprocesses.Currentapproachestomeasuringgeneexpressionpro lesincludeSAGE[34],RT/PCR[31],andhy-bridizationbasedassays.Inthelatter,asetofoligonucleotides,orasetofappropriatecDNAmolecules,DepartmentofComputerScience&Engineering,Uni
7、versityofWashington(amirbd@cs.washington.edu).SupportedbythePrograminMathematicsandMolecularBiology.yDepartmentofComputerScience,SacklerFacultyofExactSciences,Tel-AvivUniversity,Tel-Aviv69978ISRAEL.(shamir@
