文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 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

matching.Gra l(Yanetal.,2005),PIS(Yanetal.,2006)andClosure-Tree(HeandSingh,2006)introducesomeapproximationforsubgraphisomorphism.However,theseapproximatemodelsareverylimited.Noneofthesetoolsallownodegapsintheirmodels.PathAligner(ChenandHofestaedt,2004)isatoolforaligningpathways.However,itassumesthatallpathwaysarelinearpaths.ThetoolsmostcloselyrelatedtoourworkarePathBlast(Kelleyetal.,2004)andthesuccessiveNetworkBlast(Sharanetal.,2005),whicharedesignedforaligningproteininteractionnetworks.Theirgraphsimilaritymodelallowsnodemismatchesandnodegaps,butgraphstructuraldifferencesarelargelycon nedtoshortpaths.AsshowninSection3.5,ourgraphsimilaritymodeltoleratesmoregeneralstructuraldifferences,andcan ndbiologi-callyrelevantmatches,whenbothPathBlastandNetworkBlastfail.Anotherrelatedmethod(Koyuturketal.,2005)hasbeenproposedforaligningproteininteractionnetworks.However,thematchtech-niqueusedinthismethodlargelyfocusesoncapturingthepenaltyassociatedwithgeneduplication.Finally,PathBlast,NetworkBlastandthemethodproposedinKoyuturketal.(2005)canonlyperformonegraphcomparisonatatime.Tomatchaqueryagainstadatabaseofgraphs,thematchingalgorithmsmustberunforeachgraphinthedatabase.Asaresult,thesemethodsarenotcomputationallyef cientwhenqueryinglargegraphdatabases.

Inthispaper,wepresentanovelapproximatesubgraphmatchingtechniquecalledSAGA.AttheheartofSAGAisa exiblemodelforcomputinggraphsimilarity,whichpermitsnodegaps,nodemismatchesandgraphstructuraldifferences.Tospeeduptheexecutionofquerieswiththispowerfulmatchingmodel,weemployanindexingmethodforef cientqueryevaluation.Throughexperi-mentalevaluation,wedemonstratethatSAGAismore exibleandpowerfulthanexistingmodels.SAGAallowsadditionalinforma-tionderivedfromtherelationshipsbetweenentitiesinpathwaystobeincorporatedintocomparativeanalysis.OurexperimentalresultsshowthatSAGA ndsexpectedassociations,likeInsulinsignalinginType2DiabetesMellitus(T2DM).SAGAalso ndslesswellstudiedassociations,liketheToll-likereceptor,T-cellreceptorandApoptosispathwaysinHelicobacterpylori(H.pylori)infection,aswellasCalcium,WntandHedgehogsignalinginBipolarDis-order.Inaddition,SAGAprovidesapowerfultoolforbiomedicaltextcomparison.

Fig.1.(a)Anexamplegraph.(b)Anexamplesubgraphmatch.

2.2Distancemeasureforsubgraphmatching

Ourmodelmeasuressimilaritybyadistancevalue,sographsthataremoresimilarhaveasmallerdistance.Formally,thesubgraphmatchingisde nedasfollows:LetG1¼(V1,E1,f1)andG2¼(V2,E2,f2)betwographs.AnapproximatematchingfromG1(thequery)toG2(thetarget)isabijection

^1$V^2,whereV^1jV1andV^2jV2.mappingfunctionl:V

AnexamplematchisshowninFigure1.Thedashedlinesindicatethematchednodesinthetwographs.Notethatnodescanbemappedeveniftheyhavedifferentlabels.Also,notethatnotallnodesarerequiredtobemapped,e.g.v5inG1hasnomappinginG2,andisagapnode.

Thesubgraphdistance(SGD),withrespecttol,isde nedas:

SGDlðG1 G2Þ¼we·StructDistl

þwn·NodeMismatcheslþwg·NodeGapsl

where

StructDistl¼

X

1 u<vu v2V

ð1Þ

jdG1ðu vÞÀdG2ðlu lvÞjX

1u2V

ð2Þð3Þð4Þ

NodeMismatchesl¼mismatchðf1ðuÞ f2ðluÞÞX

gapG1ðuÞ

NodeGapsl¼

1u2V1ÀV

22.1

SYSTEMANDMETHODSGraphmodel

Thedistancemodelcontainsthreecomponents.TheStructDistcompo-nentmeasuresthestructuraldifferencesofthematch,theNodeMismatches

componentisthepenaltyassociatedwithmatchingtwonodeswithdifferentlabels,andtheNodeGapscomponentisusedtomeasurethepenaltyforthegapnodes.(Gapnodesarenodesinthequerythatcannotbemappedtoanynodesinthetargetgraph.)Eachofthesecomponentsisdescribedinmoredetailinsubsections2.2.1through2.2.3.

InEquation(1),we,wnandwgaretheweightsforeachcomponentinthismatchingmodel,andcanbeusedtochangetheemphasisonthedifferentpartsofthesimilaritymodel.WhileEquation(1)computesthesubgraphdistanceforaspeci cmatchingl,theactualsubgraphdistancefromaquerytoitstargetistheminimumdistanceoverallpossiblematchings,namely:

SGDðG1 G2Þ¼minSGDlðG1 G2Þ

l

Inourmodel,agraph,G,isa3-tupleG¼(V,E,f).VisthesetofnodesandE V·Visthesetof(directedorundirected)edges.Nodesinthegraphshavelabelsspeci edbythemappingf:V!L,whereListhesetofnodelabels.Thismodelcapturesthefeaturesthatarecommonlypresentinmostbiologicalgraphdatasets,inwhichnodesrepresentmolecules/complexes,labelsdenotemolecule/complexnamesandedgesindicaterelationshipsbetweennodes.WeassumethateachnodeinthegraphhasauniqueID.ThisIDisusedtoestablishatotalorderamongthenodes.

IntheexamplegraphinFigure1(a),viisusedtorepresenttheuniquenodeIDandLkisthenodelabel.Notethattwodifferentnodesinagraphcanhavethesamelabel.

Ourdistancemodelandmatchingalgorithm(discussedbelow)supportbothdirectedandundirectedgraphs.Wepresentourmethodusingundirectedgraphs;adaptationsofthedistancemeasureandthematchingalgorithmfordirectedgraphsarestraightforwardandomittedhere.

ð5Þ

TheStructDistcomponentmea-suresthestructuraldifferencesforthematchingnodepairsinthetwographs.InEquation2,thedGi(u,v)functionmeasuresthe‘distance’betweennodeuandnodevingraphGi,andisde nedasthelengthoftheshortestpathbetweenuandv.TheStructDistcomponentcomparesthedistancebetweeneachpairofmatchednodesinonegraphtothedistancebetweenthecorrespondingnodesintheothergraph,andaccumulatesthedifferences.TheNodeMismatchescom-ponentinEquation(3)isthesumofthepenalties(quanti edbythemismatchfunction)associatedwithmatchingnodeswithdifferentlabels.

Acommonandbiologicallyintuitivemismatchpenaltymodelistoimplicitlygroupnodelabelsbasedonsimilarity,allowingfora

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

node

2.2.1TheStructDistcomponent

2.2.2TheNodeMismatchescomponent

233

上一页第2页

你可能喜欢

热门文档

相关文档

  • 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