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

BIOINFORMATICS

Dataandtextmining

ORIGINALPAPER

Vol.23no.22007,pages232–239doi:10.1093/bioinformatics/btl571

SAGA:asubgraphmatchingtoolforbiologicalgraphs

YuanyuanTian1,RichardC.McEachin2,CarlosSantos3,DavidJ.States3andJigneshM.Patel1,Ã

1

DepartmentofElectricalEngineeringandComputerScience,2NationalCenterforIntegrativeBiomedicalInformaticsand3DepartmentofHumanGeneticsandBioinformaticsProgram,UniversityofMichigan,AnnArbor,MI48109,USA

ReceivedonAugust22,2006;revisedonNovember7,2006;acceptedonNovember8,2006AdvanceAccesspublicationNovember16,2006AssociateEditor:MartinBishop

ABSTRACT

Motivation:Withtherapidincreaseintheavailabilityofbiologicalgraphdatasets,thereisagrowingneedforeffectiveandefficientgraphquery-ingmethods.Duetothenoisyandincompletecharacteristicsofthesedatasets,exactgraphmatchingmethodshavelimiteduseandapproxi-mategraphmatchingmethodsarerequired.Unfortunately,existinggraphmatchingmethodsaretoorestrictiveastheyonlyallowexactornearexactgraphmatching.ThispaperpresentsanovelapproximategraphmatchingtechniquecalledSAGA.Thistechniqueemploysaflexi-blemodelforcomputinggraphsimilarity,whichallowsfornodegaps,nodemismatchesandgraphstructuraldifferences.SAGAemploysanindexingtechniquethatallowsittoefficientlyevaluatequeriesevenagainstlargegraphdatasets.

Results:SAGAhasbeenusedtoquerybiologicalpathwaysandlitera-turedatasets,whichhasrevealedinterestingsimilaritiesbetweendistinctpathwaysthatcannotbefoundbyexistingmethods.Thesematchesassociateseeminglyunrelatedbiologicalprocesses,connectstudiesindifferentsub-areasofbiomedicalresearchandthusposehypothesesfornewdiscoveries.SAGAisalsoordersofmagnitudefasterthanexistingmethods.

Availability:SAGAcanbeaccessedfreelyviathewebatdoc.guandang.net

Supplementarymaterial:Supplementarymaterialisavailableatdoc.guandang.net.

1INTRODUCTION

Graphsprovideapowerfulprimitiveformodelingbiologicaldata,suchaspathwaysandproteininteractionnetworks.Naturally,thebiomedicalcommunityhascreatedmanygraphdatabases.Forexample,PathGuide(doc.guandang.net)listsmorethan200pathwaydatabases.Manyofthesedatabasesarelargeandrapidlygrowinginsize.Tofullyexploitthewealthofinformationinthesegraphdatabases,effectiveandef cientgraphqueryingtoolsarecritical.

Previousgraphqueryingtoolshavelargelyfocusedonrelativelysimplegraphoperations,suchasretrievingmatchesbasedonthe

Ã

Towhomcorrespondenceshouldbeaddressed.

nodeattributesor ndinglinearpaths.However,inpractice,moresophisticatedapproximategraphmatchingmethodsareoftenneeded.Notethattheemphasishereisonapproximatematching,asbiologicalgraphsareoftennoisyandincomplete,whichmakesapproximatematchingmuchmoreusefulthanexactmatching.ThispaperpresentsatoolcalledtheSubstructureIndex-basedApproxi-mateGraphAlignment(SAGA),whichaddressesthisneed.

Moreformally,theproblemthatweaddressisapproximatesubgraphmatching:Givenaquerygraphandadatabaseofgraphs,wewantto ndsubgraphsinthedatabasethataresimilartothequery,allowingfornodemismatches,nodegaps(nodeinsertionsordeletions),aswellasgraphstructuraldifferences.Nodemismatchesmodelthebehaviorthattwonodesrepresentingdifferentcellularentitiescanexhibitsimilarfunctionality.Forexample,twodifferentproteinsmaybeinthesameproteinorthologousgroup,whichindicatessimilarfunctionality.Nodegapsrepresentthesituationwhereacertainnodeinonegraphcannotbemappedtoanynodeintheothergraph.Graphstructuraldifferencesallowfordifferencesinnodeconnectivityrelationships.Forexample,twonodesmaybedirectlyconnectedinonegraph,whereasthecorrespondingmatch-ingnodesintheothergraphsmaybeindirectlyrelatedthroughoneormoreadditionalnodes.

Asamotivatingexamplefortheapproximatesubgraphoperation,considerthefollowingscenario:ascientistworkingonacertaindiseasehasconstructedasmallportionofapathwaybasedonanalysisofvariousexperimentaldata.Thispathwayfragment,whichismodeledasagraph,containsnodesthatrepresentcellularentities(proteins,genes,mRNA,etc.)andedgesthatrepresentinteractions.Thescientistisinterestedin ndingthebiologicalprocessesthatmaybeaffectedbythedisease.Thistaskcanbeexpressedasaquerythatsearchesadatabaseofknownpathwaysusingthequerygraph.Furthermore,thesearchcanidentifysimilarsubcomponentssharedbetweenthequeryandgraphsinthedatabase,whichmayrevealcluesaboutwhatinformationmightbemissingorspuriousinthequerygraph,andprovideawayofgeneratingadditionalhypotheses.

Whilethereisalonghistoryofresearchongraphmatching,mostofthisworkhasfocusedonexactsubgraphmatching,i.e.thesubgraphisomorphismproblem,whichisknowntobeNP-complete.GraphGrep(Shashaetal.,2002)andGIndex(Yanetal.,2004)areindex-based lteringmethodsforexactsubgraph

Ó2006TheAuthor(s)

ThisisanOpenAccessarticledistributedunderthetermsoftheCreativeCommonsAttributionNon-CommercialLicense(doc.guandang.net)whichpermitsunrestrictednon-commercialuse,distribution,andreproductioninanymedium,providedtheoriginalworkisproperlycited.

第1页

你可能喜欢

热门文档

相关文档

  • 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