文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > BIOINFORMATICS ORIGINAL PAPER Data and text mining SAGA a subgraph matching tool for biolog
侵权投诉

BIOINFORMATICS ORIGINAL PAPER Data and text mining SAGA a subgraph matching tool for biolog

doi:10.1093/bioinformatics/btl571

SAGA:asubgraphmatchingtool

hitscanbemergedtoformalargermatch,sincetheyhavenocon ictsintheunion.Therefore,acliqueinthehit-compatiblegraphrepresentsasetofhitsthatcanbemergedwithoutanycon icts.

Afterformingthehit-compatiblegraph,thehitsassemblingproblemreducestothemaximalcliquedetectionproblem,whichcanbesolvedusingexistingef cientimplementations,suchas(BornandKerbosch,1973),orapproximatemethodssuchas(Hochbaum,1997).Thesetofhitsineachmaximalcliqueisacandidatematch.AdetailedexampleofthissecondstepforasamplequeryisillustratedinSection1ofthesupplementalmaterial.

Step3:examiningcandidates.Thisstepexamineseachcandidatematchandproducesasetofrealmatches.Here,weallowuserstospecifyathresholdPgtocontrolthepercentageofgapnodesinthesubgraphmatch.WithagivenPgvalue,thedesiredmatchesarethosewithatmostPgpercentageofgapnodesinthequery.

ForeachcandidatematchobtainedfromStep2,we rstcheckwhetherthepercentageofthegapnodesexceedsthethresholdPg.Ifso,weignorethecandidate.Otherwise,weprobetheDistanceIndexandcalculatetherealsubgraphmatchingdistanceasde nedinSection2.2.Recallthattherequiredsubgraphmatchingistheonethatminimizesthematchingdistance(cf.Equation5).Wealsofurtherexaminethesubmatchesofthecandidate.Asubmatchcanbeobtainedbyremovingoneormorenodemappingsfromtheoriginalmatch.Thisintroducesmoregapnodestothequery,andthusincreasesthesubgraphdistancebyadditionalgappenalties.However,atthesametime,theStructDistandNodeMismatchesmaybereducedaccordingtoitsde nitioninEquations(2)and(3).Therefore,ifthedecreasedamountexceedstheincreasedamount,theoverallmatchingdistancewillbelowerthantheoriginalone,whichalsomeansthatabettermatchisfoundforthequery.Iftwomatcheshavethesamematchingdistanceandoneisasubmatchoftheother,onlythesupermatchisconsidered.

2006)isusedfortheexperiments.Inaddition,weuseadataset,calledbioNLP,whichcontainsparsedPubMeddocumentsrepre-sentedasgraphs.Inthesegraphs,nodesrepresentgenesandedgesdenotethattwogeneswerediscussedinthesamesentencesome-whereinthedocument.WithbioNLP,graphsimilaritycanbeusedtoidentifyrelateddocuments.

3.1Implementation

2.4Fragmentsizeparameter

Thefragmentsizeparameter(kinSection2.3.1)controlsthesizeoffragmentsintheFragmentIndex.Thisparameteraffectsthesizeoftheindex,queryperformanceandsensitivityofsearchresults.AlargerfragmentsizeresultsinalargerFragmentIndex,whichincreasestheindexprobecost.However,alargefragmentsizemayalsoresultsinfewerfalsepositivesinthehitdetectionphase(andlowerquerysensitivity),whichreducesthecostoftheremainingsteps.Apracticalwayofpickingafragmentsizeisbasedontheselectivityofthequeries.Ifqueriesareexpectedtohavemanymatchesinthedatabase,thenasmallerfragmentsizeispreferredasitmaynotintroducemanyfalsepositives,andalsopotentiallyleadtosmallersizesofhit-compatiblegraphs.However,whenqueriestendtohaveveryfewmatches,alargefragmentsizemaybefavoredtoprunefalsepositivesintheearlystagesofthematchingalgorithm.

WehaveimplementedSAGAusingC++ontopofPostgreSQL(doc.guandang.net).Fordetectingmaximalcliques,weusetheversion2algorithmdescribedin(BornandKerbosch,1973).TheDistanceIndexandFragmentIndexareimplementedasclusteredB+-treeindices.Thefragmentsizewassettothree.TheexecutiontimesreportedcorrespondtotherunningtimeoftheC++program(whichincludesreadingthequeryspeci cationsandissuingSQLqueriestotheDBMStofetchindexentriesandrelateddatabasetuples).Allexperimentswererunona2.8GHzPentium4,Fedora2machineequippedwitha250GBSATAdisk.WeusedPostgreSQLversion8.1.3andsetthebufferpoolsizeto512MB.ForalltheexperimentswithKEGG,thevaluesfortheSAGAparametersare:we¼wg¼wn¼1,SingleGapCost¼3,dmax¼3andMaxPairDist¼3.ThePgvalueissetforeveryquerysothateachmatchcontainsatleastfournodemappings.Forthenodemismatchpenalty,weuseasimplemodel:iftwonodesbelongtothesameKEGGorthologousgrouportheyhavethesameECnumber,thenthemismatchpenaltyis0,and1otherwise.Forthesigni cancetest,wegenerate100randomgraphsforeachgraphinthedatabase,sotherearetotallyn·100randomgraphs,ifnisthenumberofgraphsinthedatabase.Weonlyretainmatcheswith0.01signi cancelevelorbetter.Whenaquerygraphisalsoincludedinthedatabase,wealwaysexcludetheself-match(thequerygraphmatchingitself)fromtheresults.Fortheexperi-mentwiththebioNLPdataset,theSAGAparametersettingsare:we¼wg¼wn¼1,SingleGapCost¼0.5,dmax¼3,andMaxPairDist¼3.Forthenodemismatchmodel,nodeswiththesamelabelhave0penalty,otherwisethemismatchpenaltyis1.

3.2Findingconservedcomponentsacrosspathways

Twoexperimentsareusedtoinvestigatecomponentsthataresharedacrossdifferentpathways.

3.2.1Queryingdisease-associatedpathwaysThisexperimentisanexploratoryanalysisto ndbiologicalprocessesthatareinvolvedin,orareaffectedby,aparticulardisease.Weuseall162KEGGhumanpathways(downloadedonJuly4,2006)asthedatabaseandchosethe10disease-associatedhumanpathwaysasqueries.Thisquerysetisasubsetofthe162humanpathwaysanditincludesthreemetabolicdisorderpathways,sixneuro-degenerativedisorderpath-ways,andoneinfectiousdiseasepathway.Ofthesepathways,onlytwoquerypathwaysproducedsigni canthits(P-value 0.01):theT2DMpathway(hsa04930)andthe‘EpithelialcellsignalinginH.pyloriinfection’pathway(hsa05120).ResultsforthesetwopathwaysarepresentedinTable1.Thefulllistofthedatabaseandquerypathwayscanbefoundinthesupplementalmaterial.Table1showsboththeP-valuesandthenumberofPubMedreferencesforthematches,asameasureofhowwellthediseaseas-sociationhasbeenstudiedinpreviousliterature.Weareparticularlyinterestedindisease-associatedpathwaymatchesthataresigni cantbutarenotyetwellstudied.

235

2.5Statisticalsignificanceofmatchingresults

TheMonteCarlosimulationapproachisemployedtoassessthestatisticalsigni canceofthematches.AP-valueiscomputedforeachmatchbasedonthefrequencyofobtainingsuchamatch,orabettermatch,whenapplyingSAGAwithrandomizeddata.Randomgraphsaregeneratedbyrandomshuf ingofedgesofthegraphspreservingthenodedegrees,andrandom-izingtheorthologousgroupsofeachnodepreservingthenumberofortholo-gousgroupsthateachnodebelongsto.Foragivenquery,inadditiontoqueryingtherealdatabase,werunSAGAonalargenumberofrandomgraphs,andestimatetheP-valueofamatchfromtherealdatabaseasthefractionofmatchesfromtherandomgraphswiththesameoralargersize(innumberofnodes)andthesameorasmallerdistancevalue.

3IMPLEMENTATIONANDRESULTS

Inthissection,wedescribetheimplementationofSAGAandpresentresultsdemonstratingitseffectivenessandef ciency.Thewell-knownKEGGpathwaydatabase(Kanehisaetal.,

上一页第4页

你可能喜欢

热门文档

相关文档

  • Bioinformatics

    ren Brunank , Bioinformatics:The Machine Learning Approach, A Bradford Book, The MIT press ,Cambridge, Massachusetts,London,England ,1998 [6] Eric ...

  • Bioinformatics

    49页 免费 Bioinformatics 06_swis... 30页 免费 bioinformatics-1 暂无评价 74页 2下载券 bioinformatics softwar... 13页 免费喜欢此文档的还喜欢...

  • bioinformatics-3

    Bioinformatics 65页 免费bioinformatics-3 暂无评价0人阅读0次下载举报文档§2.3 核酸...

  • Bioinformatics

    Bioinformatics_lect_1_理学_高等教育_教育专区。生物信息学 pptBioinformatics 主讲人: 陈海峰 主讲人 Shanghai Jiaotong University 2011-11-13 1 Contact ...

  • bioinformatics-4

    bioinformatics-4_农学_高等教育_教育专区。生物信息学§2.4 核酸序列的多序列比对 目的: ? 发现多个序列的共性 ? 发现与结构和功能相关的保守序列片段设:有k...

  • Bioinformatics 01

    免费 Bioinformatics 09_blast(... 暂无评价 50页 免费 Bioinformatics 03_genban... 暂无评价 46页 免费 Bioinformatics 04_DNA co... 暂无评价 49页 免费...

  • bioinformatics-4

    bioinformatics-4 隐藏>> §2.4 核酸序列的多序列比对 目的: ? 发现多个序列的共性 ? 发现与结构和功能相关的保守序列片段设:有k个序列s1, s2, ... ,...

  • bioinformatics.btu635

    bioinformatics.btu635_生物学_自然科学_专业资料。宏基因功能分析中特征选择和比较的二级统计程序Bioinformatics Advance Access published September 24, 2014 Genome ...

  • Bioinformatics-2010-Arends-2990-2

    BIOINFORMATICS APPLICATIONS NOTE Genetics and population analysis Vol. 26 no. 23 2010, pages 2990–2992 doi:10.1093/bioinformatics/btq565 Advance Access ...

  • BIOINFORMATICS BicAT A Biclustering Analysis Toolbox

    Bioinformatics Advance Access published March 21, 2006 BIOINFORMATICS BicAT: A Biclustering Analysis Toolbox Simon Barkow a? Stefan Bleuler a , Amela Preli?...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email